回溯算法
「所有可能的结果」，而不是「结果的个数」，一般情况下，我们就知道需要暴力搜索所有的可行解了，可以用「回溯法」。
回溯算法关键在于:不合适就退回上一步。在回溯算法中，递归用于深入到所有可能的分支，而迭代（通常在递归函数内部的循环中体现）用于探索当前层级的所有可能选项。
组合问题
39. 组合总和 - 力扣（LeetCode）
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
1.路径2.求和3.判断
回溯算法：
在循环中回溯前有改变操作，调用回溯函数判断是否继续回溯，如果结束当前循环的回溯，在回溯后进行操作。
from typing import List
class 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[:])
return
if sum(path) > target:
return
for 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 result
def 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 List
class 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 List
class 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)
return
for col in range(n):
if not self.isValid(board, row, col):
continue
board[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)
# 查看上方是否有Q
for i in range(row):
if board[i][col] == 'Q':
return False
# 查看右上方是否有Q
for i, j in zip(range(row - 1, -1, -1), range(col + 1, n, 1)):
if board[i][j] == 'Q':
return False
# 查看左上方是否有Q
for i, j in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):
if board[i][j] == 'Q':
return False
return True
作者：山鬼TJU79. 单词搜索 - 力扣（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 False
n = 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] = 1
if self.backtrack(i, j, mark, board, word[1:]) == True:
return True
else:
# 回溯
mark[i][j] = 0
return False
def backtrack(self, i, j, mark, board, word):
if len(word) == 0:
return True
for 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] = 1
if self.backtrack(cur_i, cur_j, mark, board, word[1:]) == True:
return True
else:
# 回溯
mark[cur_i][cur_j] = 0
return False
22. 括号生成 - 力扣（LeetCode）
可以插入 ） 的前提是 ( 的数量大于 ）
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
res = []
self.dfs(res, n, n, '')
return res
def dfs(self, res, left, right, path):
if left == 0 and right == 0:
res.append(path)
return
if 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 0
max_profit = 0
min_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)) # 输出应为 555. 跳跃游戏 - 力扣（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 True
return True
# 示例
nums = [2, 3, 1, 1, 4]
print(can_jump(nums)) # 输出应为 True45. 跳跃游戏 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:
break
return jumps
# 示例
nums = [2, 3, 1, 1, 4]
print(min_jumps(nums)) # 输出应为 2763. 划分字母区间 - 力扣（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 + 1
return 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]] = i
return []
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 str
for 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 = 0
st = set(nums) # 把 nums 转成哈希集合
for x in st: # 遍历哈希集合
if x - 1 in st:
continue
# x 是序列的起点
y = x + 1
while 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 defaultdict
class Solution:
def subarraySum(self, nums: list, k: int) -> int:
# 初始化计数器，用于记录和为k的子数组的数量
count = 0
n = len(nums)
# 使用defaultdict来存储前缀和出现的次数，初始时前缀和为0出现1次
preSums = defaultdict(int)
preSums[0] = 1
# 初始化前缀和为0
presum = 0
# 遍历数组中的每个元素
for i in range(n):
# 更新当前的前缀和
presum += nums[i]
# 如果存在某个前缀和等于当前前缀和减去k，则说明存在一个子数组的和为k
# defaultdict的特性使得当key不存在时返回0，所以这里不需要判断key是否存在
count += preSums[presum - k]
# 将当前前缀和出现的次数加1
preSums[presum] += 1
# 返回和为k的子数组的数量
return count双指针
283. 移动零 - 力扣（LeetCode）
快慢指针，当碰到0时i会比i0走的快
from typing import List
class 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 = 0
right = len(height) - 1
while left < right:
area = (right - left) * min(height[left], height[right])
ans = max(ans, area)
if height[left] < height[right]:
# height[left] 与右边的任意线段都无法组成一个比 ans 更大的面积
left += 1
else:
# height[right] 与左边的任意线段都无法组成一个比 ans 更大的面积
right -= 1
return ans
42. 接雨水 - 力扣（LeetCode）
对撞指针
from typing import List
class 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 += 1
else:
# 计算当前右指针位置可以捕获的水量，并累加到答案中
ans += suf_max - height[right]
# 移动右指针到下一个位置
right -= 1
# 返回计算出的总水量
return ans15. 三数之和 - 力扣（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 += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
return 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,0
res = 0
if len(s) == 0:
return 0
if s.count(s[0]) == len(s):
return 1
if len(set(s)) == len(s):
return len(s)
while right < len(s):
if s[right] not in s[left:right]:
right +=1
res = max(res,len(s[left:right]))
else:
while s[right] in s[left:right]:
left +=1
return 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] * 26
s_cnt = [0] * 26
# 统计字符串p中每个字符的出现次数
for i in range(m):
p_cnt[ord(p[i]) - ord('a')] += 1
left = 0 # 初始化滑动窗口的左边界
for right in range(n): # 遍历字符串s
cur_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 deque
def 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 result76. 最小覆盖子串 - 力扣（LeetCode）
- 初始化两个指针，
left和right，它们分别表示滑动窗口的左右边界。 - 使用两个哈希表（或字典）来记录当前窗口中的字符频率和目标字符串
t中字符的频率。 - 扩展
right指针来增加窗口的大小，直到窗口包含了t中所有的字符。 - 一旦窗口包含了
t中所有的字符，尝试通过移动left指针来缩小窗口的大小，同时保持窗口包含t中所有的字符。 - 在每次移动
left指针时，如果窗口仍然包含t中所有的字符，则更新最小子串的长度和起始位置。 - 重复步骤 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, 0
start, length = 0, float('inf') # 最小子串的起始位置和长度
while right < len(s):
# 即将移入窗口的字符
c = s[right]
# 右移窗口
right += 1
# 更新窗口中的字符频率
if c in need:
window[c] = window.get(c, 0) + 1
if window[c] == need[c]:
valid += 1
# 判断左侧窗口是否要收缩
while valid == len(need):
# 更新最小子串
if right - left < length:
start = left
length = right - left
# 即将移出窗口的字符
d = s[left]
# 左移窗口
left += 1
# 更新窗口中的字符频率
if d in need:
if window[d] == need[d]:
valid -= 1
window[d] -= 1
# 返回最小子串
return "" if length == float('inf') else s[start:start + length]
# 示例
s = "ADOBECODEBANC"
t = "ABC"
print(min_window(s, t)) # 输出 "BANC"广度优先搜索算法基本用的就是队列，深度优先搜索算法（DFS）用的基本都是递归
