散列表（上）：Word 文档中的单词拼写检查功能是如何实现的？

散列表（中）：如何打造一个工业级水平的散列表？

散列表（下）：为什么散列表和链表经常会一起使用？

哈希算法（上）：如何防止数据库中的用户信息被脱库？

哈希算法（下）：哈希算法在分布式系统中有哪些应用？

二叉树基础（上）：什么样的二叉树适合用数组来存储？

二叉树基础（下）：有了如此高效的散列表，为什么还需要二叉树？

递归树：如何借助树来求解递归算法的时间复杂度？

树的遍历 Demo

递归代码模板

如何优雅地计算斐波那契数列

LeetCode题目：

散列表

1.有效的字母异位词

class Solution {
//     // 排序然后对比解法
// func isAnagram(_ s: String, _ t: String) -> Bool {
//         let sortedS = s.sorted()
//         let sortedT = t.sorted()
//         return sortedS == sortedT ? true : false
//     }
// hashMap
    func isAnagram(_ s: String, _ t: String) -> Bool {
        if s.count != t.count { return false }
        var dictC = Dictionary<Character, Int>()
        var dictT = Dictionary<Character, Int>()
        for c in s {
            if let count = dictC[c] {
                dictC[c] = count + 1
            } else {
                dictC.updateValue(1, forKey: c)
            }
        }
        for c in t {
            if let count = dictT[c] {
                dictT[c] = count + 1
            } else {
                dictT.updateValue(1, forKey: c)
            }
        }
        for c in s {
            if dictC[c] != dictT[c] { return false }
        }
        return true
    }
}

2.字母异位词分组

class Solution {
    func groupAnagrams(_ strs: [String]) -> [[String]] {
        var res = Array<Array<String>>()
        var dict = Dictionary<Array<Int>, String>()
        for (index, str) in strs.enumerated() {
            let a: String = "a"
            let aNum = a.unicodeScalars.first!.value
            var key = Array(repeating: 0, count: 26)
            for c in str {
                key[Int(c.unicodeScalars.first!.value - aNum)] += 1
            }
            if dict[key] != nil {
                dict[key]! += "\(index),"
            } else {
                dict[key] = "\(index),"
            }
        }
        for (_, var value) in dict {
            value.removeLast()
            let indexArray = value.components(separatedBy: ",")
            var finalArray = Array<String>()
            for i in indexArray {
                finalArray.append(strs[Int(i)!])
            }
            res.append(finalArray)
        }
        return res
    }
}

二叉树

3.二叉树的前序遍历

class Solution {
        func preorderTraversal(_ root: TreeNode?) -> [Int] {
        var res = Array<Int>()
        preOrder(root, res: &res)
        return res
    }
    func preOrder(_ root: TreeNode?, res: inout Array<Int>) {
        // terminator
        if root == nil { return }
        // process current logic
        res.append(root!.val)
        // drill down
        preOrder(root?.left, res: &res)
        preOrder(root?.right, res: &res)
    }
}

4.N 叉树的前序遍历

class Solution {
        func preorder(_ root: Node?) -> [Int] {
            var res = Array<Int>()
            preorder(root, res: &res)
            return res
        }
        func preorder(_ root: Node?, res: inout Array<Int>) {
            if root == nil { return }
            res.append((root!.val))
            for i in 0..<(root?.children.count)! {
                preorder(root?.children[i], res: &res)
            }
        }
}

5.二叉树的中序遍历

class Solution {
     func inorderTraversal(_ root: TreeNode?) -> [Int] {
        var res = Array<Int>()
        inorder(root, res: &res)
        return res
    }
    func inorder(_ root: TreeNode?, res: inout Array<Int>) {
        if root == nil { return }
        inorder(root?.left, res: &res)
        res.append(root!.val)
        inorder(root?.right, res: &res)
    }
}

6.N 叉树的后序遍历

class Solution {
    func postorder(_ root: Node?) -> [Int] {
        var res = Array<Int>()
        postOrder(root, res: &res)
        return res
    }
    func postOrder(_ root: Node?, res: inout Array<Int>) {
        // terminator
        if root == nil { return }
        // process current logic
        for i in 0..<(root?.children.count)! {
            // drill down
            postOrder(root?.children[i], res: &res)
        }
        res.append(root!.val)
    }
}

7.N 叉树的层序遍历

class Solution {
    // 递归解法
    // func levelOrder(_ root: Node?) -> [[Int]] {
    //     var res = Array<Array<Int>>()
    //     var level = 0
    //     processOrder(root, res: &res, level: level)
    //     return res
    // }
    // func processOrder(_ root: Node?, res: inout Array<Array<Int>>, level: Int) {
    //     if root == nil { return }
    //     if res.count <= level {
    //         res.append([])
    //     }
    //     res[level].append(root!.val)
    //     let newLevel = level + 1
    //     for i in 0..<(root?.children.count)! {
    //         processOrder(root?.children[i], res: &res, level: newLevel)
    //     }
    // }
    //BFS解法
   func levelOrder(_ root: Node?) -> [[Int]] {
       guard let root = root else { return []}
       var queue = Array<Node?>()
       var res = Array<Array<Int>>()
        queue = [root]
       while !queue.isEmpty {
           let levelCount = queue.count
           var temp = Array<Int>()
           for _ in 0..<levelCount {
            let node = queue.removeFirst()
            temp.append(node!.val)
            node!.children.forEach { queue.append($0) }
           }
           res.append(temp)
       }
       return res
    }
}

8.翻转二叉树

class Solution {
    func invertTree(_ root: TreeNode?) -> TreeNode? {
        if root == nil { return nil}
        let left = invertTree(root?.left)
        let right = invertTree(root?.right)
        root?.left = right
        root?.right = left
        return root
    }
}

9.验证二叉搜索树

class Solution {
        func isValidBST(_ root: TreeNode?) -> Bool {
        var res = true
        var lower = Int64.min
        backTrack(root: root, lower: &lower, res: &res)
        return res
    }
    func backTrack(root: TreeNode?, lower: inout Int64, res: inout Bool) {
        // 左根右
        if root == nil {
            return }
        backTrack(root: root?.left, lower: &lower, res: &res)
        if lower >= root!.val {
            res = false
        }
        lower = Int64(root!.val)
        backTrack(root: root?.right, lower: &lower, res: &res)
    }

}

10.二叉树的最大深度

class Solution {
        func maxDepth(_ root: TreeNode?) -> Int {
        if root == nil { return 0 }
        let maxLeft = maxDepth(root?.left)
        let maxRight = maxDepth(root?.right)
        return max(maxLeft, maxRight) + 1
    }
}

11.二叉树的最小深度

class Solution {
    func minDepth(_ root: TreeNode?) -> Int {
        guard let root = root else {
            return 0
        }
        var minLevel = 0
        var queue = [root]
        while !queue.isEmpty {
            minLevel += 1
            for _ in 0..<queue.count {
                let currentNode = queue.removeFirst()
                if currentNode.left == nil && currentNode.right == nil {
                    return minLevel
                }
                if let right = currentNode.right {
                    queue.append(right)
                }
                if let left = currentNode.left {
                    queue.append(left)
                }
            }
        }
        return minLevel
    }
}

12.二叉树的序列化与反序列化

class Codec {
    func serialize(_ root: TreeNode?) -> String {
        guard let nonNilRoot = root else {
            return ""
        }
        return BFS(root: nonNilRoot)
    }
    func deserialize(_ data: String) -> TreeNode? {
        if data == "" {return nil}
        let NodeValueArray = data.split(separator: ",")
        // 构造一个TreeNode数组
        var treeNodeArray = Array<TreeNode?>()
        for i in NodeValueArray {
            if i == "Null" {
                treeNodeArray.append(nil)
            } else {
                treeNodeArray.append(TreeNode(Int(i)!))
            }
        }
        let resRoot:TreeNode? = treeNodeArray.first!
        var queue = Array<TreeNode?>()
        queue = [resRoot]
        var i = 1
        while !queue.isEmpty {
            if let currentRoot = queue.removeFirst() {
                if let left = treeNodeArray[i] {
                    currentRoot.left = left
                    queue.append(left)
                }
                if let right = treeNodeArray[i + 1] {
                    currentRoot.right = right
                    queue.append(right)
                }
                i += 2
            }
        }
        return resRoot
    }
    func BFS(root: TreeNode?) -> String {
        guard let root = root else {
            return ""
        }
        var queue: [TreeNode?] = [root]
        var res = "\(root.val),"
        while !queue.isEmpty {
            for _ in 0..<queue.count {
                let currentNode = queue.removeFirst()
                if let left = currentNode?.left {
                    queue.append(left)
                    res += "\(left.val),"
                } else {
                    res += "Null,"
                }
                if let right = currentNode?.right {
                    queue.append(right)
                    res += "\(right.val),"
                } else {
                    res += "Null,"
                }
                
            }
        }
        res.removeLast()
        return res
    }
}
// Your Codec object will be instantiated and called as such:
// var ser = Codec()
// var deser = Codec()
// deser.deserialize(ser.serialize(root))

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

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

14.从前序与中序遍历序列构造二叉树

class Solution {
func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
        var mPreorder = preorder
        var mInorder = inorder
        return backTrack(preorderNodeArray: &mPreorder, inorderNodeArray: &mInorder)
    }
    func backTrack(preorderNodeArray: inout [Int], inorderNodeArray: inout [Int]) -> TreeNode? {
        guard let rootVal = preorderNodeArray.first else {
            return nil
        }
        let root = TreeNode(rootVal)
        if preorderNodeArray.count == 1 {
            return root
        }
        var inorderLeftTree = Array(inorderNodeArray[0..<inorderNodeArray.firstIndex(of: root.val)!])
        var inorderRighTree = Array(inorderNodeArray[inorderNodeArray.firstIndex(of: root.val)! + 1..<inorderNodeArray.count])
        var preorderLeftTree = Array(preorderNodeArray[1..<inorderLeftTree.count + 1])
        var preorderRightTree = Array(preorderNodeArray[(inorderLeftTree.count + 1)..<preorderNodeArray.count])
        root.left = backTrack(preorderNodeArray: &preorderLeftTree, inorderNodeArray: &inorderLeftTree)
        root.right = backTrack(preorderNodeArray: &preorderRightTree, inorderNodeArray: &inorderRighTree)
        return root
    }
}

递归

9.括号生成

class Solution {
func generateParenthesis(_ n: Int) -> [String] {
        var res = Array<String>()
        backTrack(n: n, left: 0, right: 0, res: &res, cur: "")
        return res
    }
    func backTrack(n: Int, left: Int, right: Int, res: inout Array<String>, cur: String) {
        // terminator
        if cur.count == n * 2 {
            // process result
            res.append(cur)
            return
        }
        if left < n {
            backTrack(n: n, left: left + 1, right: right, res: &res, cur: cur + "(")
        }
        if right < left {
            backTrack(n: n, left: left, right: right + 1, res: &res, cur: cur + ")")
        }
    }
}

15.组合

class Solution {
    func combine(_ n: Int, _ k: Int) -> [[Int]] {
        var res = Array<Array<Int>>()
        var cur = Array<Int>()
        backTracking(n: n, k: k, res: &res, cur: &cur, curNum: 1)
        return res
    }
    func backTracking(n: Int, k: Int, res: inout Array<Array<Int>>, cur: inout Array<Int>, curNum: Int) {
        if cur.count + (n - curNum + 1) < k {
            return
        }
        if cur.count == k {
            res.append(cur)
            return
        }
        cur.append(curNum)
        backTracking(n: n, k: k, res: &res, cur: &cur, curNum: curNum + 1)
        cur.removeLast()
        backTracking(n: n, k: k, res: &res, cur: &cur, curNum: curNum + 1)
    }

}

16.全排列

class Solution {
func permute(_ nums: [Int]) -> [[Int]] {
        var path = Array<Int>()
        var res = Array<Array<Int>>()
        var used = Array(repeating: false, count: nums.count)
        dfs(path: &path, res: &res, used: &used, nums: nums, depth: 0)
        return res
    }
    func dfs(path: inout Array<Int>, res: inout Array<Array<Int>>, used: inout Array<Bool>, nums: Array<Int>, depth: Int) {
        if depth == nums.count {
            res.append(path)
            return
        }
        for i in 0..<nums.count {
            if used[i] { continue }
            path.append(nums[i])
            used[i] = true
            dfs(path: &path, res: &res, used: &used, nums: nums, depth: depth + 1)
            path.removeLast()
            used[i] = false
        }
    }
}

17.全排列 II

class Solution {
    func permuteUnique(_ nums: [Int]) -> [[Int]] {
        var res = Array<Array<Int>>()
        var path = Array<Int>()
        var used = Array(repeating: false, count: nums.count)
        dfs(nums: nums.sorted(by: <), res: &res, path: &path, level: 0, used: &used)
        return res
    }
    func dfs(nums: [Int], res: inout [[Int]], path: inout [Int], level: Int, used: inout [Bool]) {
        if level == nums.count {
            res.append(path)
            return
        }
        for i in 0..<nums.count {
            // !used[i - 1] 保证在填【i】这个数的时候重复数字只会被填入一次,只要最左边的。所以如果两个数字相同，并且前一个还没有用过，那么是不符合规则（用最左侧）的。要continue跳过
            if used[i] == true || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue
            }
            used[i] = true
            path.append(nums[i])
            dfs(nums: nums, res: &res, path: &path, level: level + 1, used: &used)
            path.removeLast()
            used[i] = false
        }
    }
}