admin/coding
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
coding/coding3.md

2226 lines
82 KiB
Markdown
Raw Permalink Normal View History

添加 coding3.md
2025-06-26 12:46:42 +00:00
# 回溯算法
组合
```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 <A[j] and diff in tempA:
dp[(A[j],A[i])] = dp.get((diff,A[j]),2)+1
res = max(res,dp[(A[j],A[i])])
return res
```
```python
#R 467 Unique Substrings in Wraparound String/环绕字符串中唯一的子字符串 (Medium) 字符串 s = "zab" 有六个子字符串 ("z", "a", "b", "za", "ab", and "zab") 在 base 中
# dp[i] 表示以 s[i] 结尾的最长连续有效子串的长度。
class Solution:
def findSubstringInWraproundString(self, s: str) -> 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<j
def mergeStones(self, stones: List[int], K: int) -> 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
```
Reference in New Issue Copy Permalink