回溯算法

「所有可能的結果」，而不是「結果的個數」，一般情況下，我們就知道需要暴力搜索所有的可行解了，可以用「回溯法」。

回溯算法關鍵在于:不合適就退回上一步。在回溯算法中，遞歸用于深入到所有可能的分支，而迭代（通常在遞歸函數內部的循環中體現）用于探索當前層級的所有可能選項。

組合問題

39. 組合總和 - 力扣（LeetCode）

給你一個?無重復元素?的整數數組?candidates?和一個目標整數?target?，找出?candidates?中可以使數字和為目標數?target?的 所有?不同組合?，并以列表形式返回。你可以按?任意順序?返回這些組合。

1.路徑2.求和3.判斷

?回溯算法：

在循環中回溯前有改變操作，調用回溯函數判斷是否繼續回溯，如果結束當前循環的回溯，在回溯后進行操作。

from typing import Listclass Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:res = []def backtrack(candidates, path, target, start):if sum(path) == target:res.append(path[:])returnif sum(path) > target:returnfor i in range(start, len(candidates)):path.append(candidates[i])backtrack(candidates, path, target, i)path.pop()backtrack(candidates, [], target, 0)return res# 實例化Solution類
solution = Solution()# 定義候選數字列表和目標值
candidates = [2, 3, 6, 7]
target = 7# 調用combinationSum方法并打印結果
combinations = solution.combinationSum(candidates, target)
print(combinations)

17. 電話號碼的字母組合 - 力扣（LeetCode）

class Solution:def letterCombinations(self, digits: str) -> List[str]:#數字對應的英文字母列表word_list = ["0", "0", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]#如果是空字符串直接返回空列表if digits == "":return []#保存結果列表result = []#輸入的digits的長度，作為回溯函數返回的判斷條件lenth = len(digits)#回溯函數（path當前路徑，默認為""）def back_track(digits, index, path):#如果目前path的長度和digits的長度相等，說明已經遍歷完一趟，返回結果列表if len(path) == lenth:#加入result列表result.append(path)#返回return#遍歷當前索引的數字對應的英文列表for word in word_list[int(digits[index])]:#路徑加上當前字母path = path + word#遞歸下一個數字對應的英文列表back_track(digits, index + 1, path)#撤銷當前字母path = path[:-1]back_track(digits, 0, "")return result

分割問題

131. 分割回文串 - 力扣（LeetCode）

class Solution(object):def partition(self, s):# 判斷字符串是否為回文self.is_palindrome = lambda s: s == s[::-1]# 初始化結果列表，用于存儲所有可能的分割方式result = []# 從空路徑開始回溯self.backtrack(s, result, [])return resultdef backtrack(self, s, result, path):# 如果s為空，說明已經處理完所有字符，將當前路徑加入結果列表if not s:result.append(path)return# 遍歷字符串s，嘗試每一種可能的分割方式for i in range(1, len(s) + 1):# 截取當前子串substring = s[:i]# 如果當前子串是回文，則繼續遞歸處理剩余的字符串if self.is_palindrome(substring):# 將當前子串加入路徑，并遞歸處理剩余字符串self.backtrack(s[i:], result, path + [substring])# 實例化Solution類
solution = Solution()# 定義字符串
s = "aab"# 調用partition方法并打印結果
partitions = solution.partition(s)
print(partitions)

子集問題

78. 子集 - 力扣（LeetCode）

給你一個整數數組?nums?，數組中的元素?互不相同?。返回該數組所有可能的子集

start參數和i+1，指示了在遞歸過程中應該從數組的哪個位置開始考慮元素，以避免重復的組合。

每多一個數增加一次結果

from typing import Listclass Solution:def subsets(self, nums: List[int]) -> List[List[int]]:"""生成給定數字列表的所有可能子集。:param nums: 用于生成子集的整數列表。:return: 包含所有可能子集的列表。"""if not nums:return []res = []n = len(nums)# 定義遞歸輔助函數，用于回溯生成子集def backtrack(start: int, current_subset: List[int]):"""回溯輔助函數。:param start: 當前子集開始遍歷的索引。:param current_subset: 當前正在構建的子集。"""# 將當前子集的副本添加到結果列表中res.append(current_subset[:])# 遍歷剩余元素，嘗試將其加入到子集中for i in range(start, n):# 將當前元素加入到子集，并遞歸繼續構建子集backtrack(i + 1, current_subset + [nums[i]])# 從空子集開始回溯過程backtrack(0, [])return res# 示例用法：
solution = Solution()
print(solution.subsets([1, 2, 3]))

排列問題

46. 全排列 - 力扣（LeetCode）

from typing import Listclass Solution:def permute(self, nums: List[int]) -> List[List[int]]:def backtrack(start, end):# 所有數都填完了，將當前排列加入結果集if start == end:res.append(nums[:])for i in range(start, end):# 交換前綴，將第 i 個元素固定在第 start 位nums[start], nums[i] = nums[i], nums[start]# 遞歸填下一個數backtrack(start + 1, end)# 撤銷操作nums[start], nums[i] = nums[i], nums[start]res = []backtrack(0, len(nums))return res# 實例化并調用
solution = Solution()
nums = [1, 2, 3]
print(solution.permute(nums))

每循環完列表一次添加一次結果

棋盤問題

51. N 皇后 - 力扣（LeetCode）

class Solution:def solveNQueens(self, n: int) -> List[List[str]]:# 從上往下放棋子# 按照row從小到大放置皇后board = [['.'] * n for _ in range(n)]res = []# 表示board中小于row的那些行（row上面的那些行）已經放置皇后了# 這一步開始往第row行放皇后def backtrack(row):n = len(board)# 如果到最后一行了，則將結果添加到res里if row == n:tmp = [''.join(i) for i in board]res.append(tmp)returnfor col in range(n):if not self.isValid(board, row, col):continueboard[row][col] = 'Q'backtrack(row + 1)board[row][col] = '.'backtrack(0)return res # 查看是否可以在board[row][col]的位置放置皇后def isValid(self, board, row, col):n = len(board)# 查看上方是否有Qfor i in range(row):if board[i][col] == 'Q':return False# 查看右上方是否有Qfor i, j in zip(range(row - 1, -1, -1), range(col + 1, n, 1)):if board[i][j] == 'Q':return False# 查看左上方是否有Qfor i, j in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):if board[i][j] == 'Q':return Falsereturn True 作者：山鬼TJU

79. 單詞搜索 - 力扣（LeetCode）

class Solution(object):# 定義上下左右四個行走方向directs = [(0, 1), (0, -1), (1, 0), (-1, 0)]def exist(self, board, word):""":type board: List[List[str]]:type word: str:rtype: bool"""m = len(board)if m == 0:return Falsen = len(board[0])mark = [[0 for _ in range(n)] for _ in range(m)]for i in range(len(board)):for j in range(len(board[0])):if board[i][j] == word[0]:# 將該元素標記為已使用mark[i][j] = 1if self.backtrack(i, j, mark, board, word[1:]) == True:return Trueelse:# 回溯mark[i][j] = 0return Falsedef backtrack(self, i, j, mark, board, word):if len(word) == 0:return Truefor direct in self.directs:cur_i = i + direct[0]cur_j = j + direct[1]if cur_i >= 0 and cur_i < len(board) and cur_j >= 0 and cur_j < len(board[0]) and board[cur_i][cur_j] == word[0]:# 如果是已經使用過的元素，忽略if mark[cur_i][cur_j] == 1:continue# 將該元素標記為已使用mark[cur_i][cur_j] = 1if self.backtrack(cur_i, cur_j, mark, board, word[1:]) == True:return Trueelse:# 回溯mark[cur_i][cur_j] = 0return False

22. 括號生成 - 力扣（LeetCode）

可以插入?）?的前提是?(?的數量大于?）

class Solution(object):def generateParenthesis(self, n):""":type n: int:rtype: List[str]"""res = []self.dfs(res, n, n, '')return resdef dfs(self, res, left, right, path):if left == 0 and right == 0:res.append(path)returnif left > 0:self.dfs(res, left - 1, right, path + '(')if left < right:self.dfs(res, left, right - 1, path + ')')

貪心算法

例如，有一堆鈔票，你可以拿走十張，如果想達到最大的金額，你要怎么拿？

指定每次拿最大的，最終結果就是拿走最大數額的錢。

每次拿最大的就是局部最優，最后拿走最大數額的錢就是推出全局最優。

• 將問題分解為若干個子問題
• 找出適合的貪心策略
• 求解每一個子問題的最優解
• 將局部最優解堆疊成全局最優解

121. 買賣股票的最佳時機 - 力扣（LeetCode）

因為股票就買賣一次，那么貪心的想法很自然就是取最左最小值，取最右最大值，那么得到的差值就是最大利潤。

def max_profit(prices):if not prices:return 0max_profit = 0min_price = prices[0]for price in prices:# 更新到目前為止遇到的最小價格min_price = min(min_price, price)# 計算在當前價格賣出時的利潤，并更新最大利潤max_profit = max(max_profit, price - min_price)return max_profit# 示例
prices = [7, 1, 5, 3, 6, 4]
print(max_profit(prices))  # 輸出應為 5

?55. 跳躍游戲 - 力扣（LeetCode）

def can_jump(nums):# 最遠能到達的位置max_reach = 0# 遍歷數組for i, num in enumerate(nums):# 如果當前位置超過最遠能到達的位置，說明無法到達當前位置if i > max_reach:return False# 更新最遠能到達的位置max_reach = max(max_reach, i + num)# 如果最遠能到達的位置已經覆蓋了最后一個下標，則可以到達if max_reach >= len(nums) - 1:return Truereturn True# 示例
nums = [2, 3, 1, 1, 4]
print(can_jump(nums))  # 輸出應為 True

?45. 跳躍游戲 II - 力扣（LeetCode）

def min_jumps(nums):n = len(nums)# 如果數組只有一個元素，不需要跳躍if n <= 1:return 0# 當前跳躍能到達的最遠位置current_end = 0# 下一步跳躍能到達的最遠位置farthest = 0# 跳躍次數jumps = 0# 遍歷數組，但不包括最后一個元素，因為目標是在最后一個元素處停止for i in range(n - 1):# 更新最遠能到達的位置farthest = max(farthest, i + nums[i])# 如果到達了當前跳躍的邊界if i == current_end:# 增加跳躍次數jumps += 1# 更新當前跳躍的邊界current_end = farthest# 如果當前跳躍的邊界已經覆蓋了最后一個元素，則可以停止if current_end >= n - 1:breakreturn jumps# 示例
nums = [2, 3, 1, 1, 4]
print(min_jumps(nums))  # 輸出應為 2

?763. 劃分字母區間 - 力扣（LeetCode）

def partitionLabels(s):# 記錄每個字符最后出現的位置last = {c: i for i, c in enumerate(s)}ans = []start = end = 0# 遍歷字符串for i, c in enumerate(s):# 更新當前片段的結束位置end = max(end, last[c])# 如果當前位置是當前片段的結束位置if i == end:# 記錄當前片段的長度ans.append(end - start + 1)# 更新下一個片段的開始位置start = end + 1return ans# 示例
s = "ababcbacadefegdehijhklij"
print(partitionLabels(s))  # 輸出

哈希表

1. 兩數之和 - 力扣（LeetCode）

創建一個哈希表，對于每一個?x，我們首先查詢哈希表中是否存在?target - x，然后將?x?插入到哈希表中，即可保證不會讓?x?和自己匹配。

class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:hashtable = dict()for i, num in enumerate(nums):if target - num in hashtable:return [hashtable[target - num], i]hashtable[nums[i]] = ireturn []

?49. 字母異位詞分組 - 力扣（LeetCode）

class Solution:def groupAnagrams(self, strings: List[str]) -> List[List[str]]:mp = collections.defaultdict(list) # define a map from str to list of strfor string in strings:key = "".join(sorted(string))mp[key].append(string)return list(mp.values())

128. 最長連續序列 - 力扣（LeetCode）

class Solution:def longestConsecutive(self, nums: List[int]) -> int:ans = 0st = set(nums)  # 把 nums 轉成哈希集合for x in st:  # 遍歷哈希集合if x - 1 in st:continue# x 是序列的起點y = x + 1while y in st:  # 不斷查找下一個數是否在哈希集合中y += 1# 循環結束后，y-1 是最后一個在哈希集合中的數ans = max(ans, y - x)  # 從 x 到 y-1 一共 y-x 個數return ans作者：靈茶山艾府

560. 和為 K 的子數組 - 力扣（LeetCode）

前后綴分解+哈希表

前綴和指一個數組的某下標之前的所有數組元素的和（包含其自身）

from collections import defaultdictclass Solution:def subarraySum(self, nums: list, k: int) -> int:# 初始化計數器，用于記錄和為k的子數組的數量count = 0n = len(nums)# 使用defaultdict來存儲前綴和出現的次數，初始時前綴和為0出現1次preSums = defaultdict(int)preSums[0] = 1# 初始化前綴和為0presum = 0# 遍歷數組中的每個元素for i in range(n):# 更新當前的前綴和presum += nums[i]# 如果存在某個前綴和等于當前前綴和減去k，則說明存在一個子數組的和為k# defaultdict的特性使得當key不存在時返回0，所以這里不需要判斷key是否存在count += preSums[presum - k]# 將當前前綴和出現的次數加1preSums[presum] += 1# 返回和為k的子數組的數量return count

雙指針

283. 移動零 - 力扣（LeetCode）

快慢指針，當碰到0時i會比i0走的快

from typing import Listclass Solution:def moveZeroes(self, nums: List[int]) -> None:# 初始化一個指針i0，用于指向下一個非零元素應該放置的位置i0 = 0# 遍歷數組中的每個元素for i in range(len(nums)):# 如果當前元素不是0，則將其與i0指向的位置的元素交換if nums[i]:# 交換元素，將非零元素移動到i0指向的位置nums[i], nums[i0] = nums[i0], nums[i]# 移動i0指針到下一個位置i0 += 1# 注意：這個方法直接修改了輸入的數組，不需要返回值

11. 盛最多水的容器 - 力扣（LeetCode）

對撞指針兩個指針列表一邊一個向中間靠近，同時根據兩者的高度判斷兩個指針是否前進

class Solution:def maxArea(self, height: List[int]) -> int:ans = left = 0right = len(height) - 1while left < right:area = (right - left) * min(height[left], height[right])ans = max(ans, area)if height[left] < height[right]:# height[left] 與右邊的任意線段都無法組成一個比 ans 更大的面積left += 1else:# height[right] 與左邊的任意線段都無法組成一個比 ans 更大的面積right -= 1return ans

42. 接雨水 - 力扣（LeetCode）

對撞指針

from typing import Listclass Solution:def trap(self, height: List[int]) -> int:# 初始化答案變量、左指針、前綴最大高度、后綴最大高度ans = left = pre_max = suf_max = 0# 初始化右指針指向數組的最后一個元素right = len(height) - 1# 當左指針小于右指針時，繼續循環while left < right:# 更新當前左指針指向的柱子的前綴最大高度pre_max = max(pre_max, height[left])# 更新當前右指針指向的柱子的后綴最大高度suf_max = max(suf_max, height[right])# 如果左指針的前綴最大高度小于右指針的后綴最大高度if pre_max < suf_max:# 計算當前左指針位置可以捕獲的水量，并累加到答案中ans += pre_max - height[left]# 移動左指針到下一個位置left += 1else:# 計算當前右指針位置可以捕獲的水量，并累加到答案中ans += suf_max - height[right]# 移動右指針到下一個位置right -= 1# 返回計算出的總水量return ans

?15. 三數之和 - 力扣（LeetCode）

def threeSum(nums):# 首先對數組進行排序nums.sort()result = []# 遍歷數組，直到倒數第三個元素for i in range(len(nums) - 2):# 如果當前數字大于0，則后面的數字都大于0，不可能和為0，直接返回結果if nums[i] > 0:return result# 跳過可能重復的數字if i > 0 and nums[i] == nums[i - 1]:continue# 初始化雙指針left, right = i + 1, len(nums) - 1# 使用雙指針遍歷while left < right:total = nums[i] + nums[left] + nums[right]# 如果三數之和小于0，左指針右移if total < 0:left += 1# 如果三數之和大于0，右指針左移elif total > 0:right -= 1# 如果三數之和等于0，添加到結果中，并移動左右指針else:result.append([nums[i], nums[left], nums[right]])# 跳過可能重復的數字while left < right and nums[left] == nums[left + 1]:left += 1while left < right and nums[right] == nums[right - 1]:right -= 1left += 1right -= 1return result# 示例
nums = [-1, 0, 1, 2, -1, -4]
print(threeSum(nums))  # 輸出應為[[-1, -1, 2], [-1, 0, 1]]

滑動窗口

在滑動窗口中，通常會使用兩個指針，這兩個指針分別被稱為“快指針”和“慢指針”（也有其他叫法，如“左指針”和“右指針”），它們在數組或鏈表上移動以維護一個窗口。

• 快指針（右指針）：通常用于擴展窗口，即向右移動，探索新的元素。
• 慢指針（左指針）：通常用于收縮窗口，即向右移動，移除窗口中的元素。

3. 無重復字符的最長子串 - 力扣（LeetCode）

給定一個字符串?s?，請你找出其中不含有重復字符的?最長子串的長度。

class Solution:def lengthOfLongestSubstring(self, s: str) -> int:left,right = 0,0res = 0if len(s) == 0:return 0if s.count(s[0]) == len(s):return 1if len(set(s)) == len(s):return len(s)while right < len(s):if s[right] not in s[left:right]:right +=1res = max(res,len(s[left:right]))else:while s[right] in s[left:right]:left +=1return res

?438. 找到字符串中所有字母異位詞 - 力扣（LeetCode）

class Solution:def findAnagrams(self, s: str, p: str) -> list:n, m, res = len(s), len(p), []  # 初始化字符串s和p的長度，以及結果列表if n < m: return res  # 如果s的長度小于p，則不可能包含異位詞，直接返回空列表# 初始化兩個長度為26的數組，用于存儲字符計數p_cnt = [0] * 26s_cnt = [0] * 26# 統計字符串p中每個字符的出現次數for i in range(m):p_cnt[ord(p[i]) - ord('a')] += 1left = 0  # 初始化滑動窗口的左邊界for right in range(n):  # 遍歷字符串scur_right = ord(s[right]) - ord('a')  # 計算當前字符在數組中的索引s_cnt[cur_right] += 1  # 增加當前字符的計數# 如果當前字符在s中的出現次數超過了在p中的出現次數，移動左邊界while s_cnt[cur_right] > p_cnt[cur_right]:cur_left = ord(s[left]) - ord('a')  # 計算左邊界字符在數組中的索引s_cnt[cur_left] -= 1  # 減少左邊界字符的計數left += 1  # 移動左邊界# 如果滑動窗口的大小等于p的長度，則找到了一個異位詞if right - left + 1 == m:res.append(left)  # 將左邊界索引添加到結果列表中return res  # 返回所有異位詞的起始索引列表

239. 滑動窗口最大值 - 力扣（LeetCode）

單調遞減的雙端隊列來保存窗口中的元素索引，確保隊列的首部始終是當前窗口的最大值的索引。

雙端隊列：deque允許在隊列的兩端進行插入和刪除操作。

from collections import dequedef maxSlidingWindow(nums, k):if not nums or k == 0:return []deque = deque()  # 存儲元素索引的單調隊列result = []  # 存儲結果for i in range(len(nums)):# 移除所有小于當前元素的索引while deque and nums[deque[-1]] <= nums[i]:deque.pop()# 將當前元素的索引加入隊列deque.append(i)# 移除不在窗口內的索引if deque[0] < i - k + 1:deque.popleft()# 當窗口大小達到 k 時，記錄當前窗口的最大值if i >= k - 1:result.append(nums[deque[0]])return result

76. 最小覆蓋子串 - 力扣（LeetCode）

1. 初始化兩個指針，left?和?right，它們分別表示滑動窗口的左右邊界。
2. 使用兩個哈希表（或字典）來記錄當前窗口中的字符頻率和目標字符串?t?中字符的頻率。
3. 擴展?right?指針來增加窗口的大小，直到窗口包含了?t?中所有的字符。
4. 一旦窗口包含了?t?中所有的字符，嘗試通過移動?left?指針來縮小窗口的大小，同時保持窗口包含?t?中所有的字符。
5. 在每次移動?left?指針時，如果窗口仍然包含?t?中所有的字符，則更新最小子串的長度和起始位置。
6. 重復步驟 3 和 4，直到?right?指針到達字符串?s?的末尾。

def min_window(s, t):if not t or not s:return ""# 初始化需要的字符及其頻率need = {}for char in t:need[char] = need.get(char, 0) + 1#從字典中獲取 char 對應的值。如果 char 不在字典中，則返回默認值 0# 初始化窗口中的字符及其頻率window = {}valid = 0  # 用于記錄窗口中滿足 need 條件的字符個數left, right = 0, 0start, length = 0, float('inf')  # 最小子串的起始位置和長度while right < len(s):# 即將移入窗口的字符c = s[right]# 右移窗口right += 1# 更新窗口中的字符頻率if c in need:window[c] = window.get(c, 0) + 1if window[c] == need[c]:valid += 1# 判斷左側窗口是否要收縮while valid == len(need):# 更新最小子串if right - left < length:start = leftlength = right - left# 即將移出窗口的字符d = s[left]# 左移窗口left += 1# 更新窗口中的字符頻率if d in need:if window[d] == need[d]:valid -= 1window[d] -= 1# 返回最小子串return "" if length == float('inf') else s[start:start + length]# 示例
s = "ADOBECODEBANC"
t = "ABC"
print(min_window(s, t))  # 輸出 "BANC"

廣度優先搜索算法基本用的就是隊列，深度優先搜索算法（DFS）用的基本都是遞歸