《算法通關(guān)之路》學習筆記，記錄一下自己的刷題過程，詳細的內(nèi)容請大家購買作者的書籍查閱。

1 二分法

1.1 普通二分法

# 查找nums數(shù)組中元素值為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 二分法變種

有些二分法類型的題目，在二分時無法直接判斷中間元素是否為目標元素，這類問題被稱作二分法變種問題。

例如：在有序數(shù)組里面查找第1個大于或等于5的元素，每次判斷中間元素時，無法直接斷定這個元素是否是第1個大于或等于5的元素，它可能是第2個或第3個大于或等于5的元素。

二分法變種問題大致分為兩種情況：

• 查找第一個滿足條件的元素
• 查找最后一個滿足條件的元素

此外需要注意邊界問題，這是二分法變種問題最容易出錯的地方

# 查找第1個大于等于x的元素
# 左邊界更新為l = mid + 1，不會產(chǎn)生死循環(huán)，當剩下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，會產(chǎn)生死循環(huán)，當剩下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 回溯法

回溯法的本質(zhì)是回溯思想，通常使用遞歸實現(xiàn)。
遞歸的實現(xiàn)需要考慮3個方面：搜索的設(shè)計、遞歸的狀態(tài)及遞歸的結(jié)束條件。

搜索的設(shè)計
對求解空間進行劃分，讓每一層遞歸都去嘗試搜索一部分解空間，直至搜索完所有可能的解空間。

遞歸的狀態(tài)
狀態(tài)是用來區(qū)分不同遞歸的，一般來說，我們至少攜帶一種狀態(tài)-當前位置idx，它用于找到當前可以繼續(xù)前進的搜索空間，以此進入下一層遞歸。

遞歸的結(jié)束狀態(tài)
通常包括兩個方面：找到可行解，提前結(jié)束搜索；搜索完畢，已經(jīng)沒有搜索的解空間。

# ------
ans = []
target = 0
n = 0
nums = []
error = 0
visited = set()
# ------# idx表示當前位置，cur表示當前路徑的某個信息，path表示路徑
def dfs(idx, cur, path):# -------------結(jié)束條件# 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# 更新狀態(tài)visited.add(num)dfs(idx + 1, cur + num, path + [num])# 恢復狀態(tài)visited.remove(num)

3 并查集

使用parent數(shù)組記錄每個節(jié)點的父節(jié)點，在初始情況下每個節(jié)點的父結(jié)點為本身，并使用rank記錄每個節(jié)點為根的樹的權(quán)值（樹的節(jié)點數(shù)）。

• find§：當parent[p]不為p時，表示存在非本身的父節(jié)點，此時讓p等于parent[p]，即向上尋找祖先節(jié)點，不斷尋找祖先節(jié)點，不斷重復這個過程直到parnet[p]等于p。
• union(p, q)：通過find(p,q)找到p和q的共同祖先節(jié)點，然后將權(quán)值小的祖先節(jié)點樹合并到較高的樹中。理論證明，這種算法能夠保證合并后的樹高度為O(logn)。

可以使用find§ == find(q)來判斷兩個節(jié)點是否屬于同一個祖先。

class UnionFind:'''加權(quán)快速合并'''def __init__(self, n: int) -> None:self.parent = [i for i in range(n)] # 每個節(jié)點的父節(jié)點self.rank = [0 for _ in range(n)] # 以該節(jié)點為根的樹權(quán)值（樹的節(jié)點數(shù)）self.cnt = n # 連通區(qū)域數(shù)量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:'''路徑壓縮加權(quán)快速合并'''def __init__(self, n: int) -> None:self.parent = [i for i in range(n)] # 每個節(jié)點的父節(jié)點self.rank = [0 for _ in range(n)] # 以該節(jié)點為根的樹權(quán)值（樹的節(jié)點數(shù)）self.cnt = n # 連通區(qū)域數(shù)量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

基于隊列的廣度優(yōu)先遍歷，將起始節(jié)點放入隊列中，循環(huán)遍歷隊列中的節(jié)點。擴展節(jié)點相鄰的有效節(jié)點，并將其放入隊列中。

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)] # 記錄節(jié)點是否被訪問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# 擴展節(jié)點for d in directions:next_x, next_y = x + d[0], y + d[1]# 判斷相鄰節(jié)點是否有效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 滑動窗口

借助雙指針表示窗口的左邊界和右邊界，并非根據(jù)題目要求不斷移動指針。

根據(jù)窗口大小是否固定，以及最優(yōu)解為最大或最小窗口，可以將滑動窗口分為3種類型。

5.1 窗口大小固定，最優(yōu)解與窗口大小無關(guān)

nums = [] # 題目給定數(shù)組
cnt = {x : 0 for x in nums} #字典記錄出現(xiàn)次數(shù)
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):# 優(yōu)化答案ans = max(ans, get(left, right))left += 1right += 1

5.2 窗口大小不固定，最優(yōu)解為最小窗口

初始化大小為0的滑動窗口；然后循環(huán)移動窗口直到抵達邊界，每次右指針right向右移動一步，并檢查窗口是否滿足條件，如果是，則循環(huán)向右移動左指針left，每移動一步，不斷嘗試縮小窗口直到窗口不滿足條件，更新最優(yōu)解。

left, right = 0, 0
nums = [] # 題目給定數(shù)組
cnt = {x : 0 for x in nums} #字典記錄出現(xiàn)次數(shù)
ans = len(nums) # 初始值while right < len(nums):cnt[nums[right]] += 1# 滿足題目要求，盡可能縮小窗口while left <= right and check(cnt):# 優(yōu)化答案ans = min(ans, right - left + 1)# 嘗試縮小窗口cnt[nums[left]] -= 1left += 1right += 1

5.3 窗口大小不固定，最優(yōu)解為最大窗口

初始化大小為0的滑動窗口；然后循環(huán)移動窗口直到抵達邊界，每次右指針right向右移動一步，并檢查窗口是否不滿足條件，如果是，則循環(huán)向右移動左指針left，每移動一步直到滿足條件，更新最優(yōu)解。

left, right = 0, 0
nums = [] # 題目給定數(shù)組
cnt = {x : 0 for x in nums} #字典記錄出現(xiàn)次數(shù)
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 數(shù)學

6.1 判斷素數(shù)

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 最大公約數(shù)

歐幾里得算法： 兩個整數(shù)的最大公約數(shù)等于其中較小的那個數(shù)和兩數(shù)相除余數(shù)的最大公約數(shù)。

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

6.3 最小公倍數(shù)

兩個數(shù)的乘積等于這兩個數(shù)最大公約數(shù)和最小公倍數(shù)的乘積，最小公倍數(shù) = 兩數(shù)乘積 / 兩數(shù)最大公約數(shù)

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