其实在今年五六月份就发现了这个Github上很火的一个项目，但当时出于懒惰并没有仔细钻研

labuladong/fucking-algorithm

一直到上个月（2020.11），因为要准备CSP，所以才开始看这个算法指南

猛然发现，这个指南讲解的真的很人性化。就仿佛以一种向傻子（指我自己）阐述的口吻，来解释算法题和解题套路。

于是乎，这本《labuladong的算法小抄》刚出版两天，我便直接下单了。

作者labuladong仿佛是应届毕业生，就是比我大一届，秋招拿了十二个offer。orz🤕

在此做一些学习笔记，以此督促自己认真学习并加深理解。

由于本人比较熟悉python，所以笔记中的框架及具体代码都是基于python的。

动态规划套路

  • 动态规划的三个关键

    1. base case

    2. DP table的定义

    3. 状态转移方程

看清了这三个之后，解决问题就如鱼得水了，直接结合例题来寻找感觉。

例题

假设现在要找的零钱为 amount = 11，硬币面值为coins = [1, 2, 5]，尝试找到所需硬币最少的方法

N叉树解法

把大问题分解成小问题

想要知道找11块钱最少需要多少个硬币，我只要知道

  • 找10块钱需要的最少硬币数
  • 找9块钱需要的最少硬币数
  • 找6块钱需要的最少硬币数

即可得出最后答案，那么我们按照这个思路来写递归

1
2
3
4
5
6
7
8
9
10
11
12
13
def count_coins(amount, coins):
    # base case
    if amount == 0:
        return 0
    elif amount < 0:
        return -1
    res = float('inf')
    for coin in coins:
        # 找到子问题的所需硬币数
        tmp = count_coins(amount - coin, coins)
        if tmp >= 0:
            res = min(res, tmp)
    return res + 1

这样子去解决递归问题，会进行大量的重复计算（想象成一个N叉树）

  • 比如我想知道找11块最少需要多少硬币，自然会想知道10，9，6块的解
  • 但是我在知道10块的解之后，我又会诞生一个新的求解9块的子问题（11-2=9，10-1=9）

备忘录优化解法

  • 通过新建一个哈希表来记录已经求解过的子问题的答案，来减少重复的递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def count_coins(amount, coins, memo):
    if amount in memo:
        # memo是一个备忘录，用来记录已经计算过的最优解
        # memo[amout] = k，对应找amount元所需花的最少的硬币数
        return memo[amount]
    # base case
    if amount == 0:
        return 0
    elif amount < 0:
        return -1
    res = float('inf')
    for coin in coins:
        # 找到子问题的所需硬币数
        tmp = count_coins(amount - coin, coins, memo)
        if tmp >= 0:
            res = min(res, tmp)
    if res < float('inf'):
        memo[amount] = res+1
    return res + 1

DP Table解法

上面两种解法都是依靠递归，也就是自顶向上的解法，DP table属于是自底向上求解

因为不会用到递归，所以也不会报类似超过最大递归深度的错误

1
RecursionError: maximum recursion depth exceeded in comparison

我们用数组来模拟递归，从最简单的问题求解即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def count_coins(amount, coins):
    # 建立一个dptable去存储每种的最优解
    # base case
    dp = [float('inf') for i in range(amount + 1)]
    dp[0] = 0
    # 去更新所有可能的金额的解
    for i in range(0, amount + 1):
        tmp = dp[i]
        for coin in coins:
            if i - coin >= 0:
                tmp = min(tmp, dp[i - coin]+1)
        dp[i] = tmp

    return dp[amount]

回溯法套路

  • 关键思想：递归求解问题，每次尝试一种可能性，尝试到底之后再回溯

三个关键问题

  1. 路径：已经做出的选择
  2. 选择列表：下一步可以进行的选择
  3. 结束条件：要知道什么时候退出递归

回溯法的算法框架

1
2
3
4
5
6
7
8
9
10
result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.append(路径)
        return
    
    for 选择 in 选择列表:
        路径.做选择()
        backtrack(路径, 选择列表)
        路径.撤销选择()

全排列问题

假设我要求[1,2,3]的全排列，那么针对三个关键问题

  1. 路径：用一个数组来记录我已经选择了哪些数字
  2. 选择列表：既然是全排列，下一步能选择的数字就是[1,2,3]中我还没有加入路径的数字
  3. 结束条件：当我路径的长度为3时，我就知道已经实现了一种排列方式

依据这三点可以很容易写出一个递归函数

1
2
3
4
5
6
7
8
9
10
11
12
13
res = []
def backtrack(path, nums):
    global res
    # 结束条件是路径和我的数字个数一样
    if len(path) == len(nums):
        res.append([i for i in path])
        return
    for num in nums:
        # 所有可能的选择就是不在path中的数字
        if num not in path:
            path.append(num)
            backtrack(path, nums)
            path.pop()
  • 回溯法就是纯暴力穷举，复杂度一般都很高

N皇后问题

给定一个NxN的棋盘，需要在每一行放一个皇后，最后保证

  • 每一列只有一个皇后
  • 每根和对角线平行的斜线上只有一个皇后

回溯法三个关键

  1. 路径：就是记录我已经放了哪些皇后，一个二维数组来代表棋盘
  2. 选择列表：下一步能放的位置肯定是某一行的N个位置
  3. 结束条件：如果我现在的摆放已经无法满足上述条件，就直接退出递归；如果我把N行摆满了，且满足规则要求，说明这是一种合理的摆法。

思路

为了方便描述棋盘的状态，我们将棋盘设置成一个N*N的二维数组

某格为0表示这格不放皇后，若为1表示这格放置皇后

  • 逐行放置皇后棋子
  • 为了能快速确定选择列表，我们定义了三个集合
    • cols：已经放过的皇后的列数
    • left：和从左下↙到右上↗的对角线的平行线中哪些已经被放置了皇后
      • 我们用皇后所在位置的行数-列数来标明这是哪根线
      • 比如9*9的棋盘中，只要是行数-列数 = 8的都在中间的那根斜对角线上
    • right：和left同理，标记的是从左上↖到右下↘的平行线

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
res = []
N = 9
queens = [-1 for i in range(N)]
cols, left, right = set(), set(), set()

def backtrack(row):
    # row说明现在要放的皇后的所在行数
    if row == N:
        # 当前摆放符合规则,且已经摆了N个皇后
        board = [[0 for i in range(N)] for j in range(N)]
        # 生成最后的结果
        for i in range(row):
            board[i][queens[i]] = 1
        res.append(board)
        return
    for j in range(N):
        # 尝试当前行的不同位置摆放皇后
        # 只对可能的位置进行选择
        if j not in cols and row + j not in right and row - j not in left:
            queens[row] = j
            cols.add(j)
            right.add(row + j)
            left.add(row - j)
            backtrack(row+1)
            left.remove(row - j)
            right.remove(row + j)
            cols.remove(j)

backtrack(0)

BFS算法框架

本质就是找起点到终点的最短路径。

一般框架如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def bfs(root, target):
    queue = []
    # queue是存储的是当前要遍历的这层的结点
    queue.append(root)
    # visited用来存储已经遍历过的结点，避免重复
    visited = set()
    step = 0
    while queue:
        size = len(queue)
        for i in range(size):
            # 每次出队一个结点
            node = queue.pop(0)
            # 如果这个结点是终点结点，就直接返回走的步数
            if node == target:
                return step
            # 当前结点不是终点，就继续向四周扩散
            for j in node.adj():
                if j not in visited:
                    queue.append(j)
        # 每次遍历完一层结点，步数+1
        step += 1

二叉树的最小高度

解决一个问题即可套上面的模板：

  1. 起点和终点分别是什么？

    起点就是根节点，终点就是叶节点

OK，直接套模板（说是模板，其实就是把整个过程模拟出来）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def bfs(root):
    queue = [root]
    step = 1
    while queue:
        size = len(queue)
        for i in range(size):
            # 从队列头部取出一个结点
            node = queue.pop(0)
            if not node.left and not node.right:
                # 左右子节点均为空说明当前为叶节点
                return step
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        step += 1

理解了队列，二叉树和BFS思路之后，在脑子里边模拟边写即可

这里不需要visited集合来去重是因为我们是一直向下遍历，二叉树向下遍历并不会有重复结点

关键问题理解

  1. 为什么BFS可以找到最短路径，DFS不能找到？

    BFS可以找到最短路径是因为它所尝试的每一步都是这一步的所有可能，它借助队列，实现了一步一步齐头并进，每一次都是二叉树往下扩展一层。

    DFS其实也可以找到最短路径，但是需要把二叉树的每一个树枝走到底，最后才能找到最短的记录。相比以行的扩展方式而言，这种操作会浪费不少时间。

  2. DFS相比BFS而言有优势吗？

    BFS虽然能找到最短路径，但是空间复杂度高，因为每次都是尝试的一层的全部可能性。

    如果只是单纯需要找到路径，BFS的空间复杂度为O(N)，但是DFS的空间复杂度就是O(logN)。

    一般在找最短路径的时候会使用到BFS，其他一般情况下都是用DFS(也可以说成是回溯法)

解开密码锁的最少次数

  • 一道相对较难的BFS实践

    有一个带有四个圆形拨轮的转盘锁，每个拨轮都有0-9共10个数字，每个拨轮都可以上下旋转，例如0→9，9→0

    一开始的时候转盘初始为4个0，用字符串"0000"表示，现在有一个列表deadends和一个字符串target

    deadends这个列表中会放一些死亡组合，要避免播出这个组合，返回播出target的最少次数。

    当然也会有无法播出的情况，返回-1即可。

按照思路套模板即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def bfs(deadends, target):
    queue = []
    queue.append("0000")
    step = 0
    visited = set()
    while queue:
        size = len(queue)
        for i in range(size):
            node = queue.pop(0)
            if node in deadends:
                # 当前为死亡状态，则跳过该路径
                continue
            if node == target:
                # 当前为目标状态，返回操作数
                return step
            # 尝试不同可能性
            for j in range(4):
                # 一共有四个位置可以转
                cur = int(node[j])
                for k in [cur - 1, cur + 1]:
                    if k < 0: k = 9
                    if k > 9: k = 0
                    tmp = list(node)
                    tmp[j] = str(k)
                    code = "".join(tmp)
                    if code not in visited:
                        queue.append(code)
                        visited.add(code)
        step += 1
    return -1
  • 看起来很简单，但是我们需要更深入地研究。

传统的BFS（也就是我上面的这个递归函数）只是单纯地自顶向下求解，事实上，我们可以使用双向BFS来优化整体的过程。

双向BFS会从起点和终点两边开始扩散，只需要遍历半棵树就能找到交集。

要注意，使用双向BFS的前提是要知道终点的状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def bfs(deadends, target):
    queue1, queue2 = [], []
    queue1.append("0000")
    queue2.append(target)
    step = 0
    visited = set()
    while queue1 and queue2:
        # 用states数组去存储当前扩散出来的状态
        states = []
        for node in queue1:
            # 扩散queue1
            if node in deadends:
                # 当前为死亡状态，则跳过该路径
                continue
            if node in queue2:
                # 当前为目标状态，返回操作数
                return step
            visited.add(node)
            # 尝试不同可能性
            for j in range(4):
                # 一共有四个位置可以转
                cur = int(node[j])
                for k in [cur - 1, cur + 1]:
                    # 每个位置可以向上拨，也可以向下拨
                    if k < 0: k = 9
                    if k > 9: k = 0
                    tmp = list(node)
                    tmp[j] = str(k)
                    code = "".join(tmp)
                    if code not in visited:
                        states.append(code)
        step += 1
        queue1 = queue2
        # 交换两个队列，实现交替扩散
        queue2 = states
    return -1
print(bfs(["0123"], "0238"))
  • 针对双向BFS的优化
    • 双向BFS中，会从两边交换进行扩散，队列中的元素越多，扩散出来的新元素也就越多
    • 针对这一点，我们可以控制每次扩散的队列是元素较少的队列
    • 使得以尽可能小的空间代价，来扩散两个队列找到交点
1
2
3
while queue1 and queue2:
        if len(queue1) > len(queue2):
            queue1, queue2 = queue2, queue1

双指针技巧套路框架

快慢指针可以实现

  1. 判断链表中是否有环

    • 相当于追及问题，快指针每次走两步，慢指针每次走一步
    • 如果快慢指针相遇，说明快指针超了慢指针一圈（超了一个环的长度）
    1
    2
    3
    4
    5
    6
    7
    8
    def has_cycle(head):
        fast, slow = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True
        return False

  2. 已知链表中有环，找到环的起始位置

    • 首先跟上文类似，先用追及问题的方式，找到两个指针第一次相遇的位置
    • 此时慢指针走了k步，快指针走了2k步
      • 假设两者的相遇点和环的起点距离为m
      • 那么环的起点和头节点head的距离就是k-m
      • 也就是说，如果从头节点开始走，走k-m步就会到达环的起始位置
      • 巧的是，如果从当前相遇的位置出发，走k-m步也会到达环的起始位置
    • 此时，让慢指针回到起点，重新出发，快指针不动
      • 两者以同样的速度，每次前进一格出发
      • 两者相遇的位置就是环的起点
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    def has_cycle(head):
        fast, slow = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                # 找到两者相遇的位置
                break
        slow = head
        while slow != fast:
            # 找到两者第二次相遇的位置
            fast = fast.next
            slow = slow.next
        return slow

    真的神奇！✨

  3. 寻找无环单链表的中点

    快指针每次前进两步，慢指针每次前进一步

    当快指针走到链表尽头的时候，慢指针就恰好在链表的中点了

    如果链表长度为奇数，慢指针就是在正中间，如果链表长度为偶数，慢指针就是在中点偏右

    1
    2
    3
    4
    5
    6
    def find_mid_node(head):
        fast, slow = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        return slow

  4. 寻找单链表中的倒数第k个结点

    让快指针先前进k步，然后慢指针从head出发，两个指针同时每次前进一格

    快指针走到底，慢指针就指向倒数第k个结点了

    1
    2
    3
    4
    5
    6
    7
    8
    def find_kth_node(head, k):
        fast, slow = head, head
        for i in range(k):
            fast = fast.next
        while fast:
            fast = fast.next
            slow = slow.next
        return slow