算法小抄 | 第1章
其实在今年五六月份就发现了这个Github上很火的一个项目，但当时出于懒惰并没有仔细钻研
一直到上个月（2020.11），因为要准备CSP，所以才开始看这个算法指南
猛然发现，这个指南讲解的真的很人性化。就仿佛以一种向傻子（指我自己）阐述的口吻，来解释算法题和解题套路。
于是乎，这本《labuladong的算法小抄》刚出版两天，我便直接下单了。
作者labuladong仿佛是应届毕业生，就是比我大一届，秋招拿了十二个offer。orz🤕
在此做一些学习笔记，以此督促自己认真学习并加深理解。
由于本人比较熟悉python，所以笔记中的框架及具体代码都是基于python的。
动态规划套路
-
动态规划的三个关键
-
base case
-
DP table的定义
-
状态转移方程
-
看清了这三个之后，解决问题就如鱼得水了，直接结合例题来寻找感觉。
例题
假设现在要找的零钱为 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]
回溯法套路
- 关键思想：递归求解问题，每次尝试一种可能性，尝试到底之后再回溯
三个关键问题
- 路径：已经做出的选择
- 选择列表：下一步可以进行的选择
- 结束条件：要知道什么时候退出递归
回溯法的算法框架
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.append(路径)
return
for 选择 in 选择列表:
路径.做选择()
backtrack(路径, 选择列表)
路径.撤销选择()
全排列问题
假设我要求[1,2,3]的全排列，那么针对三个关键问题
- 路径：用一个数组来记录我已经选择了哪些数字
- 选择列表：既然是全排列，下一步能选择的数字就是[1,2,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的棋盘，需要在每一行放一个皇后，最后保证
- 每一列只有一个皇后
- 每根和对角线平行的斜线上只有一个皇后
回溯法三个关键
- 路径：就是记录我已经放了哪些皇后，一个二维数组来代表棋盘
- 选择列表：下一步能放的位置肯定是某一行的N个位置
- 结束条件：如果我现在的摆放已经无法满足上述条件，就直接退出递归；如果我把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
二叉树的最小高度
解决一个问题即可套上面的模板：
-
起点和终点分别是什么？
起点就是根节点，终点就是叶节点
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集合来去重是因为我们是一直向下遍历，二叉树向下遍历并不会有重复结点
关键问题理解
-
为什么BFS可以找到最短路径，DFS不能找到？
BFS可以找到最短路径是因为它所尝试的每一步都是这一步的所有可能，它借助队列，实现了一步一步齐头并进，每一次都是二叉树往下扩展一层。
DFS其实也可以找到最短路径，但是需要把二叉树的每一个树枝走到底，最后才能找到最短的记录。相比以行的扩展方式而言，这种操作会浪费不少时间。
-
DFS相比BFS而言有优势吗？
BFS虽然能找到最短路径，但是空间复杂度高，因为每次都是尝试的一层的全部可能性。
如果只是单纯需要找到路径，BFS的空间复杂度为O(N)，但是DFS的空间复杂度就是O(logN)。
一般在找最短路径的时候会使用到BFS，其他一般情况下都是用DFS(也可以说成是回溯法)
解开密码锁的最少次数
-
一道相对较难的BFS实践
有一个带有四个圆形拨轮的转盘锁，每个拨轮都有0-9共10个数字，每个拨轮都可以上下旋转，例如0→9，9→0
一开始的时候转盘初始为4个0，用字符串”0000”表示，现在有一个列表
deadends和一个字符串targetdeadends这个列表中会放一些死亡组合，要避免播出这个组合，返回播出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
双指针技巧套路框架
快慢指针可以实现
-
判断链表中是否有环
- 相当于追及问题，快指针每次走两步，慢指针每次走一步
- 如果快慢指针相遇，说明快指针超了慢指针一圈（超了一个环的长度）
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 -
已知链表中有环，找到环的起始位置
- 首先跟上文类似，先用追及问题的方式，找到两个指针第一次相遇的位置
- 此时慢指针走了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真的神奇！✨
-
寻找无环单链表的中点
快指针每次前进两步，慢指针每次前进一步
当快指针走到链表尽头的时候，慢指针就恰好在链表的中点了
如果链表长度为奇数，慢指针就是在正中间，如果链表长度为偶数，慢指针就是在中点偏右
def find_mid_node(head): fast, slow = head, head while fast and fast.next: fast = fast.next.next slow = slow.next return slow -
寻找单链表中的倒数第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