链表
LC160.相交链表
题解： 参考灵茶山艾府题解
1# Definition for singly-linked list.
2# class ListNode:
3# def __init__(self, x):
4# self.val = x
5# self.next = None
6
7class Solution:
8 def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
9 p1 = headA
10 p2 = headB
11 while p1 is not p2:
12 p1 = p1.next if p1 else headB
13 p2 = p2.next if p2 else headA
14 return p1
核心思想是两条链表满足 $(x+z)+y = (y+z)+x$，z为公共部分的长度
树
LC236.二叉树的最近公共祖先
题解：
1# Definition for a binary tree node.
2# class TreeNode:
3# def __init__(self, x):
4# self.val = x
5# self.left = None
6# self.right = None
7
8class Solution:
9 def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
10 if root in (None, p, q):
11 return root
12 left = self.lowestCommonAncestor(root.left,p,q)
13 right = self.lowestCommonAncestor(root.right,p,q)
14 if left and right:
15 return root
16 return left or right
LC437.路径总和II
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 题解：
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def pathSum(self, root, targetSum):
9 ans = []
10 path = []
11 def dfs(node, target):
12 if node is None:
13 return
14 target-=node.val
15 path.append(node.val)
16 if node.left is None and node.right is None and target==0:
17 ans.append(path.copy())
18 else:
19 dfs(node.left, target)
20 dfs(node.right, target)
21 path.pop()
22 dfs(root, targetSum)
23 return ans
LC236.二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 题解：临界条件：当前节点是空/p/q
如果左右子树都找到了，返回当前节点，如果只有左子树有结果，返回递归左子树的结果，相反返回右子树的递归结果。
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
9 def dfs(node, p, q):
10 if node is p or node is q or node is None:
11 return node
12 left = dfs(node.left, p, q)
13 right = dfs(node.right, p, q)
14 if left and right:
15 return node
16 return left or right
17 return dfs(root, p, q)
LC543.二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。 题解：对于每个节点，计算左右子树的深度，更新答案为左右子树深度之和
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
9 ans = 0
10 def dfs(node):
11 if node is None:
12 return -1
13 left = dfs(node.left)+1
14 right = dfs(node.right)+1
15 nonlocal ans
16 ans = max(ans, left+right)
17 return max(left, right)
18 dfs(root)
19 return ans
LC124.二叉树中的最大路径和
给定一个非空二叉树，返回其最大路径和。 题解：
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def maxPathSum(self, root: Optional[TreeNode]) -> int:
9 ans = -inf
10 def dfs(node):
11 nonlcoal ans
12 if node is None:
13 return 0
14 left = dfs(node.left)
15 right = dfs(node.right)
16 ans = max(ans, left+right+node.val)
17 return max(max(left, right)+node.val, 0)
18 dfs(root)
19 return ans
LC199.二叉树的右视图
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
题解：层序遍历，每次取每一层的最后一个节点。
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 # DFS先递归右子树
9 def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
10 ans = []
11 def dfs(node, depth):
12 if node is None:
13 return
14 if len(ans)==depth:
15 ans.append(node.val)
16 dfs(node.right, depth+1)
17 dfs(node.left, depth+1)
18 dfs(root, 0)
19 return ans
20 # BFS层序遍历
21 def rightSideViewBFS(self, root: Optional[TreeNode]) -> List[int]:
22 ans = []
23 if root is None: return ans
24 q = [root]
25 while q:
26 ans.append(q[-1].val)
27 tmp = q
28 q = []
29 for node in tmp:
30 if node.left: q.append(node.left)
31 if node.right: q.append(node.right)
32 return ans
LC105. 从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历，inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
题解：递归
1class TreeNode:
2 def __init__(self, val = 0, left = None, right = None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
9 if not preorder and not inorder:
10 return None
11 for i,x in enumerate(inorder):
12 if x==preorder[0]: break
13 left = self.buildTree(preorder[1:1+i], inorder[:i])
14 right = self.buildTree(preorder[1+i:], inorder[i+1:])
15 return TreeNode(val = preorder[0], left = left, right =right)
矩阵
LC54. 螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
题解：模拟，标记
1class Solution:
2 def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
3 m, n = len(matrix), len(matrix[0])
4 directions = [(0,1),(1,0),(0,-1),(-1,0)]
5 x = y = idx = 0
6 ans = []
7 vis = [[False]*n for _ in range(m)]
8 for _ in range(m*n):
9 ans.append(matrix[x][y])
10 vis[x][y] = True
11 i,j = x+directions[idx%4][0], y+directions[idx%4][1]
12 if i<0 or i>=m or j<0 or j>=n or vis[i][j]:
13 idx+=1
14 x,y = x+directions[idx%4][0], y+directions[idx%4][1]
15 return ans
LC48. 旋转图像
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
题解：
1class Solution:
2 def rotate(self, matrix: List[List[int]]) -> None:
3 m, n = len(matrix), len(matrix[0])
4 for i in range(m):
5 for j in range(i):
6 matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
7
8 for row in matrix:
9 row = row.reverse()
滑动窗口
LC3. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
题解：
1class Solution:
2 def lengthOfLongestSubstring(self, s: str) -> int:
3 cnt = defaultdict(int)
4 ans = 0
5 left = 0
6 for i, c in enumerate(s):
7 cnt[c]+=1
8 while cnt[c]>1:
9 cnt[s[left]]-=1
10 if cnt[s[left]]==0: cnt.pop(s[left])
11 left+=1
12 ans = max(ans, i-left+1)
13 return ans
LC438. 找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
题解：
1class Solution:
2 def findAnagrams(self, s: str, p: str) -> List[int]:
3 target = Counter(p)
4 cnt = Counter()
5 left = 0
6 ans = []
7 for i, c in enumerate(s):
8 cnt[c]+=1
9 while cnt>target:
10 cnt[s[left]]-=1
11 if cnt[s[left]]==0: cnt.pop(s[left])
12 left+=1
13 if cnt==target: ans.append(left)
14 return ans
LC560. 和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
题解：哈希表+前缀和，两数之和的变体
1class Solution:
2 def subarraySum(self, nums: List[int], k:int) -> int:
3 n = len(nums)
4 presum = [0]*(n+1)
5 for i in range(n):
6 presum[i+1] = presum[i]+nums[i]
7 left, ans = 0, 0
8 cnt = defaultdict(int)
9 for i, x in enumerate(presum):
10 if x-k in cnt:
11 ans+=cnt[x-k]
12 cnt[x]+=1
13 return ans
LC239. 滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。
题解：使用单调队列存储窗口内的值
1class Solution:
2 def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
3 n = len(nums)
4 ans = [0]*(n-k+1)
5 st = deque()
6 for i, num in enumerate(nums):
7 while st and nums[st[-1]]<=num:
8 st.pop()
9 st.append(i)
10 left = i-k+1
11 if left > st[0]:
12 st.popleft()
13 if left>=0:
14 ans[left] = nums[st[0]]
15 return ans
LC76. 最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
题解：滑动窗口，在循环内更新
1class Solution:
2 def minWindow(self, s: str, t: str) -> str:
3 target = Counter(t)
4 cnt = Counter()
5 left, minlen = 0, inf
6 ans = ""
7 for i,c in enumerate(s):
8 cnt[c]+=1
9 while cnt and cnt>=target:
10 if i-left+1<minlen:
11 ans = s[left:i+1]
12 minlen = i-left+1
13 cnt[s[left]]-=1
14 if cnt[s[left]]==0: cnt.pop(s[left])
15 left+=1
16 return ans
双指针
LC15.三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
题解：
1
2class Solution:
3 def threeSum(self, nums: list[int]) -> list[list[int]]:
4 nums.sort()
5 n = len(nums)
6 ans = []
7 for i in range(n-2):
8 x = nums[i]
9 if i>0 and x==nums[i-1]:
10 continue
11 if x+nums[i+1]+nums[i+2]>0:
12 break
13 if x+nums[-2]+nums[-1]<0:
14 continue
15 left = i+1
16 right = n-1
17 while left<right:
18 s = nums[i]+nums[left]+nums[right]
19 if s<0:
20 left+=1
21 elif s>0:
22 right-=1
23 else:
24 ans.append([x, nums[left], nums[right]])
25 left+=1
26 while left<right and nums[left-1]==nums[left]:
27 left+=1
28 right-=1
29 while left<right and nums[right+1]==nums[right]:
30 right-=1
31 return ans
LC42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
题解：
1class Solution:
2 # 对于每个柱子，找左边的最大值和右边的最大值，较小的最大值为这个柱子的液面的高度，减去柱子本身的高度即为面积
3 def trap(self, height: List[int]) -> int:
4 n = len(height)
5 pre_max = [0]*n
6 pre_max[0] = height[0]
7 for i in range(1,n):
8 pre_max[i] = max(height[i], pre_max[i-1])
9 suf_max = [0]*n
10 suf_max[-1] = height[-1]
11 for i in range(n-2,-1,-1):
12 suf_max[i] = max(height[i], suf_max[i+1])
13 ans = 0
14 for i,h in enumerate(height):
15 ans+=min(suf_max[i], pre_max[i])-h
16 return ans
17
18 def trap(self, height: List[int]) -> int:
19 ans = pre_max = suf_max = 0
20 left, right = 0, len(height)-1
21 while left<right:
22 pre_max = max(pre_max, height[left])
23 suf_max = max(suf_max, height[right])
24 if pre_max<suf_max:
25 ans+=pre_max-height[left]
26 left+=1
27 else:
28 ans+=suf_max-height[right]
29 right-=1
30 return ans
31
32 # 用单调栈，横着计算面积
33 def trap(self, height: List[int]) -> int:
34 ans = 0
35 st = []
36 for i,h in enumerate(height):
37 while st and height[st[-1]]<=h:
38 bottom_h = height[st.pop()]
39 if not st:
40 break
41 left = st[-1]
42 dh = min(height[left], h)-bottom_h
43 ans+=dh*(i-left-1)
44 st.append(i)
45 return ans
LC75. 颜色分类
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
题解：维护数组中0的个数p0以及0和1的个数p1,将nums[p0]=0,nums[p1]=1
1class Solution:
2 def sortColors(self, nums: List[int]) -> None:
3 p0 = p1 = 0
4 for i, x in enumerate(nums):
5 nums[i]=2
6 if x<=1:
7 nums[p1]=0
8 p1+=1
9 if x==0:
10 nums[p0]=1
11 p0+=1
回溯
LC46.全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
题解：枚举位置，选填数字，把path看成N个位置，每个位置都有N种选法，但是要注意已经选过的数字不能再选。每一层递归负责填path[i]
1class Solution:
2 def permute(self, nums: List[int]) -> List[List[int]]:
3 n = len(nums)
4 ans = []
5 path = [0]*n
6 visited = [False]*n
7 def dfs(i):
8 if i==n:
9 ans.append(path.copy())
10 return
11 for j, v in enumerate(visited):
12 if not v:
13 visited[j] = True
14 path[i] = nums[j]
15 dfs(i+1)
16 visited[j] = False
17 dfs(0)
18 return ans
LC78.子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
题解：选或不选
1class Solution:
2 def subsets(self, nums: List[int]) -> List[List[int]]:
3 n = len(nums)
4 path = []
5 ans = []
6 def dfs(i):
7 if i==n:
8 ans.append(path.copy())
9 return
10
11 # 不选nums[i]
12 dfs(i+1)
13
14 # 选nums[i]
15 path.append(nums[i])
16 dfs(i+1)
17 path.pop()
18
19 dfs(0)
20 return ans
LC17.电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 题解：
1class Solution:
2 def letterCombinations(self, digits: str) -> List[str]:
3 mps = {'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
4 n = len(digits)
5 path = ['']*n
6 ans = []
7 def dfs(i):
8 if i==n:
9 ans.append(''.join(path))
10 return
11 for c in mps[digits[i]]:
12 path[i] = c
13 dfs(i+1)
14 dfs(0)
15 return ans
16
LC22.括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 题解：
1class Solution:
2 def generateParenthesis(self, n: int) -> List[str]:
3 path = ['']*(2*n)
4 ans = []
5 def dfs(l, r):
6 if r==n:
7 ans.append(''.join(path))
8 return
9 if l<n:
10 path[l+r] = '('
11 dfs(l+1, r)
12 if r<l:
13 path[l+r] = ')'
14 dfs(l, r+1)
15 dfs(0,0)
16 return ans
LC.39 组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
题解：选或不选
1class Solution:
2 def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
3 n = len(candidates)
4 path = []
5 ans = []
6 def dfs(i, t):
7 if t==0:
8 ans.append(path.copy())
9 return
10 if i<0 or t<0:
11 return
12 # 不选
13 dfs(i-1, t)
14 # 选
15 path.append(candidates[i])
16 dfs(i, t-candidates[i])
17 path.pop()
18 dfs(n-1, target)
19 return ans
图论
LC207.课程表
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false。
题解：
1class Solution:
2 def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
3 g = [[] for _ in range(numCourses)]
4 for a, b in prerequisites:
5 g[b].append(a)
6 colors = [0]*numCourses
7 # 返回True表示有环
8 # 1表示正在访问，2表示访问完成，0表示未访问
9 def dfs(i):
10 colors[i] = 1
11 for j in g[i]:
12 if colors[j]==1:
13 return True
14 if colors[j]==0 and dfs(j):
15 return True
16 colors[i] = 2
17 return False
18 for i, c in enumerate(colors):
19 if c==0 and dfs(i):
20 return False
21 return True
LC200.岛屿数量
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
题解：DFS
1class Solution:
2 def numIslands(self, grid: List[List[str]]) -> int:
3 m,n = len(grid), len(grid[0])
4 ans = 0
5 def dfs(i,j):
6 grid[i][j]='2'
7 for x,y in (i+1,j),(i-1,j),(i,j+1),(i,j-1):
8 if 0<=x<m and 0<=y<n and grid[x][y]=='1':
9 dfs(x,y)
10
11 for i in range(m):
12 for j in range(n):
13 if grid[i][j]=='1':
14 ans+=1
15 dfs(i,j)
16 return ans
LC994.腐烂的橘子
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一： 值 0 代表空单元格； 值 1 代表新鲜橘子； 值 2 代表腐烂的橘子。 每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。 返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
题解：BFS
1class Solution:
2 def orangesRotting(self, grid: List[List[int]]) -> int:
3 m,n = len(grid), len(grid[0])
4 cnt = 0
5 q = []
6 ans = 0
7 for i in range(m):
8 for j in range(n):
9 if grid[i][j]==1:
10 cnt+=1
11 if grid[i][j]==2:
12 q.append((i,j))
13 while q and cnt:
14 ans+=1
15 tmp = q
16 q = []
17 for i,j in tmp:
18 for x, y in (i-1,j),(i+1,j),(i,j-1),(i,j+1):
19 if 0<=x<m and 0<=y<n and grid[x][y]==1:
20 grid[x][y]=2
21 q.append((x,y))
22 cnt-=1
23
24 return -1 if cnt else ans
动态规划
LC198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个整数数组 nums ，表示一个环形街道上沿街的房屋，每个房屋内都藏有一定的现金。你不能同时偷窃相邻的两间房屋，否则会触发报警。
题解：
1class Solution:
2 # 递推
3 def rob(self, nums: List[int]) -> int:
4 n = len(nums)
5 if n==1: return nums[0]
6 f = [0]*n
7 f[0] = nums[0]
8 f[1] = max(nums[1], nums[0])
9 for i in range(2, n):
10 f[i] = max(nums[i]+f[i-2], f[i-1])
11 return f[-1]
12
13 # 记忆化递归
14 def rob(self, nums: List[int]) -> int:
15 n = len(nums)
16 if n==1: return nums[0]
17 @cache
18 def dfs(i):
19 if i==0: return nums[0]
20 if i==1: return max(nums[0], nums[1])
21 return max(nums[i]+dfs(i-2), dfs(i-1))
22 return dfs(n-1)
LC337.打家劫舍III
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。 除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。 给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
题解: 树形DP，对每个节点，选或不选
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def rob(self, root: Optional[TreeNode]) -> int:
9 @cache
10 def dfs(node):
11 if node is None:
12 return 0, 0
13 l_rob, l_norob = dfs(node.left)
14 r_rob, r_norob = dfs(node.right)
15 rob = l_norob + r_norob + node.val
16 norob = max(l_rob, l_norob) + max(r_rob, r_norob)
17 return rob, norob
18
19 return max(dfs(root))
LC64. 最小路径和
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 说明：每次只能向下或者向右移动一步。
题解：
1class Solution:
2 def minPathSum(self, grid: List[List[int]]) -> int:
3 m,n = len(grid), len(grid[0])
4 @cache
5 def dfs(i,j):
6 if i==0 and j==0: return grid[i][j]
7 if i==0: return dfs(i, j-1)+grid[i][j]
8 if j==0: return dfs(i-1, j)+grid[i][j]
9 return min(dfs(i-1, j), dfs(i, j-1))+grid[i][j]
10 return dfs(m-1, n-1)
LC72. 编辑距离
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作： 插入一个字符 删除一个字符 替换一个字符
题解：
1class Solution:
2 # 递推
3 def minDistance(self, word1: str, word2: str) -> int:
4 m,n = len(word1), len(word2)
5 f = [[0]*(n+1) for _ in range(m+1)]
6 for i in range(m+1):
7 f[i][0] = i
8 for j in range(n+1):
9 f[0][j] = j
10 for i in range(m):
11 for j in range(n):
12 if word1[i]==word2[j]:
13 f[i+1][j+1] = f[i][j]
14 else:
15 f[i+1][j+1] = min(f[i][j], f[i][j+1], f[i+1][j])+1
16 return f[-1][-1]
17
18 # 记忆化递归
19 def minDistance(self, word1: str, word2: str) -> int:
20 m,n = len(word1), len(word2)
21 @cache
22 def dfs(i,j):
23 if i==0: return j
24 if j==0: return i
25 if word1[i-1]==word2[j-1]:
26 return dfs(i-1, j-1)
27 else:
28 return min(dfs(i-1,j-1), dfs(i,j-1), dfs(i-1,j))+1
29 return dfs(m,n)
LC279. 完全平方数
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
题解：选或不选
1@cache
2def dfs(i, j):
3 if j==0:
4 return inf if i else 0
5 if j*j>i:
6 return dfs(i, j-1)
7 return min(dfs(i-j*j, j)+1, dfs(i, j-1))
8
9class Solution:
10 def numSquares(self, n):
11 return dfs(n, isqrt(n))
LC322. 零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。 你可以认为每种硬币的数量是无限的。
题解：
1class Solution:
2 # 记忆化递归：选或不选
3 def coinChange(self, coins: List[int], amount: int) -> int:
4 n = len(coins)
5 @cache
6 def dfs(i, target):
7 if i<0:
8 if target==0: return 0
9 else:
10 return inf
11 if target<coins[i]:
12 return dfs(i-1, target)
13 return min(dfs(i, target-coins[i])+1, dfs(i-1, target))
14 ans = dfs(n-1, amount)
15 return ans if ans < inf else -1
16
17 # 递推
18 def coinChange(self, coins: List[int], amount: int) -> int:
19 n = len(coins)
20 f = [[inf]*(amount+1) for _ in range(n+1)]
21 f[0][0] = 0
22 for i in range(n):
23 for j in range(amount+1):
24 if j<coins[i]:
25 f[i+1][j] = f[i][j]
26 else:
27 f[i+1][j] = min(f[i][j], f[i+1][j-coins[i]]+1)
28 ans = f[-1][-1]
29 return ans if ans<inf else -1
LC494. 目标和
给你一个非负整数数组 nums 和一个整数 target 。 你可以向数组中的每个整数添加 ‘+’ 或 ‘-’ ，并串联起所有整数，来构造一个表达式 返回可以达到目标和的不同表达式的数目。
题解：
1class Solution:
2 def findTargetSumWays(self, nums: List[int], target: int) -> int:
3 s = sum(nums)-abs(target)
4 if s<0 or s%2:
5 return 0
6 @cache
7 def dfs(i, left):
8 if i<0:
9 return 1 if left==0 else 0
10 if left<nums[i]:
11 return dfs(i-1, left)
12 return dfs(i-1, left)+dfs(i-1, left-nums[i])
13 return dfs(len(nums)-1, s//2)
LC300. 最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
题解：
1class Solution:
2 def lengthOfLIS(self, nums: List[int]) -> int:
3 n = len(nums)
4 @cache
5 def dfs(i):
6 if i==0: return 1
7 max_len = 1
8 for j in range(0, i):
9 if nums[j]<nums[i]:
10 max_len = max(max_len, dfs(j)+1)
11 return max_len
12
13 return max(dfs(i) for i in range(n))
14
15 # 贪心+二分
16 def lengthOfLIS(self, nums: List[int]) -> int:
17 g = []
18 for x in nums:
19 j = bisect_left(g, x)
20 if j == len(g):
21 g.append(x)
22 else:
23 g[j] = x
24 return len(g)
LC152. 乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。 测试用例的答案是一个 32-位 整数。 子数组 是数组的连续子序列。
题解：
1class Solution:
2 def maxProduct(self, nums: List[int]) -> int:
3 max_res = min_res = 1
4 ans = -inf
5 for x in nums:
6 max_res, min_res = max(max_res*x, min_res*x, x), min(max_res*x, min_res*x, x)
7 ans = max(ans, max_res)
8 return ans
9
LC139. 单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
题解：递归
1class Solution:
2 def wordBreak(self, s: str, wordDict: List[str]) -> bool:
3 max_len = -inf
4 for word in wordDict:
5 max_len = max(max_len, len(word))
6 words = set(wordDict)
7 @cache
8 def dfs(i):
9 if i==0:
10 return True
11 for j in range(i-1, max(i-max_len-1, -1), -1):
12 if s[j:i] in words and dfs(j):
13 return True
14 return False
15 return dfs(len(s))
贪心
LC581.最短无序连续子数组
给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。 请你找出符合题意的 最短 子数组，并输出它的长度。
题解:从左到右遍历，通过维护最大值找到最后一个下降的点，该点即为right。遍历完，最后一个right即为乱序区间的右边界，right右边是非递减区间 同理，从右到左遍历，通过维护最小值找到最后一个上升的点，该点即为left。left左边是非递减区间 [left,right]即为题目中的乱序区间
1class Solution:
2 def findUnsortedSubarray(self, nums: List[int]) -> int:
3 n = len(nums)
4 right, left = 0, n-1
5 pre_max, suf_min = nums[0], nums[-1]
6 for i in range(n):
7 if nums[i]>=pre_max:
8 pre_max = nums[i]
9 else:
10 right = i
11 if nums[n-i-1]<=suf_min:
12 suf_min = nums[n-i-1]
13 else:
14 left = n-i-1
15 return 0 if right == 0 else right-left+1
LC56. 合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
题解：先按照区间左端点排序，然后维护一个当前区间[left, right]，如果下一个区间的左端点在当前区间内，则更新当前区间的右端点为两者右端点的较大值；如果下一个区间的左端点在当前区间外，则说明当前区间已经结束，将其加入答案，并将下一个区间作为新的当前区间
1class Solution:
2 def merge(self, intervals: List[List[int]]) -> List[List[int]]:
3 intervals = sorted(intervals, key=lambda x: x[0])
4 ans = []
5 for p in intervals:
6 if ans and p[0]<= ans[-1][1]:
7 ans[-1][1] = max(ans[-1][1], p[1])
8 else:
9 ans.append(p)
10 return ans
LC55. 跳跃游戏
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
题解：维护最远能够到达的地方
1class Solution:
2 def canJump(self, nums):
3 max_right = 0
4 for i,n in enumerate(nums):
5 if i<=max_right:
6 max_right = max(max_right, i+n)
7 if max_right>=len(nums)-1:
8 return True
9 return False
LC45.跳跃游戏II
给你一个非负整数数组 nums ，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 假设你总是可以到达数组的最后一个位置。
题解：造桥，每次跳跃都选能跳的最远的桥
1class Solution:
2 def jump(self, nums: List[int]) -> int:
3 ans = 0
4 cur_right = 0
5 next_right = 0
6 for i in range(len(nums)-1):
7 next_right = max(next_right, i+nums[i])
8 if i==cur_right:
9 ans+=1
10 cur_right = next_right
11 return ans
类似题目:LC1326. 灌溉花园的最少水龙头数目
1class Solution:
2 def minTaps(self, n, ranges):
3 right_most = [0]*(n+1)
4 for i,r in enumerate(ranges):
5 left = max(i-r, 0)
6 right_most[left] = max(right_most[left], i+r)
7
8 ans = 0
9 cur_right = 0
10 next_right = 0
11 for i in range(n):
12 next_right = max(next_right, right_most[i])
13 if i==cur_right:
14 if i==next_right:
15 return -1
16 cur_right = next_right
17 ans+=1
18 return ans
LC763. 划分字母区间
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。 注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。 返回一个表示每个字符串片段的长度的列表。
题解：本质合并区间，找到每个字符最后出现的位置
1class Solution:
2 def partitionLabels(self, s: str) -> List[int]:
3 ans = []
4 last = {c:i for i,c in enumerate(s)}
5 start = end = 0
6 for i, c in enumerate(s):
7 end = max(end, last[c])
8 if end==i:
9 ans.append(end-start+1)
10 start=i+1
11 return ans
栈
LC394. 字符串解码
给你一个字符串 s ，根据下述规则反转字符串： 所有非英文字母保留在原有位置。 所有英文字母（小写或大写）位置反转。 返回反转后的 s 。
题解：
1class Solution:
2 # 递归
3 def decodeString(self, s: str) -> str:
4 if not s: return s
5 if s[0].isalpha():
6 return s[0] + self.decodeString(s[1:])
7 i = s.find("[")
8 balance = 1
9 for j in count(i+1):
10 if s[j] == '[':
11 balance+=1
12 elif s[j] == ']':
13 balance-=1
14 if balance==0:
15 return self.decodeString(s[i+1:j])*int(s[:i]) + self.decodeString(s[j+1:])
16
17 # 用栈模拟
18 def decodeString(self, s: str) -> str:
19 st = []
20 k = 0
21 res = ''
22 for i, c in enumerate(s):
23 if c.isalpha():
24 res += c
25 elif c.isdigit():
26 k = k*10+int(c)
27 elif c=='[':
28 st.append((res, k))
29 res = ''
30 k = 0
31 else:
32 pre_res, pre_k = st.pop()
33 res = pre_res+ pre_k*res
34 return res
单调栈
LC739. 每日温度
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指在第 i 天之后，才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。
题解：
1class Solution:
2 def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
3 n = len(temperatures)
4 ans = [0]*n
5 st = []
6 for i, t in enumerate(temperatures):
7 while st and temperatures[st[-1]]<t:
8 j = st.pop()
9 ans[j] = i-j
10 st.append(i)
11 return ans
LC84. 柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。
题解：和LC42. 接雨水的单调栈做法类似。
1class Solution:
2 def largestRectangleArea(self, heights: List[int]) -> int:
3 st = []
4 ans = 0
5 heights = [-1]+heights+[-1]
6 for i,h in enumerate(heights):
7 while st and heights[st[-1]]>=h:
8 j = st.pop()
9 start = st[-1] if st else -1
10 ans = max(ans, heights[j]*(i-start-1))
11 st.append(i)
12
13 return ans
二分查找
LC35.搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。
题解：二分查找，开区间
1class Solution
2 def searchInsert(self, nums: List[int], target: int) -> int:
3 left, right = -1, len(nums)
4 while left+1<right:
5 mid = (left+right)//2
6 if nums[mid]>=target:
7 right = mid
8 else:
9 left = mid
10 return right
LC74. 搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵： 每行中的整数从左到右按非严格递增顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
题解：
1class Solution:
2 # 直接二分
3 def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
4 m,n = len(matrix), len(matrix[0])
5 left, right = -1, m*n
6 while left+1<right:
7 mid = (left+right)//2
8 x = mid//n
9 y = mid%n
10 if matrix[x][y]==target: return True
11 if matrix[x][y]<target:
12 left = mid
13 else:
14 right = mid
15 return False
16
17 # 利用矩阵的性质
18 def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
19 m,n = len(matrix), len(matrix[0])
20 i,j = 0, n-1
21 while i<m and j>=0:
22 if matrix[i][j]==target:
23 return True
24 if matrix[i][j]<target:
25 i+=1
26 else:
27 j-=1
28 return False
LC33. 搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值 互不相同 。 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
题解：
1class Solution:
2 def findMin(self, nums):
3 left, right = -1, len(nums)-1
4 while left+1<right:
5 mid = (left+right)//2
6 if nums[mid]<nums[-1]:
7 right = mid
8 else:
9 left = mid
10 return right
11
12 def lowerbound(self, nums, left, right, target):
13 while left+1<right:
14 mid = (left+right)//2
15 if nums[mid]>=target:
16 right = mid
17 else:
18 left = mid
19 return right if nums[right]==target else -1
20
21 def search(self, nums: List[int], target: int) -> int:
22 idx = self.findMin(nums)
23 if target<=nums[-1]:
24 return self.lowerbound(nums, idx-1, len(nums), target)
25 else:
26 return self.lowerbound(nums, -1, idx, target)