《算法通关之路》chapter17一些通用解题模板

《算法通关之路》学习笔记，记录一下自己的刷题过程，详细的内容请大家购买作者的书籍查阅。

1 二分法

1.1 普通二分法

# 查找nums数组中元素值为target的下标。如果不存在，则返回-1def bs(nums: list[int], target: int) -> int :l, h = 0, len(nums) - 1while l <= h:mid = l + (h - l) // 2if nums[mid] == target:return midelif nums[mid] < target:l = mid + 1else:h = mid - 1return -1nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
nums[bs(nums, 8)]

8

1.2 二分法变种

有些二分法类型的题目，在二分时无法直接判断中间元素是否为目标元素，这类问题被称作二分法变种问题。

例如：在有序数组里面查找第1个大于或等于5的元素，每次判断中间元素时，无法直接断定这个元素是否是第1个大于或等于5的元素，它可能是第2个或第3个大于或等于5的元素。

二分法变种问题大致分为两种情况：

• 查找第一个满足条件的元素
• 查找最后一个满足条件的元素

此外需要注意边界问题，这是二分法变种问题最容易出错的地方

# 查找第1个大于等于x的元素
# 左边界更新为l = mid + 1，不会产生死循环，当剩下1个元素时跳出即可def bs(nums: list[int], target: int) -> int :l, h = 0, len(nums) - 1while l <= h:mid = l + (h - l) // 2if l == h: # 边界条件breakelif nums[mid] < target:l = mid + 1else:h = midreturn lnums = [1, 2, 3, 4, 5, 6, 7, 9, 10]
nums[bs(nums, 8)]

9

# 查找最后1个小于等于x的元素
# 左边界更新为l = mid，会产生死循环，当剩下2个元素时跳出即可def bs(nums: list[int], target: int) -> int :l, h = 0, len(nums) - 1while l <= h:mid = l + (h - l) // 2if l == h or l + 1 == h: # 边界条件breakelif nums[mid] <= target:l = midelse:h = mid - 1return nums[h] if nums[h] <= target else nums[l]nums = [1, 2, 3, 4, 5, 6, 7, 8, 10, 11]
nums[bs(nums, 8)]

10

2 回溯法

回溯法的本质是回溯思想，通常使用递归实现。
递归的实现需要考虑3个方面：搜索的设计、递归的状态及递归的结束条件。

搜索的设计
对求解空间进行划分，让每一层递归都去尝试搜索一部分解空间，直至搜索完所有可能的解空间。

递归的状态
状态是用来区分不同递归的，一般来说，我们至少携带一种状态-当前位置idx，它用于找到当前可以继续前进的搜索空间，以此进入下一层递归。

递归的结束状态
通常包括两个方面：找到可行解，提前结束搜索；搜索完毕，已经没有搜索的解空间。

# ------
ans = []
target = 0
n = 0
nums = []
error = 0
visited = set()
# ------# idx表示当前位置，cur表示当前路径的某个信息，path表示路径
def dfs(idx, cur, path):# -------------结束条件# 1 找到解if cur == target:ans.append(path.copy())return# 2 搜索完毕if idx == n:return# --------------------# 考虑可能的解，进入下一层递归for num in nums:if num == error or num in visited:continue# 更新状态visited.add(num)dfs(idx + 1, cur + num, path + [num])# 恢复状态visited.remove(num)

3 并查集

使用parent数组记录每个节点的父节点，在初始情况下每个节点的父结点为本身，并使用rank记录每个节点为根的树的权值（树的节点数）。

• find§：当parent[p]不为p时，表示存在非本身的父节点，此时让p等于parent[p]，即向上寻找祖先节点，不断寻找祖先节点，不断重复这个过程直到parnet[p]等于p。
• union(p, q)：通过find(p,q)找到p和q的共同祖先节点，然后将权值小的祖先节点树合并到较高的树中。理论证明，这种算法能够保证合并后的树高度为O(logn)。

可以使用find§ == find(q)来判断两个节点是否属于同一个祖先。

class UnionFind:'''加权快速合并'''def __init__(self, n: int) -> None:self.parent = [i for i in range(n)] # 每个节点的父节点self.rank = [0 for _ in range(n)] # 以该节点为根的树权值（树的节点数）self.cnt = n # 连通区域数量def find(self, p: int) -> int: while p != self.parent[p]:p = self.parent[p]return pdef union(self, p: int, q: int) -> None: # 按秩合并root_p, root_q = self.find(p), self.find(q)if root_p == root_q:returnif self.rank[root_p] > self.rank[root_q]:self.parent[root_q] = root_pelif self.rank[root_p] < self.rank[root_q]:self.parent[root_p] = root_qelse:self.parent[root_q] = root_pself.rank[root_p] += 1self.cnt -= 1

class UnionFind:'''路径压缩加权快速合并'''def __init__(self, n: int) -> None:self.parent = [i for i in range(n)] # 每个节点的父节点self.rank = [0 for _ in range(n)] # 以该节点为根的树权值（树的节点数）self.cnt = n # 连通区域数量def find(self, p: int) -> int:  # 路径压缩if p != self.parent[p]:self.parent[p] = self.find(self.parent[p])return self.parent[p]def union(self, p: int, q: int) -> None: # # 按秩合并root_p, root_q = self.find(p), self.find(q)if root_p == root_q:returnif self.rank[root_p] > self.rank[root_q]:self.parent[root_q] = root_pelif self.rank[root_p] < self.rank[root_q]:self.parent[root_p] = root_qelse:self.parent[root_q] = root_pself.rank[root_p] += 1self.cnt -= 1

4 BFS

基于队列的广度优先遍历，将起始节点放入队列中，循环遍历队列中的节点。扩展节点相邻的有效节点，并将其放入队列中。

from collections import dequegrid = [0 * 5 for _ in range(5)] # n * m的矩阵def bfs(grid):m, n = len(grid), len(grid[0])directions = [(0, 1), (0, -1), (-1, 0), (1, 0)] # 扩展方向visited = [[False] * n for _ in range(m)] # 记录节点是否被访问queue = deque()level = 0 # 深度queue.append((0, 0))visited[0][0] = Truewhile len(queue) > 0:sz = len(queue)for _ in range(sz):top = queue.popleft()x, y = top# 扩展节点for d in directions:next_x, next_y = x + d[0], y + d[1]# 判断相邻节点是否有效if next_x < 0 or next_x >= m or next_y < 0 or next_y >= n:continuequeue.append((next_x, next_y))visited[next_x][next_y] = Truelevel += 1return level

5 滑动窗口

借助双指针表示窗口的左边界和右边界，并非根据题目要求不断移动指针。

根据窗口大小是否固定，以及最优解为最大或最小窗口，可以将滑动窗口分为3种类型。

5.1 窗口大小固定，最优解与窗口大小无关

nums = [] # 题目给定数组
cnt = {x : 0 for x in nums} #字典记录出现次数
ans = 0 # 答案
init_len = 0 # 窗口大小def check(cnt): # 题目所述条件passdef get(left, right): # 题目要求的答案pass# 初始化大小为init_len的窗口
for i in range(init_len):num = nums[i]cnt[num] += 1left, right = 0, init_len# 检查是否满足题目要求
if check(cnt):ans = get(left, right)while right < len(nums):num, num2 = nums[left], nums[right]cnt[num] -= 1cnt[num2] += 1# 检查是否满足题目要求if check(cnt):# 优化答案ans = max(ans, get(left, right))left += 1right += 1

5.2 窗口大小不固定，最优解为最小窗口

初始化大小为0的滑动窗口；然后循环移动窗口直到抵达边界，每次右指针right向右移动一步，并检查窗口是否满足条件，如果是，则循环向右移动左指针left，每移动一步，不断尝试缩小窗口直到窗口不满足条件，更新最优解。

left, right = 0, 0
nums = [] # 题目给定数组
cnt = {x : 0 for x in nums} #字典记录出现次数
ans = len(nums) # 初始值while right < len(nums):cnt[nums[right]] += 1# 满足题目要求，尽可能缩小窗口while left <= right and check(cnt):# 优化答案ans = min(ans, right - left + 1)# 尝试缩小窗口cnt[nums[left]] -= 1left += 1right += 1

5.3 窗口大小不固定，最优解为最大窗口

初始化大小为0的滑动窗口；然后循环移动窗口直到抵达边界，每次右指针right向右移动一步，并检查窗口是否不满足条件，如果是，则循环向右移动左指针left，每移动一步直到满足条件，更新最优解。

left, right = 0, 0
nums = [] # 题目给定数组
cnt = {x : 0 for x in nums} #字典记录出现次数
ans = 0 # 初始值while right < len(nums):cnt[nums[right]] += 1# 不满足题目要求，需要缩小窗口while not check(cnt):cnt[nums[left]] -= 1left += 1ans = max(ans, right - left + 1)right += 1

6 数学

6.1 判断素数

def isPrime(n: int) -> bool:if n <= 1:return Falsei = 2while i * i <= n:if n % i == 0:return Falsei += 1return TrueisPrime(121)

False

6.2 最大公约数

欧几里得算法： 两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。

def gcd(a: int, b: int) -> int:return a if b == 0 else gcd(b, a % b)

6.3 最小公倍数

两个数的乘积等于这两个数最大公约数和最小公倍数的乘积，最小公倍数 = 两数乘积 / 两数最大公约数

def lcm(a, int, b: int) -> int:return a * b // gcd(a, b)