算法小抄 | 第1章


其实在今年五六月份就发现了这个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块钱需要的最少硬币数

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

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)

备忘录优化解法

  • 通过新建一个哈希表来记录已经求解过的子问题的答案,来减少重复的递归
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属于是自底向上求解

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

RecursionError: maximum recursion depth exceeded in comparison

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

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. 结束条件:要知道什么时候退出递归

回溯法的算法框架

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.append(路径)
        return
    
    for 选择 in 选择列表:
        路径.做选择()
        backtrack(路径, 选择列表)
        路径.撤销选择()

全排列问题

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

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

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

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同理,标记的是从左上↖到右下↘的平行线

代码实现

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算法框架

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

一般框架如下:

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,直接套模板(说是模板,其实就是把整个过程模拟出来)

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即可。

按照思路套模板即可。

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的前提是要知道终点的状态

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中,会从两边交换进行扩散,队列中的元素越多,扩散出来的新元素也就越多
    • 针对这一点,我们可以控制每次扩散的队列是元素较少的队列
    • 使得以尽可能小的空间代价,来扩散两个队列找到交点
while queue1 and queue2:
        if len(queue1) > len(queue2):
            queue1, queue2 = queue2, queue1

双指针技巧套路框架

快慢指针可以实现

  1. 判断链表中是否有环

    • 相当于追及问题,快指针每次走两步,慢指针每次走一步
    • 如果快慢指针相遇,说明快指针超了慢指针一圈(超了一个环的长度)
    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步也会到达环的起始位置
    • 此时,让慢指针回到起点,重新出发,快指针不动
      • 两者以同样的速度,每次前进一格出发
      • 两者相遇的位置就是环的起点
    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. 寻找无环单链表的中点

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

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

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

    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个结点了

    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