# 回溯算法 组合 ```python # 第77题. 组合 # 返回 1 ... n 中所有可能的 k 个数的组合。 class Solution: def combine(self, n: int, k: int) -> List[List[int]]: result = [] # 存放结果集 self.backtracking(n, k, 1, [], result) return result def backtracking(self, n, k, startIndex, path, result): if len(path) == k: result.append(path[:]) return for i in range(startIndex, n - (k - len(path)) + 2): # 优化的地方，优化前 range(startIndex, n + 1) path.append(i) # 处理节点 self.backtracking(n, k, i + 1, path, result) path.pop() # 回溯，撤销处理的节点 ``` ```python #R 216.组合总和III # [1,2,3,4,5,6,7,8,9]这个集合中找到和为n的k个数的组合 class Solution: def combinationSum3(self, k: int, n: int) -> List[List[int]]: result = [] # 存放结果集 self.backtracking(n, k, 0, 1, [], result) return result def backtracking(self, targetSum, k, currentSum, startIndex, path, result): if currentSum > targetSum: # 剪枝操作 return # 如果path的长度等于k但currentSum不等于targetSum，则直接返回 if len(path) == k: if currentSum == targetSum: result.append(path[:]) return for i in range(startIndex, 9 - (k - len(path)) + 2): # 剪枝 currentSum += i # 处理 path.append(i) # 处理 self.backtracking(targetSum, k, currentSum, i + 1, path, result) # 注意i+1调整startIndex currentSum -= i # 回溯 path.pop() # 回溯 ``` ```python # 0 电话号码的字母组合 class Solution: def __init__(self): self.letterMap = [ "", # 0 "", # 1 "abc", # 2 "def", # 3 "ghi", # 4 "jkl", # 5 "mno", # 6 "pqrs", # 7 "tuv", # 8 "wxyz" # 9 ] self.result = [] self.s = "" def backtracking(self, digits, index): if index == len(digits): self.result.append(self.s) return digit = int(digits[index]) # 将索引处的数字转换为整数 letters = self.letterMap[digit] # 获取对应的字符集 for i in range(len(letters)): self.s += letters[i] # 处理字符 self.backtracking(digits, index + 1) # 递归调用，注意索引加1，处理下一个数字 self.s = self.s[:-1] # 回溯，删除最后添加的字符 def letterCombinations(self, digits): if len(digits) == 0: return self.result self.backtracking(digits, 0) return self.result ``` ```python # 39. 组合总和 # 无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 # candidates 中的数字可以无限制重复被选取。 class Solution: def backtracking(self, candidates, target, total, startIndex, path, result): if total > target: return if total == target: result.append(path[:]) return for i in range(startIndex, len(candidates)): total += candidates[i] path.append(candidates[i]) self.backtracking(candidates, target, total, i, path, result) # 不用i+1了，表示可以重复读取当前的数 total -= candidates[i] path.pop() def combinationSum(self, candidates, target): result = [] self.backtracking(candidates, target, 0, 0, [], result) return result ``` ```python #R 40.组合总和II # 数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。 class Solution: def backtracking(self, candidates, target, total, startIndex, used, path, result): if total == target: result.append(path[:]) return for i in range(startIndex, len(candidates)): # 对于相同的数字，只选择第一个未被使用的数字，跳过其他相同数字 if i > startIndex and candidates[i] == candidates[i - 1] and not used[i - 1]: continue if total + candidates[i] > target: break total += candidates[i] path.append(candidates[i]) used[i] = True self.backtracking(candidates, target, total, i + 1, used, path, result) used[i] = False total -= candidates[i] path.pop() def combinationSum2(self, candidates, target): used = [False] * len(candidates) result = [] candidates.sort() self.backtracking(candidates, target, 0, 0, used, [], result) return result ``` 分割 ```python #R 131.分割回文串 # 将 s 分割成一些子串，使每个子串都是回文串 class Solution: def partition(self, s: str) -> List[List[str]]: # 递归用于纵向遍历; for循环用于横向遍历; 当切割线迭代至字符串末尾，说明找到一种方法; 类似组合问题，为了不重复切割同一位置，需要start_index来做标记下一轮递归的起始位置(切割线) result = [] self.backtracking(s, 0, [], result) return result def backtracking(self, s, start_index, path, result ): # Base Case if start_index == len(s): result.append(path[:]) return # 单层递归逻辑 for i in range(start_index, len(s)): # 此次比其他组合题目多了一步判断： # 判断被截取的这一段子串([start_index, i])是否为回文串 if self.is_palindrome(s, start_index, i): path.append(s[start_index:i+1]) self.backtracking(s, i+1, path, result) # 递归纵向遍历：从下一处进行切割，判断其余是否仍为回文串 path.pop() # 回溯 def is_palindrome(self, s: str, start: int, end: int) -> bool: i: int = start j: int = end while i < j: if s[i] != s[j]: return False i += 1 j -= 1 return True ``` ```python #R 93.复原IP地址 class Solution: def restoreIpAddresses(self, s: str) -> List[str]: result = [] self.backtracking(s, 0, 0, "", result) return result def backtracking(self, s, start_index, point_num, current, result): if point_num == 3: # 逗点数量为3时，分隔结束 if self.is_valid(s, start_index, len(s) - 1): # 判断第四段子字符串是否合法 current += s[start_index:] # 添加最后一段子字符串 result.append(current) return for i in range(start_index, len(s)): if self.is_valid(s, start_index, i): # 判断 [start_index, i] 这个区间的子串是否合法 sub = s[start_index:i + 1] self.backtracking(s, i + 1, point_num + 1, current + sub + '.', result) else: break def is_valid(self, s, start, end): if start > end: return False if s[start] == '0' and start != end: # 0开头的数字不合法 return False num = 0 for i in range(start, end + 1): if not s[i].isdigit(): # 遇到非数字字符不合法 return False num = num * 10 + int(s[i]) if num > 255: # 如果大于255了不合法 return False return True ``` 子集 ```python # 0 子集 class Solution: def subsets(self, nums): result = [] path = [] self.backtracking(nums, 0, path, result) return result def backtracking(self, nums, startIndex, path, result): result.append(path[:]) # 收集子集，要放在终止添加的上面，否则会漏掉自己 # if startIndex >= len(nums): # 终止条件可以不加 # return for i in range(startIndex, len(nums)): path.append(nums[i]) self.backtracking(nums, i + 1, path, result) path.pop() ``` ```python #R 90.子集II # 可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。 解集不能包含重复的子集。 class Solution: def subsetsWithDup(self, nums): result = [] path = [] used = [False] * len(nums) nums.sort() # 去重需要排序 self.backtracking(nums, 0, used, path, result) return result def backtracking(self, nums, startIndex, used, path, result): result.append(path[:]) # 收集子集 for i in range(startIndex, len(nums)): # used[i - 1] == True，说明同一树枝 nums[i - 1] 使用过 # used[i - 1] == False，说明同一树层 nums[i - 1] 使用过 # 而我们要对同一树层使用过的元素进行跳过 if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]: continue path.append(nums[i]) used[i] = True self.backtracking(nums, i + 1, used, path, result) used[i] = False path.pop() ``` ```python #R 491.递增子序列 # 数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。 利用set去重 class Solution: def findSubsequences(self, nums): result = [] path = [] self.backtracking(nums, 0, path, result) return result def backtracking(self, nums, startIndex, path, result): if len(path) > 1: result.append(path[:]) # 注意要使用切片将当前路径的副本加入结果集 # 注意这里不要加return，要取树上的节点 uset = set() # 使用集合对本层元素进行去重 for i in range(startIndex, len(nums)): if (path and nums[i] < path[-1]) or nums[i] in uset: continue uset.add(nums[i]) # 记录这个元素在本层用过了，本层后面不能再用了 path.append(nums[i]) self.backtracking(nums, i + 1, path, result) path.pop() ``` 排列 ```python # 46.全排列 class Solution: def permute(self, nums): result = [] self.backtracking(nums, [], [False] * len(nums), result) return result def backtracking(self, nums, path, used, result): if len(path) == len(nums): result.append(path[:]) return for i in range(len(nums)): if used[i]: continue used[i] = True path.append(nums[i]) self.backtracking(nums, path, used, result) path.pop() used[i] = False ``` ```python #R 47.全排列 II # 可包含重复数字的序列 ，返回所有不重复的全排列 class Solution: def permuteUnique(self, nums): nums.sort() # 排序 result = [] self.backtracking(nums, [], [False] * len(nums), result) return result def backtracking(self, nums, path, used, result): if len(path) == len(nums): result.append(path[:]) return for i in range(len(nums)): if (i > 0 and nums[i] == nums[i - 1] and not used[i - 1]) or used[i]: continue used[i] = True path.append(nums[i]) self.backtracking(nums, path, used, result) path.pop() used[i] = False ``` 棋盘 ```python #R 51. N皇后 class Solution: def solveNQueens(self, n: int) -> List[List[str]]: result = [] # 存储最终结果的二维字符串数组 chessboard = ['.' * n for _ in range(n)] # 初始化棋盘 self.backtracking(n, 0, chessboard, result) # 回溯求解 return [[''.join(row) for row in solution] for solution in result] # 返回结果集 def backtracking(self, n: int, row: int, chessboard: List[str], result: List[List[str]]) -> None: if row == n: result.append(chessboard[:]) # 棋盘填满，将当前解加入结果集 return for col in range(n): if self.isValid(row, col, chessboard): chessboard[row] = chessboard[row][:col] + 'Q' + chessboard[row][col+1:] # 放置皇后 self.backtracking(n, row + 1, chessboard, result) # 递归到下一行 chessboard[row] = chessboard[row][:col] + '.' + chessboard[row][col+1:] # 回溯，撤销当前位置的皇后 def isValid(self, row: int, col: int, chessboard: List[str]) -> bool: # 检查列 for i in range(row): if chessboard[i][col] == 'Q': return False # 当前列已经存在皇后，不合法 # 检查 45 度角是否有皇后 i, j = row - 1, col - 1 while i >= 0 and j >= 0: if chessboard[i][j] == 'Q': return False # 左上方向已经存在皇后，不合法 i -= 1 j -= 1 # 检查 135 度角是否有皇后 i, j = row - 1, col + 1 while i >= 0 and j < len(chessboard): if chessboard[i][j] == 'Q': return False # 右上方向已经存在皇后，不合法 i -= 1 j += 1 return True # 当前位置合法 ``` ```python #R 37. 解数独 class Solution: def solveSudoku(self, board: List[List[str]]) -> None: """ Do not return anything, modify board in-place instead. """ self.backtracking(board) def backtracking(self, board: List[List[str]]) -> bool: # 若有解，返回True；若无解，返回False for i in range(len(board)): # 遍历行 for j in range(len(board[0])): # 遍历列 # 若空格内已有数字，跳过 if board[i][j] != '.': continue for k in range(1, 10): if self.is_valid(i, j, k, board): board[i][j] = str(k) if self.backtracking(board): return True board[i][j] = '.' # 若数字1-9都不能成功填入空格，返回False无解 return False return True # 有解 def is_valid(self, row: int, col: int, val: int, board: List[List[str]]) -> bool: # 判断同一行是否冲突 for i in range(9): if board[row][i] == str(val): return False # 判断同一列是否冲突 for j in range(9): if board[j][col] == str(val): return False # 判断同一九宫格是否有冲突 start_row = (row // 3) * 3 start_col = (col // 3) * 3 for i in range(start_row, start_row + 3): for j in range(start_col, start_col + 3): if board[i][j] == str(val): return False return True ``` 其他 ```python #R 282 Expression Add Operators/给表达式添加运算符 (Hard) # 输入: num = "123", target = 6 输出: ["1+2+3", "1*2*3"] # 每个字符与字符实际上有四种连接方式，加减乘和拼接 class Solution: def addOperators(self, num: str, target: int) -> List[str]: def backtrace(idx: int, cursum: int, preadd: int) -> None: nonlocal res nonlocal path if idx == n: if cursum == target: res.append(path[:]) return pn = len(path) for i in range(idx, n): x_str = num[idx: i + 1] x = int(x_str) if idx == 0: path += x_str backtrace(i + 1, cursum + x, x) path = path[ :pn] else: path += '+' + x_str backtrace(i + 1, cursum + x, x) path = path[ :pn] path += '-' + x_str backtrace(i + 1, cursum - x, -x) path = path[ :pn] path += '*' + x_str backtrace(i + 1, cursum - preadd + preadd * x, preadd * x) path = path[ :pn] if x == 0: return n = len(num) res = [] path = "" backtrace(0, 0, 0) return res ``` ```python #R 698 Partition to K Equal Sum Subsets/划分为k个相等的子集 (Medium) class Solution: def canPartitionKSubsets(self, nums: List[int], k: int) -> bool: def dfs(i): if i == len(nums): return True for j in range(k): if j and cur[j] == cur[j - 1]: continue cur[j] += nums[i] if cur[j] <= s and dfs(i + 1): return True cur[j] -= nums[i] return False s, mod = divmod(sum(nums), k) if mod: return False cur = [0] * k nums.sort(reverse=True) return dfs(0) ``` # 图Visited ```python # 连通图归类 def fun(fd): visited = set() res = [] def helper(p, group): if p in visited: return visited.add(p) group.append(p) for f in fd[p]: if f not in visited: helper(f, group) for key in fd: if key not in visited: group = [] helper(key, group) res.append(group) return res # 构造一个图,返回结果：[[1, 2], [3]] graph = { 1: [2], 2: [1], 3: [ ] } ``` ```python # 计算某节点所在的连通分量的成员个数 from typing import List, Dict, Set def helper(friend_map: Dict[int, List[int]], p: int, visited: Set[int]) -> int: # helper在求p所在类的成员个数 if p in visited: return 0 visited.add(p) res = 1 for f in friend_map[p]: if f not in visited: res += helper(friend_map, f, visited) return res visited_set = set() result = helper(graph, 1, visited_set) ``` ```python # 返回类的个数（0. Number of Provinces/省份数量）(Medium) from typing import List def findCircleNum(graph: List[List[int]]) -> int: def dfs(node): visited.add(node) for neighbor, isConnected in enumerate(graph[node]): if isConnected and neighbor not in visited: dfs(neighbor) n = len(graph) provinces = 0 visited = set() for city in range(n): if city not in visited: provinces += 1 dfs(city) return provinces # 示例 graph = [ [1, 1, 0], [1, 1, 0], [0, 0, 1] ] ``` ```python #R Most Stones Removed with Same Row or Column/移除最多的同行或同列石头(Medium) # 石头放在整数坐标点上, move操作移除某一块石头共享一列或一行的一块石头,最多能执行多少次 move class Solution: def removeStones(self, stones: List[List[int]]) -> int: # 构建图 graph = collections.defaultdict(list) for i, (x, y) in enumerate(stones): for j, (xx, yy) in enumerate(stones): if x == xx or y == yy: graph[i].append(j) # DFS计算连通分量数量 def dfs(node): visited.add(node) for neighbor in graph[node]: if neighbor not in visited: dfs(neighbor) n = len(stones) visited = set() components = 0 for i in range(n): if i not in visited: components += 1 dfs(i) return n - components ``` ```python # n个点最少移动几根能使所有点都连通当且仅当线的个数>=n-1. 最少移动的数就是连通分支个数-1 (1319. Number of Operations to Make Network Connected) class Solution: def makeConnected(self, n: int, connections: List[List[int]]) -> int: if len(connections) < n - 1: return -1 edges = collections.defaultdict(list) for x, y in connections: edges[x].append(y) edges[y].append(x) seen = set() def dfs(u: int): seen.add(u) for v in edges[u]: if v not in seen: dfs(v) ans = 0 for i in range(n): if i not in seen: dfs(i) ans += 1 return ans - 1 ``` ```python #无向图环路检测，可以使用深度优先搜索（DFS）来检测是否存在环路。一般的思路是从一个节点开始进行深度优先搜索，如果在搜索的过程中访问到了已经访问过的节点，那么就说明存在环。 #? Bellman-Ford，无向图环路检测，良序 ``` ```python #R 200. Number of Islands 给定一个由 '1'（陆地）和 '0'（水）组成的二维网格，计算岛屿的数量。岛屿是由相邻的陆地水平或垂直连接形成的（不包括对角线）。你可以假设网格的四个边都被水包围。 class Solution: def numIslands(self, grid: List[List[str]]) -> int: if not grid or not grid[0]: return 0 rows, cols = len(grid), len(grid[0]) islands = 0 def dfs(row, col): if 0 <= row < rows and 0 <= col < cols and grid[row][col] == '1': grid[row][col] = '0' # 标记为已访问 # 递归搜索相邻的陆地 dfs(row - 1, col) dfs(row + 1, col) dfs(row, col - 1) dfs(row, col + 1) for row in range(rows): for col in range(cols): if grid[row][col] == '1': islands += 1 dfs(row, col) return islands ``` ```python #类似的题目 Search treasury # 皮卡公式：如果只有一个dect告诉你点在内部=1，边界=0，外部=-1，求多边形面积：从一个内部点开始探测出内部点i和边界点b个数，用皮卡公式：i + b/2.0 – 1 def help(pt, visited, i, b): # 为了在递归调用中保持对 i 和 b 的引用，将它们封装为长度为 1 的列表（[i] 和 [b]），通过修改列表的值实现引用传递的效果。 def dect(p): # 实现 dext 函数的逻辑 # 注意：这里的 dext 函数需要根据实际情况替换为你的具体实现 pass if dect(pt) == -1 or tuple(pt) in visited: return visited.add(tuple(pt)) if dect(pt) == 1: i[0] += 1 if dect(pt) == 0: b[0] += 1 help([pt[0] + 1, pt[1]], visited, i, b) help([pt[0] - 1, pt[1]], visited, i, b) help([pt[0], pt[1] + 1], visited, i, b) help([pt[0], pt[1] - 1], visited, i, b) ``` ```python # 797 回溯， 所有可能的路径，有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径 class Solution: def __init__(self): self.result = [] self.path = [0] def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]: if not graph: return [] self.dfs(graph, 0) return self.result def dfs(self, graph, root: int): if root == len(graph) - 1: # 成功找到一条路径时 # ***Python的list是mutable类型*** # ***回溯中必须使用Deep Copy*** self.result.append(self.path[:]) return for node in graph[root]: # 遍历节点n的所有后序节点 self.path.append(node) self.dfs(graph, node) self.path.pop() # 回溯 ``` ```python #R (hard) 单词接龙，从单词 beginWord 和 endWord 的转换序列每次转换只能改变一个字母，wordList = ["hot","dot","dog"] class Solution: def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int: wordSet = set(wordList) if len(wordSet)== 0 or endWord not in wordSet: return 0 mapping = {beginWord:1} queue = deque([beginWord]) while queue: word = queue.popleft() path = mapping[word] for i in range(len(word)): word_list = list(word) for j in range(26): word_list[i] = chr(ord('a')+j) newWord = "".join(word_list) if newWord == endWord: return path+1 if newWord in wordSet and newWord not in mapping: mapping[newWord] = path+1 queue.append(newWord) return 0 ``` ```python #R 463. 岛屿的周长 class Solution: def islandPerimeter(self, grid: List[List[int]]) -> int: m = len(grid) n = len(grid[0]) # 创建res二维素组记录答案 res = [[0] * n for j in range(m)] for i in range(m): for j in range(len(grid[i])): # 如果当前位置为水域，不做修改或reset res[i][j] = 0 if grid[i][j] == 0: res[i][j] = 0 # 如果当前位置为陆地，往四个方向判断，update res[i][j] elif grid[i][j] == 1: if i == 0 or (i > 0 and grid[i-1][j] == 0): res[i][j] += 1 if j == 0 or (j >0 and grid[i][j-1] == 0): res[i][j] += 1 if i == m-1 or (i < m-1 and grid[i+1][j] == 0): res[i][j] += 1 if j == n-1 or (j < n-1 and grid[i][j+1] == 0): res[i][j] += 1 # 最后求和res矩阵，这里其实不一定需要矩阵记录，可以设置一个variable res 记录边长，舍矩阵无非是更加形象而已 ans = sum([sum(row) for row in res]) return ans ``` ```python # 1066. Campus Bikes II # visited技巧题目非图论 workers, bikes代表工人和自行车的坐标。找到工人各自的自行车使得L1距离总和最近。 res[i] = work[i]对应的bikes, work和bike都没有访问过，才更新res def assignBikes(workers, bikes): def dist(a, b): return abs(a[0] - b[0]) + abs(a[1] - b[1]) dict_list = [] for i in range(len(workers)): for j in range(len(bikes)): dict_list.append([dist(workers[i], bikes[j]), i, j]) dict_list.sort(key=lambda x: x[0]) res = [-1] * len(workers) visited = set() for it in dict_list: if res[it[1]] == -1 and it[2] not in visited: res[it[1]] = it[2] visited.add(it[2]) return res ``` ```python #R 1091. Shortest Path in Binary Matrix/二进制矩阵中的最短路径(Medium) class Solution: def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int: if grid[0][0]: return -1 n = len(grid) grid[0][0] = 1 q = deque([(0, 0)]) ans = 1 while q: for _ in range(len(q)): i, j = q.popleft() if i == j == n - 1: return ans for x in range(i - 1, i + 2): for y in range(j - 1, j + 2): if 0 <= x < n and 0 <= y < n and grid[x][y] == 0: grid[x][y] = 1 q.append((x, y)) ans += 1 return -1 ``` ```python # 0 Course Schedule. prerequisites[i] = [a, b] 表示如果要学习课程 a 则必须先学习课程 b。判断是否可能完成所有课程学习。 统计课程安排图中每个节点的入度，生成 入度表 indegrees。 借助一个队列 queue，将所有入度为 0 的节点入队。 当 queue 非空时，依次将队首节点出队，在课程安排图中删除此节点 pre 在每次 pre 出队时，执行 numCourses--； class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: indegrees = [0 for _ in range(numCourses)] adjacency = [[] for _ in range(numCourses)] queue = deque() # Get the indegree and adjacency of every course. for cur, pre in prerequisites: indegrees[cur] += 1 adjacency[pre].append(cur) # Get all the courses with the indegree of 0. for i in range(len(indegrees)): if not indegrees[i]: queue.append(i) # BFS TopSort. while queue: pre = queue.popleft() numCourses -= 1 for cur in adjacency[pre]: indegrees[cur] -= 1 if not indegrees[cur]: queue.append(cur) return not numCourses ``` ```python #R 210 Course Schedule II/课程表 II (Medium) # 返回你为了学完所有课程所安排的学习顺序，indeg 存储每个节点的入度 class Solution: def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]: g = defaultdict(list) indeg = [0] * numCourses for a, b in prerequisites: g[b].append(a) indeg[a] += 1 ans = [] q = deque(i for i, x in enumerate(indeg) if x == 0) while q: i = q.popleft() ans.append(i) for j in g[i]: indeg[j] -= 1 if indeg[j] == 0: q.append(j) return ans if len(ans) == numCourses else [] ``` ```python #R 329 Longest Increasing Path in a Matrix/矩阵中的最长递增路径 (Medium) class Solution: def longestIncreasingPath(self, matrix: List[List[int]]) -> int: m, n = len(matrix), len(matrix[0]) flag = [[-1] * n for _ in range(m)] #存储从（i，j）出发的最长递归路径 def dfs(i, j): if flag[i][j] != -1: # 记忆化搜索，避免重复的计算 return flag[i][j] else: d = 1 for (x, y) in [[-1, 0], [1, 0], [0, 1], [0, -1]]: x, y = i + x, j + y if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[i][j]: d = max(d, dfs(x, y) + 1) # 取四个邻接点的最长 flag[i][j] = d return d res = 0 for i in range(m): # 遍历矩阵计算最长路径 for j in range(n): if flag[i][j] == -1: res = max(res, dfs(i, j)) return res ``` ```python #R 743 Network Delay Time/网络延迟时间 (Medium) # 从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号 Dijkstra 算法 class Solution: def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int: g = [[float('inf')] * n for _ in range(n)] for x, y, time in times: g[x - 1][y - 1] = time dist = [float('inf')] * n dist[k - 1] = 0 used = [False] * n for _ in range(n): x = -1 for y, u in enumerate(used): if not u and (x == -1 or dist[y] < dist[x]): x = y used[x] = True for y, time in enumerate(g[x]): dist[y] = min(dist[y], dist[x] + time) ans = max(dist) return ans if ans < float('inf') else -1 ``` ```python # 752 Open the Lock/打开转盘锁 (Medium) from queue import Queue class Solution: def openLock(self, deadends: List[str], target: str) -> int: deadends = set(deadends) # in 操作在set中时间复杂度为O(1) if '0000' in deadends: return -1 # ----------------BFS 开始------------------ q = Queue() q.put(('0000', 0)) # 初始化根节点 (当前节点值，转动步数) while not q.empty(): node, step = q.get() for i in range(4): for add in (1, -1): cur = node[:i] + str((int(node[i]) + add) % 10) + node[i+1:] if cur == target: return step + 1 if not cur in deadends: q.put((cur, step + 1)) deadends.add(cur) # 避免重复搜索 return -1 ``` ```python #R 827 Making A Large Island/最大人工岛 (Hard) # 最多 只能将一格 0 变成 1 class Solution: def largestIsland(self, grid: List[List[int]]) -> int: n = len(grid) def dfs(i: int, j: int) -> int: size = 1 grid[i][j] = len(area) + 2 # 记录 (i,j) 属于哪个岛 for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1): if 0 <= x < n and 0 <= y < n and grid[x][y] == 1: size += dfs(x, y) return size # DFS 每个岛，统计各个岛的面积，记录到 area 列表中 area = [] for i, row in enumerate(grid): for j, x in enumerate(row): if x == 1: area.append(dfs(i, j)) # 加上这个特判，可以快很多 if not area: # 没有岛 return 1 ans = 0 for i, row in enumerate(grid): for j, x in enumerate(row): if x: continue s = set() for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1): if 0 <= x < n and 0 <= y < n and grid[x][y]: s.add(grid[x][y]) # 记录上下左右格子所属岛屿编号 ans = max(ans, sum(area[idx - 2] for idx in s) + 1) # 累加面积 return ans if ans else n * n # 如果最后 ans 仍然为 0，说明所有格子都是 1，返回 n^2 ``` ```python #R 0 Get Watched Videos by Your Friends/获取你好友已观看的视频 (Medium) # watchedVideos[i] 和 friends[i] 分别表示 id = i 的人观看过的视频列表和他的好友列表。找出所有指定 level 的视频 class Solution: def watchedVideosByFriends(self, watchedVideos, friends, id, level): n = len(friends) used = [False] * n q = collections.deque([id]) used[id] = True for _ in range(level): span = len(q) for i in range(span): u = q.popleft() for v in friends[u]: if not used[v]: q.append(v) used[v] = True freq = collections.Counter() for _ in range(len(q)): u = q.pop() for watched in watchedVideos[u]: freq[watched] += 1 videos = list(freq.items()) videos.sort(key=lambda x: (x[1], x[0])) ans = [video[0] for video in videos] return ans ``` ```python #R 1761 Minimum Degree of a Connected Trio in a Graph/一个图中连通三元组的最小度数 (困难) # 连通三元组的度数 是所有满足此条件的边的数目：一个顶点在这个三元组内，而另一个顶点不在这个三元组内。返回所有连通三元组中度数的 最小值 class Solution: def minTrioDegree(self, n: int, edges: List[List[int]]) -> int: g = [[False] * n for _ in range(n)] deg = [0] * n for u, v in edges: u, v = u - 1, v - 1 g[u][v] = g[v][u] = True deg[u] += 1 deg[v] += 1 ans = inf for i in range(n): for j in range(i + 1, n): if g[i][j]: for k in range(j + 1, n): if g[i][k] and g[j][k]: ans = min(ans, deg[i] + deg[j] + deg[k] - 6) return -1 if ans == inf else ans ``` # 动态规划 简单 ```python # 1. 斐波那契数 class Solution: def fib(self, n: int) -> int: # 排除 Corner Case if n == 0: return 0 # 创建 dp table dp = [0] * (n + 1) # 初始化 dp 数组 dp[0] = 0 dp[1] = 1 # 遍历顺序: 由前向后。因为后面要用到前面的状态 for i in range(2, n + 1): # 确定递归公式/状态转移公式 dp[i] = dp[i - 1] + dp[i - 2] # 返回答案 return dp[n] ``` ```python # 1. 爬楼梯 # 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶 # 空间复杂度为O(n)版本 class Solution: def climbStairs(self, n: int) -> int: if n <= 1: return n dp = [0] * (n + 1) dp[1] = 1 dp[2] = 2 for i in range(3, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n] ``` ```python # 1. 使用最小花费爬楼梯 class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: dp = [0] * (len(cost) + 1) dp[0] = 0 # 初始值，表示从起点开始不需要花费体力 dp[1] = 0 # 初始值，表示经过第一步不需要花费体力 for i in range(2, len(cost) + 1): # 在第i步，可以选择从前一步（i-1）花费体力到达当前步，或者从前两步（i-2）花费体力到达当前步 # 选择其中花费体力较小的路径，加上当前步的花费，更新dp数组 dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]) return dp[len(cost)] # 返回到达楼顶的最小花费 ``` ```python # 62.不同路径 # 一个机器人位于一个 m x n 网格的左上角，机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。总共有多少条不同的路径 class Solution: def uniquePaths(self, m: int, n: int) -> int: # 创建一个二维列表用于存储唯一路径数 dp = [[0] * n for _ in range(m)] # 设置第一行和第一列的基本情况 for i in range(m): dp[i][0] = 1 for j in range(n): dp[0][j] = 1 # 计算每个单元格的唯一路径数 for i in range(1, m): for j in range(1, n): dp[i][j] = dp[i - 1][j] + dp[i][j - 1] # 返回右下角单元格的唯一路径数 return dp[m - 1][n - 1] ``` ```python 0. 子矩阵和：一般用动态规划。dp 行列各加一行0方便计算 ``` ```python # 1. 不同路径 II 网格中有障碍物 class Solution: def uniquePathsWithObstacles(self, obstacleGrid): m = len(obstacleGrid) n = len(obstacleGrid[0]) if obstacleGrid[m - 1][n - 1] == 1 or obstacleGrid[0][0] == 1: return 0 dp = [[0] * n for _ in range(m)] for i in range(m): if obstacleGrid[i][0] == 0: # 遇到障碍物时，直接退出循环，后面默认都是0 dp[i][0] = 1 else: break for j in range(n): if obstacleGrid[0][j] == 0: dp[0][j] = 1 else: break for i in range(1, m): for j in range(1, n): if obstacleGrid[i][j] == 1: continue dp[i][j] = dp[i - 1][j] + dp[i][j - 1] return dp[m - 1][n - 1] ``` ```python # 96.不同的二叉搜索树 class Solution: def numTrees(self, n: int) -> int: dp = [0] * (n + 1) # 创建一个长度为n+1的数组，初始化为0 dp[0] = 1 # 当n为0时，只有一种情况，即空树，所以dp[0] = 1 for i in range(1, n + 1): # 遍历从1到n的每个数字 for j in range(1, i + 1): # 对于每个数字i，计算以i为根节点的二叉搜索树的数量 dp[i] += dp[j - 1] * dp[i - j] # 利用动态规划的思想，累加左子树和右子树的组合数量 return dp[n] # 返回以1到n为节点的二叉搜索树的总数量 ``` ```python # 139.单词拆分 # s 是否可以被空格拆分为一个或多个在字典中出现的单词 class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: wordSet = set(wordDict) n = len(s) dp = [False] * (n + 1) # dp[i] 表示字符串的前 i 个字符是否可以被拆分成单词 dp[0] = True # 初始状态，空字符串可以被拆分成单词 for i in range(1, n + 1): # 遍历背包 for j in range(i): # 遍历单词 if dp[j] and s[j:i] in wordSet: dp[i] = True # 如果 s[0:j] 可以被拆分成单词，并且 s[j:i] 在单词集合中存在，则 s[0:i] 可以被拆分成单词 break return dp[n] ``` 背包问题 ```python #R 背包问题 def test_2_ei_bag_problem1(weight, value, bagweight): # 二维数组 dp = [[0] * (bagweight + 1) for _ in range(len(weight))] # 初始化 for j in range(weight[0], bagweight + 1): dp[0][j] = value[0] # weight数组的大小就是物品个数 for i in range(1, len(weight)): # 遍历物品 for j in range(bagweight + 1): # 遍历背包容量 if j < weight[i]: dp[i][j] = dp[i - 1][j] else: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]) return dp[len(weight) - 1][bagweight] ``` ```python # 0 分割等和子集 # 将这个数组分割成两个子集，使得两个子集的元素和相等 class Solution: def canPartition(self, nums: List[int]) -> bool: total_sum = sum(nums) if total_sum % 2 != 0: return False target_sum = total_sum // 2 dp = [[False] * (target_sum + 1) for _ in range(len(nums) + 1)] # 初始化第一行（空子集可以得到和为0） for i in range(len(nums) + 1): dp[i][0] = True for i in range(1, len(nums) + 1): for j in range(1, target_sum + 1): if j < nums[i - 1]: # 当前数字大于目标和时，无法使用该数字 dp[i][j] = dp[i - 1][j] else: # 当前数字小于等于目标和时，可以选择使用或不使用该数字 dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]] return dp[len(nums)][target_sum] ``` ```python # 494.目标和 # 有两个符号 + 和 - 使最终数组和为目标数 S 的所有添加符号的方法数 class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: total_sum = sum(nums) # 计算nums的总和 if abs(target) > total_sum: return 0 # 此时没有方案 if (target + total_sum) % 2 == 1: return 0 # 此时没有方案 target_sum = (target + total_sum) // 2 # 目标和 # 创建二维动态规划数组，行表示选取的元素数量，列表示累加和 dp = [[0] * (target_sum + 1) for _ in range(len(nums) + 1)] # 初始化状态 dp[0][0] = 1 # 动态规划过程 for i in range(1, len(nums) + 1): for j in range(target_sum + 1): dp[i][j] = dp[i - 1][j] # 不选取当前元素 if j >= nums[i - 1]: dp[i][j] += dp[i - 1][j - nums[i - 1]] # 选取当前元素 return dp[len(nums)][target_sum] # 返回达到目标和的方案数 ``` ```python # 474.一和零 # 找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 # dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。 ``` ```python # 518.零钱兑换II # 函数来计算可以凑成总金额的硬币组合数 ``` ```python # 爬楼梯（进阶版）每次你可以爬至多m (1 <= m < n)个台阶。 ``` ```python #R 零钱兑换 计算可以凑成总金额所需的最少的硬币个数。 class Solution: def coinChange(self, coins: List[int], amount: int) -> int: n = len(coins) dp = [[amount+1] * (amount+1) for _ in range(n+1)] # 初始化为一个较大的值，如 +inf 或 amount+1 # 合法的初始化 dp[0][0] = 0 # 其他 dp[0][j]均不合法 # 完全背包：优化后的状态转移 for i in range(1, n+1): # 第一层循环：遍历硬币 for j in range(amount+1): # 第二层循环：遍历背包 if j < coins[i-1]: # 容量有限，无法选择第i种硬币 dp[i][j] = dp[i-1][j] else: # 可选择第i种硬币 dp[i][j] = min( dp[i-1][j], dp[i][j-coins[i-1]] + 1 ) ans = dp[n][amount] return ans if ans != amount+1 else -1 ``` ```python # 279.完全平方数 # 若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 class Solution: def numSquares(self, n: int) -> int: # 预处理出 <=sqrt(n) 的完全平方数 nums = [] i = 1 while i*i <= n: nums.append(i*i) i += 1 # 转化为完全背包问题【套用「322. 零钱兑换」】 target = n length = len(nums) dp = [[target+1] * (target+1) for _ in range(length+1)] # 初始化为一个较大的值，如 +inf 或 target+1 dp[0][0] = 0 # 合法的初始化；其他 dp[0][j]均不合法 # 完全背包：优化后的状态转移 for i in range(1, length+1): # 第一层循环：遍历nums for j in range(target+1): # 第二层循环：遍历背包 if j < nums[i-1]: # 容量有限，无法选择第i个数字 dp[i][j] = dp[i-1][j] else: # 可选择第i个数字 dp[i][j] = min( dp[i-1][j], dp[i][j-nums[i-1]] + 1 ) return dp[length][target] ``` 股票系列 ```python #R 1. 买卖股票的最佳时机 class Solution: def maxProfit(self, prices: List[int]) -> int: length = len(prices) if len == 0: return 0 dp = [[0] * 2 for _ in range(length)] dp[0][0] = -prices[0] dp[0][1] = 0 for i in range(1, length): dp[i][0] = max(dp[i-1][0], -prices[i]) dp[i][1] = max(dp[i-1][1], prices[i] + dp[i-1][0]) return dp[-1][1] ``` ```python #R 122.买卖股票的最佳时机II # 可以尽可能地完成更多的交易，不能同时参与多笔交易 class Solution: def maxProfit(self, prices: List[int]) -> int: length = len(prices) dp = [[0] * 2 for _ in range(length)] dp[0][0] = -prices[0] dp[0][1] = 0 for i in range(1, length): dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]) #注意这里是和121. 买卖股票的最佳时机唯一不同的地方 dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]) return dp[-1][1] ``` ```python #R 0 买卖股票的最佳时机含手续费 class Solution: def maxProfit(self, prices: List[int], fee: int) -> int: n = len(prices) dp = [[0] * 2 for _ in range(n)] dp[0][0] = -prices[0] #持股票 for i in range(1, n): dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]) dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i] - fee) return max(dp[-1][0], dp[-1][1]) ``` ```python #R 123.买卖股票的最佳时机III 最多可以完成 两笔 交易。 # 0 没有操作 （其实我们也可以不设置这个状态）； 1 第一次持有股票； 2 第一次不持有股票 class Solution: def maxProfit(self, prices: List[int]) -> int: if len(prices) == 0: return 0 dp = [[0] * 5 for _ in range(len(prices))] dp[0][1] = -prices[0] dp[0][3] = -prices[0] for i in range(1, len(prices)): dp[i][0] = dp[i-1][0] dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]) dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i]) dp[i][3] = max(dp[i-1][3], dp[i-1][2] - prices[i]) dp[i][4] = max(dp[i-1][4], dp[i-1][3] + prices[i]) return dp[-1][4] ``` ```python #R 188.买卖股票的最佳时机IV 最多可以完成 k 笔交易 class Solution: def maxProfit(self, k: int, prices: List[int]) -> int: if len(prices) == 0: return 0 dp = [[0] * (2*k+1) for _ in range(len(prices))] for j in range(1, 2*k, 2): dp[0][j] = -prices[0] for i in range(1, len(prices)): for j in range(0, 2*k-1, 2): dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j] - prices[i]) dp[i][j+2] = max(dp[i-1][j+2], dp[i-1][j+1] + prices[i]) return dp[-1][2*k] ``` ```python #R 1. 股票最佳买卖股票时机含冷冻期 class Solution: def maxProfit(self, prices: List[int]) -> int: if not prices: return 0 n = len(prices) # f[i][0]: 手上持有股票的最大收益 # f[i][1]: 手上不持有股票，并且处于冷冻期中的累计最大收益 # f[i][2]: 手上不持有股票，并且不在冷冻期中的累计最大收益 f = [[-prices[0], 0, 0]] + [[0] * 3 for _ in range(n - 1)] for i in range(1, n): f[i][0] = max(f[i - 1][0], f[i - 1][2] - prices[i]) f[i][1] = f[i - 1][0] + prices[i] f[i][2] = max(f[i - 1][1], f[i - 1][2]) return max(f[n - 1][1], f[n - 1][2]) ``` 子序列系列 ```python # 300.最长递增子序列 # 找到其中最长严格递增子序列的长度 class Solution: def lengthOfLIS(self, nums: List[int]) -> int: if len(nums) <= 1: return len(nums) dp = [1] * len(nums) result = 1 for i in range(1, len(nums)): for j in range(0, i): if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j] + 1) result = max(result, dp[i]) #取长的子序列 return result ``` ```python # 1. 最长连续递增序列 class Solution: def findLengthOfLCIS(self, nums: List[int]) -> int: if len(nums) == 0: return 0 result = 1 dp = [1] * len(nums) for i in range(len(nums)-1): if nums[i+1] > nums[i]: #连续记录 dp[i+1] = dp[i] + 1 result = max(result, dp[i+1]) return result ``` ```python # 1. 最长重复子数组 # 数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度==连续子序列 class Solution: def findLength(self, nums1: List[int], nums2: List[int]) -> int: # 创建一个二维数组 dp，用于存储最长公共子数组的长度 dp = [[0] * (len(nums2) + 1) for _ in range(len(nums1) + 1)] # 记录最长公共子数组的长度 result = 0 # 遍历数组 nums1 for i in range(1, len(nums1) + 1): # 遍历数组 nums2 for j in range(1, len(nums2) + 1): # 如果 nums1[i-1] 和 nums2[j-1] 相等 if nums1[i - 1] == nums2[j - 1]: # 在当前位置上的最长公共子数组长度为前一个位置上的长度加一 dp[i][j] = dp[i - 1][j - 1] + 1 # 更新最长公共子数组的长度 if dp[i][j] > result: result = dp[i][j] # 返回最长公共子数组的长度 return result ``` ```python # 1143.最长公共子序列 # 两个字符串的最长公共子序列的长度 class Solution: def longestCommonSubsequence(self, text1: str, text2: str) -> int: # 创建一个二维数组 dp，用于存储最长公共子序列的长度 dp = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)] # 遍历 text1 和 text2，填充 dp 数组 for i in range(1, len(text1) + 1): for j in range(1, len(text2) + 1): if text1[i - 1] == text2[j - 1]: # 如果 text1[i-1] 和 text2[j-1] 相等，则当前位置的最长公共子序列长度为左上角位置的值加一 dp[i][j] = dp[i - 1][j - 1] + 1 else: # 如果 text1[i-1] 和 text2[j-1] 不相等，则当前位置的最长公共子序列长度为上方或左方的较大值 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) # 返回最长公共子序列的长度 return dp[len(text1)][len(text2)] ``` ```python # 1035.不相交的线 # 连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且我们绘制的直线不与任何其他连线（非水平线）相交。 class Solution: def maxUncrossedLines(self, A: List[int], B: List[int]) -> int: dp = [[0] * (len(B)+1) for _ in range(len(A)+1)] for i in range(1, len(A)+1): for j in range(1, len(B)+1): if A[i-1] == B[j-1]: dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) return dp[-1][-1] ``` ```python # 1. 最大子序和 # 最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 class Solution: def maxSubArray(self, nums: List[int]) -> int: dp = [0] * len(nums) dp[0] = nums[0] result = dp[0] for i in range(1, len(nums)): dp[i] = max(dp[i-1] + nums[i], nums[i]) #状态转移公式 result = max(result, dp[i]) #result 保存dp[i]的最大值 return result ``` ```python # 392.判断子序列 # s 是否为 t 的子序列 class Solution: def isSubsequence(self, s: str, t: str) -> bool: dp = [[0] * (len(t)+1) for _ in range(len(s)+1)] for i in range(1, len(s)+1): for j in range(1, len(t)+1): if s[i-1] == t[j-1]: dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = dp[i][j-1] if dp[-1][-1] == len(s): return True return False ``` ```python #R 0 不同的子序列 # s 的子序列中 t 出现的个数 class Solution: def numDistinct(self, s: str, t: str) -> int: dp = [[0] * (len(t)+1) for _ in range(len(s)+1)] for i in range(len(s)): dp[i][0] = 1 for j in range(1, len(t)): dp[0][j] = 0 for i in range(1, len(s)+1): for j in range(1, len(t)+1): if s[i-1] == t[j-1]: dp[i][j] = dp[i-1][j-1] + dp[i-1][j] else: dp[i][j] = dp[i-1][j] return dp[-1][-1] ``` ```python # 1. 两个字符串的删除操作 # 每步可以删除任意一个字符串中的一个字符 class Solution: def minDistance(self, word1: str, word2: str) -> int: dp = [[0] * (len(word2)+1) for _ in range(len(word1)+1)] for i in range(len(word1)+1): dp[i][0] = i for j in range(len(word2)+1): dp[0][j] = j for i in range(1, len(word1)+1): for j in range(1, len(word2)+1): if word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = min(dp[i-1][j-1] + 2, dp[i-1][j] + 1, dp[i][j-1] + 1) return dp[-1][-1] ``` ```python # 1. 编辑距离 class Solution: def minDistance(self, word1: str, word2: str) -> int: dp = [[0] * (len(word2)+1) for _ in range(len(word1)+1)] for i in range(len(word1)+1): dp[i][0] = i for j in range(len(word2)+1): dp[0][j] = j for i in range(1, len(word1)+1): for j in range(1, len(word2)+1): if word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1 return dp[-1][-1] ``` ```python # 1. 回文子串 字符串中有多少个回文子串，dp[i][j] 表示子串s[i⋯j]是否是回文子串 class Solution: def countSubstrings(self, s: str) -> int: n = len(s) dp = [[False] * n for _ in range(n)] result = 0 for i in range(n): dp[i][i] = True result += 1 for i in range(n - 1, -1, -1): for j in range(i + 1, n): dp[i][j] = (s[i] == s[j]) and (j - i <= 1 or dp[i + 1][j - 1]) if dp[i][j]: result += 1 return result ``` ```python #R 0 最长回文子序列 class Solution: def longestPalindromeSubseq(self, s: str) -> int: dp = [[0] * len(s) for _ in range(len(s))] for i in range(len(s)): dp[i][i] = 1 for i in range(len(s)-1, -1, -1): for j in range(i+1, len(s)): if s[i] == s[j]: dp[i][j] = dp[i+1][j-1] + 2 else: dp[i][j] = max(dp[i+1][j], dp[i][j-1]) return dp[0][-1] ``` ```python #R 33.9 Wildcard Matching/通配符匹配 (Hard) # '?' 可以匹配任何单个字符。'*' 可以匹配任意字符序列（包括空字符序列）。 class Solution: def isMatch(self, s: str, p: str) -> bool: m, n = len(s), len(p) f = [[False] * (n + 1) for _ in range(m + 1)] # 初始条件：翻译自递归边界 # 对应边界 i<0 and j < 0 return True f[0][0] = True # 对应边界 i<0 j>=0的处理 for j in range(n): f[0][j + 1] = p[j] == '*' and f[0][j] # 对应边界 j<0 (f初始化已经赋值了False, 不用写) for i in range(m): for j in range(n): if s[i] == p[j] or p[j] == '?': f[i + 1][j + 1] = f[i][j] elif p[j] == '*': f[i + 1][j + 1] = f[i][j + 1] or f[i + 1][j] return f[m][n] ``` ```python # 64 Minimum Path Sum/最小路径和 (Medium) # dp[i][j] 的值代表直到走到 (i,j) 的最小路径和。 class Solution: def minPathSum(self, grid: [[int]]) -> int: for i in range(len(grid)): for j in range(len(grid[0])): if i == j == 0: continue elif i == 0: grid[i][j] = grid[i][j - 1] + grid[i][j] elif j == 0: grid[i][j] = grid[i - 1][j] + grid[i][j] else: grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j] return grid[-1][-1] ``` ```python #R 91 Decode Ways/解码方法 (Medium) # "12" 可以解码为 "AB"（1 2）或者 "L"（12） 时间复杂度O(n),空间复杂度O(n) class Solution: def numDecodings(self, s: str) -> int: size = len(s) #特判 if size == 0: return 0 dp = [0]*(size+1) dp[0] = 1 for i in range(1,size+1): t = int(s[i-1]) if t>=1 and t<=9: dp[i] += dp[i-1] #最后一个数字解密成一个字母 if i >=2:#下面这种情况至少要有两个字符 t = int(s[i-2])*10 + int(s[i-1]) if t>=10 and t<=26: dp[i] += dp[i-2]#最后两个数字解密成一个一个字母 return dp[-1] ``` ```python # 97 Interleaving String/交错字符串 (Medium) # dp[i][j] 表示 s1 的前 i 个字符和 s2的前 j 个字符是否能构成s3 的前 i+j 个字符 class Solution: def isInterleave(self, s1: str, s2: str, s3: str) -> bool: len1=len(s1) len2=len(s2) len3=len(s3) if(len1+len2!=len3): return False dp=[[False]*(len2+1) for i in range(len1+1)] dp[0][0]=True for i in range(1,len1+1): dp[i][0]=(dp[i-1][0] and s1[i-1]==s3[i-1]) for i in range(1,len2+1): dp[0][i]=(dp[0][i-1] and s2[i-1]==s3[i-1]) for i in range(1,len1+1): for j in range(1,len2+1): dp[i][j]=(dp[i][j-1] and s2[j-1]==s3[i+j-1]) or (dp[i-1][j] and s1[i-1]==s3[i+j-1]) return dp[-1][-1] ``` ```python # 152 Maximum Product Subarray/乘积最大子数组 (Medium) # 右端点下标为 i 的子数组的最大/小乘积 class Solution: def maxProduct(self, nums: List[int]) -> int: n = len(nums) f_max = [0] * n f_min = [0] * n f_max[0] = f_min[0] = nums[0] for i in range(1, n): x = nums[i] # 把 x 加到右端点为 i-1 的（乘积最大/最小）子数组后面， # 或者单独组成一个子数组，只有 x 一个元素 f_max[i] = max(f_max[i - 1] * x, f_min[i - 1] * x, x) f_min[i] = min(f_max[i - 1] * x, f_min[i - 1] * x, x) return max(f_max) ``` ```python # 198 House Robber (Easy) # 每个房屋存放金额的非负整数数组，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 class Solution: def rob(self, nums: List[int]) -> int: f = [0] * (len(nums) + 2) for i, x in enumerate(nums): f[i + 2] = max(f[i + 1], f[i] + x) return f[-1] ``` ```python # 221 Maximal Square/最大正方形 (Medium) # f[i][j]代表在matrix[i-1][j-1]处能构成的最大正方形 class Solution: def maximalSquare(self, matrix: List[List[str]]) -> int: m, n = len(matrix), len(matrix[0]) f = [[0 for _ in range(n + 1)] for _ in range(m + 1)] max_len = 0 for i in range(1, m + 1): for j in range(1, n + 1): if matrix[i - 1][j - 1] == "1": f[i][j] = ( min( f[i - 1][j], f[i][j - 1], f[i - 1][j - 1], ) + 1 ) max_len = max(max_len, f[i][j]) return max_len**2 ``` ```python #R 311.66 Burst Balloons/戳气球 (Medium) # nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> [] # 定义 f[i][j] 表示戳破区间 [i,j] 内的所有气球能得到的最多硬币数 class Solution: def maxCoins(self, nums: List[int]) -> int: n = len(nums) arr = [1] + nums + [1] f = [[0] * (n + 2) for _ in range(n + 2)] for i in range(n - 1, -1, -1): for j in range(i + 2, n + 2): for k in range(i + 1, j): f[i][j] = max(f[i][j], f[i][k] + f[k][j] + arr[i] * arr[k] * arr[j]) return f[0][-1] ``` ```python #R 377 Combination Sum IV/组合总和 Ⅳ (Medium) # 与39题不同之处，顺序不同的序列被视作不同的组合。 class Solution(object): def combinationSum4(self, nums, target): dp = [0] * (target + 1) dp[0] = 1 res = 0 for i in range(target + 1): for num in nums: if i >= num: dp[i] += dp[i - num] return dp[target] ``` ```python #H 0 Arithmetic Slices II - Subsequence/等差数列划分 II - 子序列 (Hard) # 所有等差子序列的数目 dp_ik=\sum_j^i-1 (dp_jk+1) 第一维用哈希表提高查询效率、节省空间 class Solution: def numberOfArithmeticSlices(self, nums: List[int]) -> int: n,ans=len(nums),0 dp=[defaultdict(int) for _ in range(n)] for i,num in enumerate(nums): for j in range(i): k=num-nums[j] dp[i][k]+=dp[j][k]+1 ans+=dp[j][k] return ans ``` ```python #H 0 Longest Arithmetic Subsequence/最长等差数列 (Medium) # 以 a[i] 结尾的最长等差子序列公差及其长度，存到一个哈希表dp(i)={d:L} class Solution: def longestArithSeqLength(self, a: List[int]) -> int: f = [{} for _ in range(len(a))] for i, x in enumerate(a): for j in range(i - 1, -1, -1): d = x - a[j] # 公差 if d not in f[i]: f[i][d] = f[j].get(d, 1) + 1 return max(max(d.values()) for d in f[1:]) ``` ```python #H 873 Length of Longest Fibonacci Subsequence/最长的斐波那契子序列的长度 (Medium) # 这f[x][y]代表了以数字x和y结尾的最大斐波那契序列长度。f[x][y]=f[y−x][x]+1 由于数据范围很大，用哈希表嵌套哈希表实现。 class Solution: def lenLongestFibSubseq(self, A: List[int]) -> int: dp = {} res = 0 tempA = set(A) for i in range(1,len(A)): for j in range(i): diff = A[i]-A[j] if diff int: if not s: return 0 dp = {} # 记录以某个字符结尾的最长连续子串长度 max_len = 0 # 当前连续子串长度 for i in range(len(s)): if i > 0 and (ord(s[i]) - ord(s[i-1]) == 1 or (s[i-1] == 'z' and s[i] == 'a')): max_len += 1 else: max_len = 1 dp[s[i]] = max(dp.get(s[i], 0), max_len) return sum(dp.values()) ``` ```python #R 688 Knight Probability in Chessboard/骑士在棋盘上的概率 (Medium) # dp[step][i][j]= 1/8 sum_di,dj dp[step−1][i+di][j+dj] class Solution: def knightProbability(self, n: int, k: int, row: int, column: int) -> float: dp = [[[0] * n for _ in range(n)] for _ in range(k + 1)] for step in range(k + 1): for i in range(n): for j in range(n): if step == 0: dp[step][i][j] = 1 else: for di, dj in ((-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2)): ni, nj = i + di, j + dj if 0 <= ni < n and 0 <= nj < n: dp[step][i][j] += dp[step - 1][ni][nj] / 8 return dp[k][row][column] ``` ```python # 740 Delete and Earn/删除并获得点数 (Medium) # 必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。返回你能通过这些操作获得的最大点数。 # 数组 sum 记录数组 nums 中所有相同元素之和，即 sum[x]=x⋅c_x class Solution: def deleteAndEarn(self, nums: List[int]) -> int: maxVal = max(nums) total = [0] * (maxVal + 1) for val in nums: total[val] += val def rob(nums: List[int]) -> int: size = len(nums) first, second = nums[0], max(nums[0], nums[1]) for i in range(2, size): first, second = second, max(first + nums[i], second) return second return rob(total) ``` ```python #R 877 Stone Game/石子游戏 (Medium) class Solution: def stoneGame(self, piles: List[int]) -> bool: N = len(piles) f = [[0]*(N+1) for _ in range(N+1)] # 防止出界 for l in range(N): for i in range(N-l): j = i+l f[i][j] = max(piles[i]-f[i+1][j], piles[j]-f[i][j-1]) return f[0][N-1]>0 ``` ```python # 0 Maximum Sum Circular Subarray/环形子数组的最大和 (Medium) # 分类讨论一：子数组没有跨过边界（在nums中间）。最大非空子数组和（力扣第53题) # 分类讨论二：子数组跨过边界（在nums两端）。其余元素和越小，子数组和越大。 class Solution: def maxSubarraySumCircular(self, nums: List[int]) -> int: max_s = -inf # 最大子数组和，不能为空 min_s = 0 # 最小子数组和，可以为空 max_f = min_f = 0 for x in nums: # 以 nums[i-1] 结尾的子数组选或不选（取 max）+ x = 以 x 结尾的最大子数组和 max_f = max(max_f, 0) + x max_s = max(max_s, max_f) # 最大遍历每个结尾 # 以 nums[i-1] 结尾的子数组选或不选（取 min）+ x = 以 x 结尾的最小子数组和 min_f = min(min_f, 0) + x min_s = min(min_s, min_f) if sum(nums) == min_s: return max_s return max(max_s, sum(nums) - min_s) ``` ```python #R 1000 Minimum Cost to Merge Stones/合并石头的最低成本 (Hard) # 每次移动需要将连续的k堆石头合并为一堆，成本为这k堆中石头的总数。 # 定义 f[i][j][k] 表示将 [i,j] 合并成k堆的最小成本 dp[i][j][k] = min(dp[i][m][1] + dp[m+1][j][k-1]) i≤m int: n = len(stones) if (n - 1) % (K-1): return -1 def get(i, j): return sums[j+1] - sums[i] dp = [[[float("inf")] * (K+1) for _ in range(n)] for _ in range(n)] sums = [0] * (1+n) for i in range(1, n+1): sums[i] = sums[i-1] + stones[i-1] for i in range(n): dp[i][i][1] = 0 for l in range(2, n+1): for i in range(n - l + 1): j = i + l - 1 for k in range(2, K+1): for m in range(i, j): dp[i][j][k] = min(dp[i][j][k], dp[i][m][1] + dp[m+1][j][k-1]) dp[i][j][1] = dp[i][j][K] + get(i, j) #合并成一堆特殊情况不可以从合并成0获得 return dp[0][n-1][1] ``` ```python # 0 Longest String Chain/? (Medium) # 返回 前身单词链的 最长可能长度 class Solution: def longestStrChain(self, words: List[str]) -> int: words.sort(key=len) f = {} # 不要用 defaultdict，这会在字符串不存在的时候插入字符串 for s in words: res = 0 for i in range(len(s)): # 枚举去掉 s[i] res = max(res, f.get(s[:i] + s[i + 1:], 0)) f[s] = res + 1 return max(f.values()) ``` ```python # 1186 Maximum Subarray Sum with One Deletion/删除一次得到子数组最大和 (Medium) # f[i][j] 表示子数组的右端点下标是i，j=不能/必须删除数字的情况下，子数组元素和的最大值。 ​class Solution: def maximumSum(self, arr: List[int]) -> int: f = [[-inf] * 2] + [[0, 0] for _ in arr] for i, x in enumerate(arr): f[i + 1][0] = max(f[i][0], 0) + x f[i + 1][1] = max(f[i][1] + x, f[i][0]) return max(max(r) for r in f) ``` ```python #R 1395 Count Number of Teams/统计作战单位数 (中等) # 3个士兵组成一个作战单位单调的作战单位的方案数。 # dp[i]记录的是第i个数之前比其值小的数的个数 class Solution: def numTeams(self, rating: List[int]) -> int: def func(nums): dp = [0] * len_ res = 0 for i in range(1, len_): idx = i - 1 while idx >= 0: if nums[i] > nums[idx]: dp[i] += 1 if dp[idx] > 0: res += dp[idx] idx -= 1 return res len_ = len(rating) return func(rating[::-1]) + func(rating) ``` # 其他 ```python #最大公约数 def gcd(a, b): while b: a, b = b, a % b return a ``` ```python #质因数分解 def prime_factors(n): factors = [] divisor = 2 while n > 1: while n % divisor == 0: factors.append(divisor) n //= divisor divisor += 1 return factors ``` ```python 29.除法 def divide(dividend, divisor): INT_MAX = 2**31 - 1 INT_MIN = -2**31 # 处理特殊情况 if divisor == 0: return INT_MAX if dividend == 0: return 0 # 判断结果的正负性 sign = 1 if (dividend < 0) ^ (divisor < 0): sign = -1 # 将被除数和除数都转为正数，以防止整数溢出 dividend, divisor = abs(dividend), abs(divisor) # 使用位运算逐步减去除数的倍数 result = 0 while dividend >= divisor: temp_divisor, multiple = divisor, 1 while dividend >= temp_divisor: dividend -= temp_divisor result += multiple # 左移一位相当于将除数翻倍 temp_divisor <<= 1 multiple <<= 1 # 根据结果的正负性返回最终值 result *= sign # 处理溢出情况 if result > INT_MAX: return INT_MAX elif result < INT_MIN: return INT_MIN else: return result ``` ```python 311.稀疏矩阵乘法 def multiply(A, B): # 确定 A 和 B 的行数和列数 rows_A, cols_A = len(A), len(A[0]) rows_B, cols_B = len(B), len(B[0]) # 初始化结果矩阵 C C = [[0] * cols_B for _ in range(rows_A)] # 遍历 A 的每个元素 for i in range(rows_A): for j in range(cols_A): # 如果 A 的元素不为 0，则遍历 B 对应列的元素进行乘法累加 if A[i][j] != 0: for k in range(cols_B): C[i][k] += A[i][j] * B[j][k] return C ``` ```python # ？a/b向0靠拢；a%b向-b或者b靠拢即a%b = a – (a/b)*b; 如果取余一定要 [0,n-1]，可以: (a%n + n) % n; ``` ```python # ？一堆string 转化成数字时，可以用map存储已经转化的string->number. 从左到右，先检验剩下的时候再map里，如果在 left*10^(right size)+right，else left = left*10 + 第i位，并存入map ``` ```python # K个字母构成长度为n的字符，相邻最多两个一样：a[n]最后两个不一样；b[n]最后两个一样；一共c[n]=a[n]+b[n].则a[n]=c[n]*(K-1);b[n]=a[n-1] ``` ```python # 0 ?/服务中心的最佳位置 (困难) # 到所有客户的欧几里得距离的总和最小 class Solution: def getMinDistSum(self, positions: List[List[int]]) -> float: n = len(positions) #### 梯度下降 Gradient Descent GD, 也可以尝试批量梯度下降，Batch Gradient Descent, BGD epoches = 10 ** 5 #迭代次数 eps = 1e-7 #epsilon 浮点小相对误差限 lr = 1.11 #学习率 learning rate decay = 0.003 #学习率的衰减率 def dist(xc, yc): #中心点[xc,yc]到所有点的距离之和 res = 0.0 for x, y in positions: res += ((x-xc)**2 + (y-yc)**2) ** 0.5 return res xc = sum(p[0] for p in positions) / n yc = sum(p[1] for p in positions) / n for epoc in range(epoches): dx = 0.0 dy = 0.0 for x, y in positions: dx += (xc-x) / ( ((xc-x)**2 + (yc-y)**2) ** 0.5 + eps ) dy += (yc-y) / ( ((xc-x)**2 + (yc-y)**2) ** 0.5 + eps ) xc_pre, yc_pre = xc, yc xc -= dx * lr yc -= dy * lr lr *= (1.0 - decay) delta = ((xc-xc_pre)**2 + (yc-yc_pre)**2) ** 0.5 if delta < eps: break return dist(xc, yc) ``` ```python # 1779 ?/找到最近的有相同 X 或 Y 坐标的点 (简单) # 返回距离你当前位置 曼哈顿距离 最近 class Solution: def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int: ans, mi = -1, inf for i, (a, b) in enumerate(points): if a == x or b == y: d = abs(a - x) + abs(b - y) if mi > d: ans, mi = i, d return ans ``` ```python # 1049.9 Actors and Directors Who Cooperated At Least Three Times * $/? (Easy) import pandas as pd def actors_and_directors(actor_director: pd.DataFrame) -> pd.DataFrame: # 使用 groupby 和 count 函数对 actor_id 和 director_id 进行分组计数 counts = actor_director.groupby(['actor_id', 'director_id']).size().reset_index(name='count') # 从计数结果中筛选出合作次数大于等于3次的组合 result = counts[counts['count'] >= 3][['actor_id', 'director_id']] return result ``` --------------------------------------------- # 难题 ```python # 218 The Skyline Problem/天际线问题 (Hard) # 分治！时间复杂度为：nlog(n) class Solution: def getSkyline(self, buildings): if not buildings: return [] if len(buildings) == 1: return [[buildings[0][0], buildings[0][2]], [buildings[0][1], 0]] mid = len(buildings) // 2 left = self.getSkyline(buildings[:mid]) right = self.getSkyline(buildings[mid:]) return self.merge(left, right) def merge(self, left, right): # 记录目前左右建筑物的高度 lheight = rheight = 0 # 位置 l = r = 0 # 输出结果 res = [] while l < len(left) and r < len(right): if left[l][0] < right[r][0]: # current point cp = [left[l][0], max(left[l][1], rheight)] lheight = left[l][1] l += 1 elif left[l][0] > right[r][0]: cp = [right[r][0], max(right[r][1], lheight)] rheight = right[r][1] r += 1 # 相等情况 else: cp = [left[l][0], max(left[l][1], right[r][1])] lheight = left[l][1] rheight = right[r][1] l += 1 r += 1 # 和前面高度比较，不一样才加入 if len(res) == 0 or res[-1][1] != cp[1]: res.append(cp) # 剩余部分添加进去 res.extend(left[l:] or right[r:]) return res ``` ```python # 849.9 Rectangle Area II/矩形面积 II (Hard) # 线段树 + 扫描线 太难了 ``` ```python class MyCalendarTwo: #线段树方法hard def __init__(self): self.tree = {} def update(self, start: int, end: int, val: int, l: int, r: int, idx: int) -> None: if r < start or end < l: return if start <= l and r <= end: p = self.tree.get(idx, [0, 0]) p[0] += val p[1] += val self.tree[idx] = p return mid = (l + r) // 2 self.update(start, end, val, l, mid, 2 * idx) self.update(start, end, val, mid + 1, r, 2 * idx + 1) p = self.tree.get(idx, [0, 0]) p[0] = p[1] + max(self.tree.get(2 * idx, (0,))[0], self.tree.get(2 * idx + 1, (0,))[0]) self.tree[idx] = p def book(self, start: int, end: int) -> bool: self.update(start, end - 1, 1, 0, 10 ** 9, 1) if self.tree[1][0] > 2: self.update(start, end - 1, -1, 0, 10 ** 9, 1) return False return True ``` ```python # 2663 Lexicographically Smallest Beautiful String/字典序最小的美丽字符串 (困难) hd # 返回一个长度为n的美丽字符串，该字符串还满足：在字典序大于 s 的所有美丽字符串中字典序最小。 # 1 不能出现 s[i]=s[i−1] 以及 s[i]=s[i−2]; 2 小写字母表的前k个字母组成;3 修改的位置越靠右越好。s 视作一个 k 进制数，不停地末尾加一 class Solution: def smallestBeautifulString(self, s: str, k: int) -> str: a = ord('a') k += a s = list(map(ord, s)) #将字符串s转换为ASCII码列表 n = len(s) i = n - 1 # 从最后一个字母开始 s[i] += 1 # 先加一 while i < n: if s[i] == k: # 需要进位 if i == 0: # 无法进位 return "" # 进位 s[i] = a i -= 1 s[i] += 1 elif i and s[i] == s[i - 1] or i > 1 and s[i] == s[i - 2]: s[i] += 1 # 如果 s[i] 和左侧的字符形成回文串，就继续增加 s[i] else: i += 1 # 反过来检查后面是否有回文串 return ''.join(map(chr, s)) ``` ```python # 0 Optimal Account Balancing $/最优账单平衡 (Hard) # 输入： [[0,1,10],[2,0,5]]，0 给 1 $10 ； 2 给 0 $5 。 输出：2 # 我们应该将这些人分成尽可能多的合计总金额为0的组。我们可以使用状态压缩动态规划，通过枚举子集的方式来进行求解。 # 令dp[state]表示state所对应的这组人所能够分成的最多的组数。注意我们只有在sum[state]=0的情况下才去枚举state的子集。 # 转移方程为dp[state]=max_{sub⫋state} (dp[sub])+1。最后的答案就是n−dp[2^n −1]，其中n是总金额不为0的人数。 class Solution: def minTransfers(self, transactions: List[List[int]]) -> int: from collections import defaultdict # 第一步：计算每个人的净余额 balance = defaultdict(int) for sender, receiver, amount in transactions: balance[sender] += amount # 发送者的余额增加 balance[receiver] -= amount # 接收者的余额减少 # 第二步：筛选出余额不为零的人 v = [account for account in balance.values() if account != 0] n = len(v) # 非零余额的数量 # 第三步：计算所有子集的余额和 sum_ = [0] * (1 << n) # 初始化大小为 2^n 的 sum_ 数组 for i in range(1, 1 << n): for j in range(n): if i & (1 << j): # 如果子集中包含第 j 个人 sum_[i] = sum_[i ^ (1 << j)] + v[j] # 更新该子集的余额和 break # 第四步：初始化动态规划数组 dp = [0] * (1 << n) for i in range(1, 1 << n): if sum_[i] != 0: # 如果子集的余额和不为零，跳过 continue dp[i] = 1 # 初始至少需要一次转账 # 寻找子集的子掩码 si = (i - 1) & i # 使用 si 变量来存放当前子集的子掩码 while si: # 当 si 不为零时继续 if dp[si]: # 仅考虑有效的子掩码 dp[i] = max(dp[i], dp[si] + 1) # 更新当前子集的最大转账次数 si = (si - 1) & i # 获取下一个子掩码 # 最终结果是总人数减去能消除的转账数量 return n - dp[(1 << n) - 1] # dp[(1 << n) - 1] 表示所有人的组合 ``` ```python # 643.99 Maximum Average Subarray II $/子数组最大平均数 II (Hard) # 找出长度大于等于 k 最大平均值的连续子数组的平均值。计算误差小于 10-5。 # 判断avg是大于还是小于答案，用累加和技巧计算长度大于等于 k的区间 class Solution: def findMaxAverage(self, nums: List[int], k: int) -> float: def check(avg): # 如果是求长度等于 k 的区间的区间和：使用滑动窗口，维护首尾前缀和（见643.最大平均子段和） # 这一题是大于等于 k 。 我们需要知道以 end 结尾，长度大于等于 k 的区间中最大的区间和 # 多维护一个 start_sum 的最小值即可。 end_sum - min_sum 即为所求区间和最大值 end_sum = sum(num - avg for num in nums[:k]) start_sum = min_start_sum = 0 for end in range(k, len(nums)): if end_sum >= min_start_sum: return True end_sum += nums[end] - avg start_sum += nums[end-k] - avg min_start_sum = min(min_start_sum, start_sum) return end_sum >= min_start_sum # 二分法 l, r = min(nums), max(nums) while r - l > 1e-5: mid = (l+r) / 2 if check(mid): # 存在符合条件的区间，其平均值大于等于 mid，下界向上收缩 l = mid else: r = mid return l ```