算法【腾讯50题Swift版】下篇

16. 最接近的三数之和

中等题，很好理解，还是固定一个i，然后双指针处理

class Solution {
    func threeSumClosest(_ nums: [Int], _ target: Int) -> Int {
        let n = nums.count
        guard n >= 3 else { return 0 }
        var a = nums
        a.sort()
        var res = a[0] + a[1] + a[2]
        for i in 0..<n {
            var l = i + 1
            var r = n - 1
            while l < r {
                let sum = a[i] + a[l] + a[r]
                if abs(sum - target) < abs(res - target) {
                    res = sum
                }
                if sum > target {
                    r -= 1
                } else if sum < target {
                    l += 1
                } else {
                    return sum
                }
            }
        }
        return res
    }
}

33. 搜索旋转排序数组

中等题，经典二分，要么左半部分是有序的，要么右半部分是有序的

class Solution {
    func search(_ nums: [Int], _ target: Int) -> Int {
        var l = 0, r = nums.count - 1
        while l <= r {
            let mid = (r + l) >> 1
            if nums[mid] == target {
                return mid
            }
            if nums[l] <= nums[mid] {
                if target >= nums[l], target < nums[mid] {
                    r = mid - 1
                } else {
                    l = mid + 1
                }
            } else {
                if target > nums[mid], target <= nums[r] {
                    l = mid + 1
                } else {
                    r = mid - 1
                }
            }
        }
        return -1
    }
}

43. 字符串相乘

中等题，这题出的没啥意义，不点评了

class Solution {
    func multiply(_ num1: String, _ num2: String) -> String {
        if num1 == "0" || num2 == "0" {
            return "0"
        }
        let arr1 = Array(num1), arr2 = Array(num2)
        var res = Array(repeating: 0, count: arr1.count + arr2.count)
        for i in (0..<arr1.count).reversed() {
            let n1 = Int(String(arr1[i]))!
            for j in (0..<arr2.count).reversed() {
                let n2 = Int(String(arr2[j]))!
                let sum = n1 * n2 + res[i+j+1] + (res[i+j] * 10)
                res[i+j+1] = sum % 10
                res[i+j] = sum / 10
            }
        }
        var result = ""
        for i in 0..<res.count {
            if i == 0, res[0] == 0 {
                continue
            }
            result += "\(res[i])"
        }
        return result
    }
}

46. 全排列

中等题，全排列是很重要的，本题里数组元素都不同才转化为集合来做，如果有重复元素用数组做也可以

class Solution {
    func permute(_ nums: [Int]) -> [[Int]] {
        let n = nums.count
        var ans: [[Int]] = []
        var path: [Int] = Array(repeating: 0, count: n)
        func dfs(_ i: Int, _ s: Set<Int>) {
            if i == n {
                ans.append(path)
                return
            }
            for x in s {
                path[i] = x
                var s1 = s
                s1.remove(x)
                dfs(i+1, s1)
            }
        }
        dfs(0, Set<Int>(nums))
        return ans
    }
}

53. 最大子数组和

中等题，动态规划，简单来说就是用数组来记录到每一位的最大连续子数组和

class Solution {
    func maxSubArray(_ nums: [Int]) -> Int {
        var n = nums
        for i in 1..<n.count {
            if n[i-1] > 0 {
                n[i] += n[i-1]
            }
        }
        return n.max()!
    }
}

54. 螺旋矩阵

中等题，四条边不断向内压缩，注意方向和临界条件即可

class Solution {
    func spiralOrder(_ matrix: [[Int]]) -> [Int] {
        if matrix.isEmpty {
            return []
        }
        var l = 0, r = matrix[0].count - 1, t = 0, b = matrix.count - 1
        var res: [Int] = []
        while true {
            for i in l...r { res.append(matrix[t][i]) }
            t += 1
            if t > b {break}
            for i in t...b { res.append(matrix[i][r]) }
            r -= 1
            if r < l {break}
            for i in (l...r).reversed() { res.append(matrix[b][i]) }
            b -= 1
            if b < t {break}
            for i in (t...b).reversed() { res.append(matrix[i][l]) }
            l += 1
            if l > r {break}

        }
        return res
    }
}

59. 螺旋矩阵 II

中等题，跟上题差不多，由取数变成了填数

class Solution {
    func generateMatrix(_ n: Int) -> [[Int]] {
        if n == 1 {
            return [[1]]
        }
        var l = 0, r = n - 1, t = 0, b = n - 1
        var res = Array(repeating: Array(repeating: 0,count: n) ,count: n)
        var num = 0
        while true {
            for i in l...r { num += 1; res[t][i] = num }
            t += 1
            if t > b {break}
            for i in t...b { num += 1; res[i][r] = num }
            r -= 1
            if r < l {break}
            for i in (l...r).reversed() { num += 1; res[b][i] = num }
            b -= 1
            if b < t {break}
            for i in (t...b).reversed() { num += 1; res[i][l] = num }
            l += 1
            if l > r {break}

        }
        return res
    }
}

61. 旋转链表

中等题，简单来说就是遍历链表拿到尾结点和长度，有了长度就能拿到应该截断的位置，然后截断再接上

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func rotateRight(_ head: ListNode?, _ k: Int) -> ListNode? {
        if head == nil || k == 0 {
            return head
        }
        var n = 0
        var trail: ListNode?
        var node: ListNode? = head
        while node != nil {
            trail = node
            node = node!.next
            n += 1
        }
        node = head
        let m = k % n
        if m == 0 {
            return head
        }
        for _ in 0..<n-m-1 {
            node = node?.next
        }
        var newH: ListNode? = node?.next
        node?.next = nil
        trail?.next = head
        return newH

    }
}

62. 不同路径

中等题，简单的动态规划，计算出每个格子的路径数，注意两条边的路径数都是1

class Solution {
    func uniquePaths(_ m: Int, _ n: Int) -> Int {
        var dp = Array(repeating: Array(repeating: 1, count: n), count: m)
        for i in 1..<m {
            for j in 1..<n {
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
            }
        }
        return dp[m-1][n-1]
    }
}

78. 子集

中等题，每多一个数，相当于在当前的子集中插入一个数，再加上此数自身

class Solution {
    func subsets(_ nums: [Int]) -> [[Int]] {
        var result: [[Int]] = []
        for i in nums {
            let temp = [i]
            for n in result {
                result.append(n + temp)
            }
            result.append(temp)
        }
        result.append([])
        return result
    }
}

89. 格雷编码

中等题，简单理解就是前加1，再镜像，镜像的再前加1。用递归解决

class Solution {
    func grayCode(_ n: Int) -> [Int] {
        if n == 0 {
            return [0]
        }
        let arr1 = grayCode(n-1)
        let arr2 = arr1.reversed().map {$0 + 1<<(n-1)}
        return arr1 + arr2
    }
}

122. 买卖股票的最佳时机 II

中等题，这道题很简单，不要想复杂喽。想象一下股神的操作，每涨必持有，每跌必不在场

class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        var p: Int = 0
        for i in 1..<prices.count {
            if prices[i] - prices[i-1] > 0 {
                p += prices[i] - prices[i-1]
            }
        }
        return p
    }
}

142. 环形链表 II

中等题，这题需要数学推导。构建两轮快慢指针的相遇，第一次相遇后，快指针重新指向头节点，然后快指针速率降到一步，再次相遇点就是环入口。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.next = nil
 *     }
 * }
 */

class Solution {
    func detectCycle(_ head: ListNode?) -> ListNode? {
        var fast = head, slow = head
        while true {
            if fast == nil || fast?.next == nil {
                return nil
            }
            fast = fast?.next?.next
            slow = slow?.next
            if fast === slow {
                break
            }
        }
        fast = head
        while slow !== fast {
            slow = slow?.next
            fast = fast?.next
        }
        return fast
    }
}

146. LRU 缓存

中等题，本题是可以用数组来做的，但是数组的移动、删除不是O(1)，而双向链表可以做到，所以才用双向链表来做。我也验证了两种方法，发现双向链表确实比数组快了很多。

class LRUCache {
    var capacity: Int
    var map: [Int: DoubleNode] = [:]
    var first: DoubleNode?
    var last: DoubleNode?

    init(_ capacity: Int) {
        self.capacity = capacity
    }

    func get(_ key: Int) -> Int {
        if let node = map[key] {
            move(node)
            return node.value
        } else {
            return -1
        }
    }

    func put(_ key: Int, _ value: Int) {
        if let node = map[key] {
            node.value = value
            move(node)
        } else {
            add(key, value)
        }
    }
    func move(_ node: DoubleNode) {
        if node === first {
            return
        }
        if node === last {
            last = last!.pre
        }

        node.pre?.next = node.next
        node.next?.pre = node.pre

        node.next = first
        first?.pre = node
        first = node
    }
    func add(_ key: Int, _ value: Int) {
        if map.keys.count == capacity {
            delete()
        }
        let node = DoubleNode(key, value)
        node.next = first
        first?.pre = node
        first = node
        map[key] = node

        if last == nil {
            last = node
        }
    }
    func delete() {
        if let last = last {
            map[last.key] = nil
            self.last = last.pre
            self.last?.next = nil

            if first === last {
                first = nil
            }
        }
    }
}

class DoubleNode {
    var key: Int
    var value: Int
    var pre: DoubleNode?
    var next: DoubleNode?
    init(_ key: Int, _ value: Int) {
        self.key = key
        self.value = value
    }
}


/**
 * Your LRUCache object will be instantiated and called as such:
 * let obj = LRUCache(capacity)
 * let ret_1: Int = obj.get(key)
 * obj.put(key, value)
 */

148. 排序链表

中等题，用递归排序

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func sortList(_ head: ListNode?) -> ListNode? {
        if head == nil || head!.next == nil {
            return head
        }
        var fast = head!.next, slow = head
        while fast != nil, fast!.next != nil {
            slow = slow?.next
            fast = fast!.next!.next
        }
        let temp = slow?.next
        slow?.next = nil
        var left = sortList(head), right = sortList(temp), h: ListNode? = ListNode(0)
        let res = h
        while left != nil, right != nil {
            if left!.val < right!.val {
                h?.next = left
                left = left!.next
            } else {
                h?.next = right
                right = right!.next
            }
            h = h?.next
        }
        h?.next = left != nil ? left : right
        return res!.next
    }
}

155. 最小栈

中等题，用辅助栈处理最小元素问题

class MinStack {
    var stack: [Int] = []
    var min_stack: [Int] = []
    init() {

    }

    func push(_ val: Int) {
        stack.append(val)
        if min_stack.isEmpty ||  val <= min_stack.last! {
            min_stack.append(val)
        }
    }

    func pop() {
        if let k  = stack.popLast() {
            if let m = min_stack.last {
                if m == k {
                    min_stack.popLast()
                }
            }
        }
    }

    func top() -> Int {
        return stack.last!
    }

    func getMin() -> Int {
        return min_stack.last!
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * let obj = MinStack()
 * obj.push(val)
 * obj.pop()
 * let ret_3: Int = obj.top()
 * let ret_4: Int = obj.getMin()
 */

215. 数组中的第K个最大元素

中等题，生成随机数，然后用快排处理

class Solution {
    func findKthLargest(_ nums: [Int], _ k: Int) -> Int {
        return quickSelect(nums, k)
    }
    func quickSelect(_ nums: [Int], _ k: Int) -> Int {
        let ran = Int.random(in: 0..<nums.count)
        let pivot = nums[ran]
        var big: [Int] = [], small: [Int] = [], equal: [Int] = []
        for item in nums {
            if item > pivot {
                big.append(item)
            } else if item < pivot {
                small.append(item)
            } else {
                equal.append(item)
            }
        }
        if k <= big.count {
            return quickSelect(big, k)
        }
        if nums.count - small.count < k {
            return quickSelect(small, k - nums.count + small.count)
        }
        return pivot
    }
}

230. 二叉搜索树中第K小的元素

中等题，两种方法，一种是把值都存到数组里，排序数组再取值。第二种是遍历途中记录数量，达到k返回，注意添加节点的顺序是先左再自己然后右。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func kthSmallest(_ root: TreeNode?, _ k: Int) -> Int {
        var lm = 0, my = 0
        func dfs(_ node: TreeNode?) {
            if node == nil {
                return
            }
            dfs(node!.left)
            lm += 1
            if lm == k {
                my = node!.val
                return
            }
            dfs(node!.right)
        }
        dfs(root)
        return my
    }
}

235. 二叉搜索树的最近公共祖先

中等题，要么都在左边，要么都在右边，除此之外就返回当前节点

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */

class Solution {
    func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
        if p!.val < root!.val, q!.val < root!.val {
            return lowestCommonAncestor(root!.left, p, q)
        } else if p!.val > root!.val, q!.val > root!.val {
            return lowestCommonAncestor(root!.right, p, q)
        }
        return root
    }
}

236. 二叉树的最近公共祖先

中等题，递归到p或q或空为止，左右都有返回当前节点，否则左边有返回左边、右边有返回右边，都没有返回空。返回空和右边有的情况合并了。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */

class Solution {
    func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
        if root == nil || root === p || root === q {
            return root
        }
        let left = lowestCommonAncestor(root!.left, p, q)
        let right = lowestCommonAncestor(root!.right, p, q)
        if let left = left, let right = right {
            return root
        }
        return left != nil ? left : right
    }
}

237. 删除链表中的节点

中等题，注意题中说node不是末尾节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.next = nil
 *     }
 * }
 */

class Solution {
    func deleteNode(_ node: ListNode?) {
        node?.val =  node?.next?.val ?? -1
        node?.next = node?.next?.next
    }
}

238. 除自身以外数组的乘积

中等题，对角线是1，正反遍历两遍，把两边的元素都乘上

class Solution {
    func productExceptSelf(_ nums: [Int]) -> [Int] {
        var ans = Array(repeating: 1, count: nums.count)
        var temp = 1
        for i in 0..<nums.count {
            ans[i] = temp
            temp *= nums[i]
        }
        temp = 1
        for i in (0..<nums.count).reversed() {
            ans[i] *= temp
            temp *= nums[i]
        }
        return ans
    }
}

4. 寻找两个正序数组的中位数

困难题，先合并再取中位数

class Solution {
    func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
      let len = nums1.count + nums2.count
      var arr: [Int] = []
      var i = 0, j = 0
      for _ in 0..<len {
        var itemi: Int? , itemj: Int?
        if i < nums1.count {
            itemi = nums1[i]
        }
        if j < nums2.count {
            itemj = nums2[j]
        }
        if let itemi = itemi, let itemj = itemj {
            if itemi < itemj {
                arr.append(itemi)
                i += 1
            } else {
                arr.append(itemj)
                j += 1
            }
        } else if let itemi = itemi {
            arr.append(itemi)
            i += 1
        } else if let itemj = itemj {
            arr.append(itemj)
            j += 1
        }
      }
      if len % 2 == 0 {
        return Double(arr[len/2 - 1] + arr[len/2]) / 2.0
      } else {
        return Double(arr[len/2])
      }
    }
}

23. 合并 K 个升序链表

困难题，用分治方法，合并两个，将结果再和另一个合并

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        var list1: ListNode? = l1
        var list2: ListNode? = l2
        let dummy: ListNode? = ListNode()
        var node = dummy
        while list1 != nil && list2 != nil {
            if list1!.val < list2!.val {
                node?.next = list1
                list1 = list1!.next
            } else {
                node?.next = list2
                list2 = list2!.next
            }
            node = node?.next
        }
        node?.next = list1 ?? list2
        return dummy!.next

    }
    func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
        func dfs(_ i: Int,_ j: Int) -> ListNode? {
            var m = j - i
            if m == 0 { return nil }
            if m == 1 { return lists[i] }
            let left = dfs(i, i + (m >> 1))
            let right = dfs(i + (m >> 1), j)
            return mergeTwoLists(left, right)
        }
        return dfs(0, lists.count)
    }
}

124. 二叉树中的最大路径和

困难题，路径和是左子链值+右子链值+当前节点值。注意如果左或右子链和为负数，负贡献的链路直接丢弃不要。如果左右子链和都是负数，就相当于只返回当前节点值，题目说了路径可以仅包含一个节点。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func maxPathSum(_ root: TreeNode?) -> Int {
        var ans = -1000
        func dfs(_ node: TreeNode?) -> Int {
            if node == nil {
                return 0
            }
            let l_val = dfs(node?.left)
            let r_val = dfs(node?.right)
            ans = max(ans, l_val + r_val + node!.val)
            return max(0, max(l_val, r_val) + node!.val)
        }
        dfs(root)
        return ans
    }
}