題目一：找出數(shù)組中的所有重復(fù)數(shù)字

在一個(gè)長(zhǎng)度為n的數(shù)組里所有元素都在0~n-1的范圍內(nèi)。數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個(gè)數(shù)字是重復(fù)了，也不知道每個(gè)數(shù)字重復(fù)了幾次。請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字。例如：如果輸入長(zhǎng)度為7的數(shù)組 [2,3,1,0,2,5,3]，那么對(duì)應(yīng)輸出是 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
}

上述的時(shí)間復(fù)雜度為O(n)，需要使用O(n)的輔助空間

題目二：在二維數(shù)組中查找

在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。

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實(shí)現(xiàn)鏈表及常用方法

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
            }
        }
    }
    //從尾到頭遍歷鏈表 (遞歸實(shí)現(xiàn)，但可能導(dǎo)致棧溢出)
    func reverseTraverse(pHead:ListNode?) {
        
        guard let head = pHead else {
            return
        }
        
        if (head.next != nil) {
            reverseTraverse(pHead: head.next)
        }
        
        print(head.value)
    }
}

1.刪除鏈表中倒數(shù)第n個(gè)節(jié)點(diǎ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
  
  // 設(shè)置后一個(gè)節(jié)點(diǎn)初始位置
  for _ in 0 ..< n {
    if post == nil {
      break
    }
    post = post!.next
  }
  
  // 同時(shí)移動(dòng)前后節(jié)點(diǎn)
  while post != nil && post!.next != nil {
    pre = prev!.next
    post = post!.next
  }
  
  // 刪除節(jié)點(diǎn)
  pre!.next = pre!.next!.next
  
  return dummy.next
}

題目四：斐波那契數(shù)列

求斐波那契數(shù)列的第n項(xiàng)

通常使用遞歸實(shí)現(xiàn)，但遞歸重復(fù)計(jì)算太多，效率太低

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
}

時(shí)間復(fù)雜度最壞情況：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
            }
        }
    }
}

時(shí)間復(fù)雜度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
    }
}

時(shí)間復(fù)雜度O(n^2)

題目六：查找算法

1.二分查找(找到返回下標(biāo)，未找到返回-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.地上有一個(gè)m行n列的方格。一個(gè)機(jī)器人從坐標(biāo)（0，0）的格子開(kāi)始移動(dòng)，它每次可以向左、右、上、下移動(dòng)一格，但不能進(jìn)入行坐標(biāo)和列坐標(biāo)的數(shù)位之和大于k的格子。例如：當(dāng)k為18時(shí)，機(jī)器人能夠進(jìn)入方格（35， 37），因?yàn)?+5+3+7=18，但它不能進(jìn)入方格（35，38），因?yàn)?+5+3+8=19 。請(qǐng)問(wèn)該機(jī)器人能夠到達(dá)多少個(gè)格子？

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、給你一根長(zhǎng)度為n的繩子，請(qǐng)把繩子剪成m段（n、m都是整數(shù)，n > 1、m > 1）,每段繩子的長(zhǎng)度記為k[0]、k[1]、k[2]...k[m]。請(qǐng)問(wèn)k[0] x k[1] x k[2]...x k[m]可能的最大乘積是多少？例如，當(dāng)繩子長(zhǎng)度為8時(shí)，我們把它剪成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)
}

證明：當(dāng)n >= 5時(shí)可以證明 3(n - 3) > n 并且 2(n -2) > n 也就是說(shuō)當(dāng)n大于或等于5的時(shí)候，要把繩子剪成3或者2的繩子段，又因?yàn)?3(n - 3) > 2(n -2) 成立，所以應(yīng)該盡可能多的剪成3，當(dāng)n為4時(shí)因?yàn)橹辽偌粢坏叮猿朔e最大為2*2

時(shí)間和空間復(fù)雜度O(1)

題目九 按位運(yùn)算

1.計(jì)算一個(gè)數(shù)的二進(jìn)制中有多少個(gè)1

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

題目十 數(shù)值的整數(shù)次方

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
}

題目十二 查找鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)

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
}

題目十三 合并兩個(gè)有序遞增鏈表，合并后鏈表依然有序遞增。

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
}