剑指Offer-Swift

题目一：找出数组中的所有重复数字

在一个长度为n的数组里所有元素都在0~n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如：如果输入长度为7的数组 [2,3,1,0,2,5,3]，那么对应输出是 2、3

func duplicate (_ numbers:[Int]?, _ duplicate: inout [Int]) -> Bool {
    
    guard var temps = numbers else {
        return false
    }
    
    guard temps.count >= 0 else {
        return false
    }
    
    for number in temps {
        
        if (number < 0 || number > temps.count - 1) {
            return false
        }
 
    }
    
    for (index, _) in temps.enumerated() {
        while temps[index] != index {
            if (temps[index] == temps[temps[index]]){
                duplicate.append(temps[index])
                break
            }
            //交换temps[index] 和 temps[temps[index]]
            let temp = temps[index]
            temps[index] = temps[temps[index]]
            temps[temp] = temp
        }
    }
    
    if (duplicate.count > 0) {
        return true
    }
    
    return false
}

上述的时间复杂度为O(n)，需要使用O(n)的辅助空间

题目二：在二维数组中查找

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

func find(_ numbers:[[Int]]?, number: Int) -> Bool {
    
    guard var temps = numbers else {
        return false
    }
    
    guard temps.count > 0 else {
        return false
    }
    
    var row = 0
    var column = temps[0].count - 1
    
    while row < temps.count && column > 0 {
        
        if temps[row][column] == number {
            return true
        }else if temps[row][column] > number {
            column -= 1
        }else {
            row += 1
        }
        
    }
    
    return false
}

题目三：Swift实现链表及常用方法

class ListNode {
    var value: Int
    var next: ListNode?
    
    init(_ value: Int) {
        self.value = value
        self.next = nil
    }
}

class List {
    
    var head: ListNode?
    var tail: ListNode?
    
    func addToTail(_ value: Int) {
        let node = ListNode(value)
        
        if self.tail == nil {
            self.tail = node
            self.head = self.tail
        }else {
            self.tail!.next = node
            self.tail = self.tail!.next
        }
        
    }
    
    func addToHead(_ value: Int) {
        let node = ListNode(value)
        
        if self.head == nil {
            self.head = node
            self.tail = self.head
        }else {
            node.next = self.head
            self.head = node
        }
        
    }
    
    func removeNode(_ value: Int) {
        guard let head = self.head, let _ = self.tail else {
            return
        }
        
        var node = head
        while node.next != nil && node.next!.value != value{
            node = node.next!
        }
        
        if (node.next != nil && node.next!.value != value) {
            var temp = node.next
            node.next = node.next!.next
            
            if (temp != nil) {
                temp = nil
            }
        }
    }
    //从尾到头遍历链表 (递归实现，但可能导致栈溢出)
    func reverseTraverse(pHead:ListNode?) {
        
        guard let head = pHead else {
            return
        }
        
        if (head.next != nil) {
            reverseTraverse(pHead: head.next)
        }
        
        print(head.value)
    }
}

1.删除链表中倒数第n个节点。例：1->2->3->4->5，n = 2。返回1->2->3->5。

func removeNodeFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
  guard let head = head else {
    return nil
  }
  
  let dummy = ListNode(0)
  dummy.next = head
  var pre: ListNode? = dummy
  var post: ListNode? = dummy
  
  // 设置后一个节点初始位置
  for _ in 0 ..< n {
    if post == nil {
      break
    }
    post = post!.next
  }
  
  // 同时移动前后节点
  while post != nil && post!.next != nil {
    pre = prev!.next
    post = post!.next
  }
  
  // 删除节点
  pre!.next = pre!.next!.next
  
  return dummy.next
}

题目四：斐波那契数列

求斐波那契数列的第n项

通常使用递归实现，但递归重复计算太多，效率太低

func fibonacci (_ n: Int) -> Int64 {
    
    let result:[Int64] = [0, 1]
    if (n < 2) {
        return result[n]
    }
    
    var fibNMinusOne: Int64 = 1
    var fibNMinusTwo: Int64 = 0
    var fibN: Int64 = 0xx
    
    for _ in 2...n {
        fibN = fibNMinusOne + fibNMinusTwo
        fibNMinusTwo = fibNMinusOne
        fibNMinusOne = fibN
    }
    
    return fibN
}

题目五：排序

1.快速排序

func partition(numbers: inout [Int], start: inout Int, end: inout Int) {
    
    let key = numbers[end]
    
    while start < end {
        
        while start < end && numbers[start] <= key {
            start += 1
        }
        numbers[end] = numbers[start]
        while start < end && numbers[end] >= key {
            end -= 1
        }
        numbers[start] = numbers[end]
    }
    
    numbers[start] = key
}

时间复杂度最坏情况：O(n^2)
平均：O(nlogn)

2.冒泡排序

func bubbleSort (numbers: inout [Int]) {
    let lenght = numbers.count
    
    for i in 0..<lenght - 1 {
        
        for j in 0..<lenght - 1 - i {
            
            if (numbers[j] < numbers[j + 1]) {
                let temp = numbers[j]
                numbers[j] = numbers[j + 1]
                numbers[j + 1] = temp
            }
        }
    }
}

时间复杂度O(n^2)

3.插入排序

func insertSort<T>(_ arr:inout [T], compare:(T, T) -> Bool) {
    for i in 1..<arr.count {
        let key = arr[i]
        var j = i - 1
        
        while j >= 0 && compare(arr[j], key) {
            arr[j + 1] = arr[j]
            j -= 1
        }
        arr[j + 1] = key
    }
}

时间复杂度O(n^2)

题目六：查找算法

1.二分查找(找到返回下标，未找到返回-1)

func binarySearch (_ numbers: [Int], number: Int) -> Int {
    
    var left = 0
    var right = numbers.count - 1
    
    while left <= right {
        let mid = (left + right) / 2
        
        if (numbers[mid] > number) {
            right = mid - 1
        }else if (numbers[mid] < number) {
            left = mid + 1
        }else {
            return mid
        }
    }
    
    return -1
}

题目七：回溯法

1.地上有一个m行n列的方格。一个机器人从坐标（0，0）的格子开始移动，它每次可以向左、右、上、下移动一格，但不能进入行坐标和列坐标的数位之和大于k的格子。例如：当k为18时，机器人能够进入方格（35， 37），因为3+5+3+7=18，但它不能进入方格（35，38），因为3+5+3+8=19 。请问该机器人能够到达多少个格子？

func movingCount(threshold: Int, rows:Int, cols:Int) -> Int {
    
    guard threshold >= 0, rows > 0, cols > 0 else {
        return 0
    }
    var visited = Array(repeating: false, count: rows * cols)
    
    let count = movingCountCore(threshold, rows, cols, 0, 0, &visited)
    
    return count
}

func movingCountCore(_ threshold: Int,_ rows:Int,_ cols:Int,_ row:Int,_ col:Int,_ visited: inout [Bool]) -> Int {
    var count = 0
    
    if check(threshold: threshold, rows: rows, cols: cols, row: row, col: col, visited: visited) {
        visited[row * cols + col] = true
        
        count = 1 + movingCountCore(threshold, rows, cols, row - 1, col, &visited)
            + movingCountCore(threshold, rows, cols, row, col - 1, &visited)
            + movingCountCore(threshold, rows, cols, row + 1, col, &visited)
            + movingCountCore(threshold, rows, cols, row, col + 1, &visited)
        
    }
    
    return count
}

func check (threshold: Int, rows:Int, cols:Int, row:Int, col:Int, visited: [Bool]) -> Bool {
    
    if row >= 0 && row < rows && col < cols && getDigitSum(row) + getDigitSum(col) <= threshold && !visited[row*cols + col] {
        return true
    }
    
    return false
}

func getDigitSum(_ number: Int) -> Int {
    
    var temp = number
    var sum = 0
    
    while temp < 0 {
        sum += number % 10
        temp = temp / 10
    }
    return sum
}

题目八

1、给你一根长度为n的绳子，请把绳子剪成m段（n、m都是整数，n > 1、m > 1）,每段绳子的长度记为k[0]、k[1]、k[2]...k[m]。请问k[0] x k[1] x k[2]...x k[m]可能的最大乘积是多少？例如，当绳子长度为8时，我们把它剪成2、3、3三段，得到最大的乘积为18

贪婪算法

func maxProductAfterCutting(length: Int) -> Int {
    if length < 2 {
        return 0
    }
    
    if length == 2 {
        return 1
    }
    
    if length == 3 {
        return 2
    }
    
    var timeOf3 = length / 3
    
    if length - timeOf3 * 3 == 1 {
        timeOf3 -= 1
    }
    
    let timeOf2 = (length - timeOf3 * 3) / 2
    
    let n = powf(Float(3), Float(timeOf3))
    let m = powf(Float(2), Float(timeOf2))
    
    return Int(n * m)
}

证明：当n >= 5时可以证明 3(n - 3) > n 并且 2(n -2) > n 也就是说当n大于或等于5的时候，要把绳子剪成3或者2的绳子段，又因为 3(n - 3) > 2(n -2) 成立，所以应该尽可能多的剪成3，当n为4时因为至少剪一刀，所以乘积最大为2*2

时间和空间复杂度O(1)

题目九按位运算

1.计算一个数的二进制中有多少个1


func numberOfOne(_ number:Int) -> Int {
    
    var (n, count) = (number, 0)
    
    while n > 0 {
        count += 1
        n = (n - 1) & n
    }
    return count
}

题目十数值的整数次方


enum PowerError: Error {
    case invalidInput
}


func power(base: Double, exponent:Int) throws -> Double {
    
    if base == 0.0 && exponent < 0 {
        throw PowerError.invalidInput
    }
    
    var absExponent = exponent
    
    if exponent < 0 {
        absExponent = -exponent
    }
    
    var result = powerWithUnsignedExponent(base: base, exponent: absExponent)
    if exponent < 0 {
        result = 1.0 / result
    }
    return result
}

func powerWithUnsignedExponent(base: Double, exponent: Int) -> Double {
    
    if exponent == 0 {
        return 1
    }
    if (exponent == 1) {
        return base
    }
    
    var result = powerWithUnsignedExponent(base: base, exponent: exponent >> 1)
    result *= result
    
    if exponent & 0x1 == 1 {
        result *= base
    }
    
    return result
}

题目十一


func Reorder<T>(numbers: inout [T],_ conditions:(T) ->Bool) {
    
    if numbers.count <= 0 {
        return
    }
    
    var (start, end) = (0, numbers.count - 1)
    
    while start < end {
        
        while start < end && !conditions(numbers[start]) {
            start += 1
        }
        
        while start < end && conditions(numbers[end]) {
            end -= 1
        }
        
        if start < end {
            let temp = numbers[start]
            numbers[start] = numbers[end]
            numbers[end] = temp
        }
        
    }
    
}

Reorder(numbers: &arr) { (number:Int) -> Bool in
    return (number & 1) == 0
}

题目十二查找链表中倒数第k个节点


func findKthToTail(listHeadNode: ListNode, k:Int) -> ListNode? {
    
    var pAhead = listHeadNode
    
    for _ in 0..<k {
        
        if pAhead.next != nil {
           pAhead = pAhead.next!
        }else {
            return nil
        }
    }
    
    var pBehind = listHeadNode
    
    while pAhead.next != nil {
        
        pAhead = pAhead.next!
        pBehind = pBehind.next!
        
    }
    
    return pBehind
}

题目十三合并两个有序递增链表，合并后链表依然有序递增。

class ListNode {
    var value: Int
    var next: ListNode?

    init(_ value: Int) {
        self.value = value
        self.next = nil
    }
}

func Merge(pHead1: ListNode?, pHead2: ListNode?) -> ListNode? {
    
    guard let pHeadOne = pHead1, let pHeadTwo = pHead2 else {
        return nil
    }
    
    var pMergedHead: ListNode? = nil
    
    if (pHeadOne.value < pHeadTwo.value) {
        pMergedHead = pHeadOne
        pMergedHead?.next = Merge(pHead1: pHeadOne.next, pHead2: pHeadTwo)
    }else {
        pMergedHead = pHeadTwo
        pMergedHead?.next = Merge(pHead1: pHeadOne, pHead2: pHeadTwo.next)
    }
    
    return pMergedHead
}

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 206,602评论 6赞 481
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 88,442评论 2赞 382
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 152,878评论 0赞 344
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 55,306评论 1赞 279
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 64,330评论 5赞 373
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,071评论 1赞 285
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,382评论 3赞 400
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,006评论 0赞 259
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 43,512评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,965评论 2赞 325
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,094评论 1赞 333
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,732评论 4赞 323
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,283评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,286评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,512评论 1赞 262
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,536评论 2赞 354
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,828评论 2赞 345