Hot 100 第二部分Hot 100 指的是 LeetCode 上的一个题单撰写第 34 ~ 68 题为什么是 67 呢，因为没开会员写不了 253 会议室 II 哈哈哈339 除法求值图论，先跳过394 字符串解码因为有嵌套的存在，所以一般使用栈的形式处理这种遇到 ‘[’ 就进，遇到 ‘]’ 就退到上一个 ‘[’ ，然后把处理完的字符串放进去数字处理时候，遇到 ‘[’ 表示当前数字完结了，把数字放进栈标准解答会更加简洁，我这边写的则相对直观一点class Solution: def decodeString(self, s: str) -> str: str_stk = [] num_stk = [] num = 0 for c in s: if c.isdigit(): num = num * 10 + int(c) elif c == '[': num_stk.append(num) num = 0 # 这个数字处理完了，清空并入栈 str_stk.append(c) elif c == ']': parts = [] while str_stk and str_stk[-1] != '[': parts.append(str_stk.pop()) str_stk.pop() # 弹出 '[' repeat_str = "".join(reversed(parts)) # 注意这里弹出来是颠倒的 k = num_stk.pop() str_stk.append(repeat_str * k) # 放回栈中 else: str_stk.append(c) return "".join(str_stk)347 前 K 个高频元素使用 heapq 的 api，小顶堆解法class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: mp = Counter(nums) heap = [] for key, val in mp.items(): if len(heap) < k: heapq.heappush(heap, (val, key)) elif val > heap[0][0]: heapq.heapreplace(heap, (val, key)) return [key for _, key in heap]338 比特位计数这个实际上使用dp来写，而不是逐个运算，最后一个用位运算class Solution: def countBits(self, n: int) -> List[int]: dp = [0] * (n + 1) for num in range(1, n + 1): dp[num] = dp[num >> 1] + (num & 1) return dp 337 打家劫舍 III经典 dp, 注意是取最优解, 而不是一定偷class Solution: def rob(self, root: Optional[TreeNode]) -> int: def dfs(node): if not node: return (0, 0) # (不偷, 偷) l0, l1 = dfs(node.left) r0, r1 = dfs(node.right) not_rob = max(l0, l1) + max(r0, r1) # 孩子可以偷也可以不偷 rob = l0 + r0 + node.val # 一定不能偷 return (not_rob, rob) return max(dfs(root))121 买卖股票的最佳时机计算最大差值，抛砖引玉的砖class Solution: def maxProfit(self, prices: List[int]) -> int: min_p = float('inf') ret = 0 for p in prices: ret = max(p - min_p, ret) min_p = min(p, min_p) return ret312 戳气球这道题是一个 hard 的区间dp，将一个长问题分为多个子区间去完成，要点就是状态转移是“最后一步的操作”，区间有可能是二维双向扩展的，他们的特点是dp需要重建，做一个决策会改变问题结构相似的题目还有：516, 647, 1039, 1130, 375, 546（越来越难）dp 数组含义：在区间 (l, r)（注意是开区间）里最后戳的是 k，那么最后一次得到的金币这个就能够固定左右边界，然后获得的收益只和 k 有关系了，而问题被分成了 k 左右两个区间把 dp 数组设置为 dp[a][b] 是区间 (a, b) 之间的最优解，从最小的区间开始向上推进class Solution: def maxCoins(self, nums: List[int]) -> int: a = [1] + nums + [1] m = len(a) dp = [[0] * m for _ in range(m)] # dp[l][r] 表示开区间 (l, r) 全部戳完的最大金币 for l in range(m - 1, -1, -1): for r in range(l + 2, m): # 至少留一个 k：l < k < r best = 0 for k in range(l + 1, r): best = max(best, dp[l][k] + dp[k][r] + a[l] * a[k] * a[r]) dp[l][r] = best return dp[0][m - 1]309 买卖股票的最佳时机含冷冻期代码随想录经典题，略class Solution: def maxProfit(self, prices: List[int]) -> int: free, hold, frozen = 0, -prices[0], 0 for p in prices[1:]: new_frozen = hold + p new_free = max(free, frozen) new_hold = max(hold, free - p) free, hold, frozen = new_free, new_hold, new_frozen return max(free, frozen)301 删除无效的括号hard 回溯，有一定的难度，注意回溯的一个特征就是找到所有的解注意到：在某个区间内，) 数量一定是小于等于 ( 数量的，否则必定无法匹配成功，这是剪枝的关键地方不能全局到结尾来统计左右括号数量，一定要逐个区间计算，否则会出现 )( 不用删的错误情况class Solution: def removeInvalidParentheses(self, s: str) -> List[str]: lrem = rrem = 0 for c in s: if c == '(': lrem += 1 elif c == ')': if lrem == 0: rrem += 1 # 左边没了，只能删右边 else: lrem -= 1 # 预计匹配，左边少删一个 def is_valid(s): balance = 0 for c in s: if c == '(': balance += 1 elif c == ')': balance -= 1 if balance < 0: return False return (balance == 0) def dfs(start: int, lrem: int, rrem: int, cur: str): # 只要超删就剪枝 if lrem < 0 or rrem < 0: return # 删够了才检查合法性 if lrem == 0 and rrem == 0 and is_valid(cur): ret.append(cur) return for i in range(start, len(cur)): # 只对括号尝试删除 if cur[i] not in '()': continue # 去重：同一层如果连续相同字符，只删第一个 if i > start and cur[i] == cur[i - 1]: continue nxt = cur[:i] + cur[i + 1:] if cur[i] == '(': dfs(i, lrem - 1, rrem, nxt) else: # cur[i] == ')' dfs(i, lrem, rrem - 1, nxt) ret = [] dfs(0, lrem, rrem, s) return ret300 最长递增子序列dp方法就是从前面找一个比他小的进行状态累加但是有 二分+贪心 的最优解，比较难想：如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小贪心就在于：我一定会在同一个位置选择更小的那个数，使得后面的数尽可能比我这个位置的数字大如果这个数比我所有已知的数字都大，那么就是我的序列就上升一次，否则替换一个台阶具体的讲解可以看看from bisect import bisect_left class Solution: def lengthOfLIS(self, nums: List[int]) -> int: tails = [] # 这是一个有序数组 for n in nums: idx = bisect_left(tails, n) # 找到 <= x 的下标位置 if idx == len(tails): # 是结尾，直接加入 tails.append(n) else: tails[idx] = n return len(tails)287 寻找重复数图论判环算法297 二叉树的序列化与反序列化主要是要标记 null 这一个注意点，如果是前序遍历就是顺序解码可以回去复习一下：根据前+中遍历来恢复一个二叉树的算法class Codec: def serialize(self, root): # 前序遍历 ret: str = [] def preTraversal(curr): nonlocal ret if curr is None: ret.append('#') return ret.append(str(curr.val)) preTraversal(curr.left) preTraversal(curr.right) preTraversal(root) # print(ret) return ','.join(ret) def deserialize(self, data): it = iter(data.split(',')) def build(): x = next(it) if x == '#': return None node = TreeNode(int(x)) node.left = build() node.right = build() return node return build() 287 寻找重复数这题目和 142 环形链表 II 都使用 Floyid 算法可以判断环的位置把下标看成是一个节点，把 nums[i] 看成是下一个节点，就是一个链表找环的题目class Solution: def findDuplicate(self, nums: List[int]) -> int: # Floyid 环算法 slow = nums[0] fast = nums[nums[0]] while slow != fast: slow = nums[slow] fast = nums[nums[fast]] # 找到相遇点，回去找入环点 slow = 0 while slow != fast: slow = nums[slow] fast = nums[fast] return slow283 移动零双指针移动所有不是 0 的数据class Solution: def moveZeroes(self, nums: List[int]) -> None: # 原地修改不返回， 把所有不是 0 的全部向前移动 n = len(nums) slow = 0 for fast in range(n): if nums[fast] != 0: nums[slow] = nums[fast] slow += 1 while slow < n: nums[slow] = 0 slow += 1279 完全平方数动态规划经典题目class Solution: def numSquares(self, n: int) -> int: dp = [float('inf')] * (n + 1) # 1 ~ n dp[0] = 0 for i in range(1, n + 1): for sq in range(int(sqrt(i)) + 1): dp[i] = min(dp[i], dp[i - sq * sq] + 1) return dp[n]253 会议室 II没会员，下次一定240 搜索二维矩阵 II把起点设置在左下角，或者右上角，就可以每次判断去除一整行或者列class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: m = len(matrix) n = len(matrix[0]) i, j = m -1, 0 while i >= 0 and j < n: if matrix[i][j] > target: i -= 1 elif matrix[i][j] < target: j += 1 else: return True else: return False239 滑动窗口最大值可以用 top k 的同样思路，使用大顶堆，一旦堆顶过期了就弹出，否则只需要 push 就行了这里写一下更优解法，单调队列的方式，这个还是蛮难写的，要重点学一学：如果遇到 i < j 且 nums[i] <= nums[j] 的时候，一旦 nums[j]入队就可以把 nums[i]直接丢弃了（只要 nums[j] 在就一定是他更大）如果出口处这个最大的元素已经被窗口抛弃了，则正常弹出这两条规则分别对应 窗口右侧加入，窗口左侧放入两种操作，这就构成了我们的整个单调队列，最大值永远是出口处的元素从右侧放进来的元素，会从右边一直删除元素直到，他左边那个值比他大（或者他就是最大的），这样左边永远是更大的值class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: n = len(nums) q = deque() # 存下标，保证 nums[q] 单调递减（队首最大） for i in range(k): while q and nums[q[-1]] <= nums[i]: q.pop() # 从队尾弹出更小/相等的 q.append(i) ret = [nums[q[0]]] for i in range(k, n): if q and q[0] <= i - k: q.popleft() # 先移除过期（只可能在队首） while q and nums[q[-1]] <= nums[i]: q.pop() # 比当前值来的早，还比当前值小，没有任何维护的意义 q.append(i) ret.append(nums[q[0]]) return ret22 括号生成是 LeetCode 301 删除无效的括号 的派生题目，是那道题的子集，更简单的版本class Solution: def generateParenthesis(self, n: int) -> List[str]: res = [] path = [] def backtrace(left, right): if left == 0 and right == 0: res.append("".join(path)) return if left > right: # 右括号数 > 左括号 return if left > 0: path.append('(') backtrace(left - 1, right) path.pop() if right > 0: path.append(')') backtrace(left, right - 1) path.pop() backtrace(n, n) return res49 字母异位词分组判断异位词应该使用 Hash，这里主要使用一个 26 维的向量（实际上就是一个 hash）作为 key外层再进行一个 hash 将所有的（26维向量相同）异位词放一起这里插播一个 python 的要点，dict.get() 拿到的不是原来的数据，修改是不会写入到 dict 中的，应该使用 dict.setdefault 或者直接初始化 dict 为 mp = defaultdict(list)class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: mp = {} for s in strs: count = [0] * 26 for c in s: count[ord(c) - ord('a')] += 1 key = tuple(count) mp.setdefault(key, []).append(s) return list(mp.values())48 旋转图像这题有两种解法，一个是四点交换（算边界条件麻烦点），一个是转置+对称交换其中四点变换（计算机方法）的方法更加适合 cpp 因为看起来清晰点，而且操作更加底层实际上这两个算法的复杂度都是空间 O(1) 时间 O(n^2) ，没有什么区别，这里用 cpp 写吧，逻辑清楚点，不然就是 4 元素 tuple 直接交换了class Solution { public: void rotate(vector<vector<int>>& matrix) { int n = matrix.size(); for (int i = 0; i <= n / 2 - 1; i++) { for (int j = 0; j <= (n - 1) / 2; j++) { // 四点变换 int tmp = matrix[i][j]; matrix[i][j] = matrix[n - j - 1][i]; matrix[n - j - 1][i] = matrix[n - i -1][n - j -1]; matrix[n - i -1][n - j -1] = matrix[j][n - i -1]; matrix[j][n - i -1] = tmp; } } } };46 全排列全排列回溯可以用 标记数组的方式来一个个遍历class Solution: def permute(self, nums: List[int]) -> List[List[int]]: n = len(nums) used = [False] * n ret = [] curr = [] def backtrace(): if len(curr) == n: ret.append(curr.copy()) return for i in range(n): if used[i]: continue used[i] = True curr.append(nums[i]) backtrace() curr.pop() used[i] = False backtrace() print(ret) return ret42 接雨水传奇背诵题接雨水，要么单调栈，要么双指针class Solution: def trap(self, height: List[int]) -> int: stk = [] ret = 0 n = len(height) for i in range(n): while stk and height[stk[-1]] <= height[i]: # 单调栈：非空且栈顶 <= 当前值，需要弹出 mid_idx = stk.pop() if stk: # 表示 mid_idx 左边有比他大的, 可以接水 left_idx = stk[-1] l = i - left_idx -1 h = min(height[left_idx], height[i]) - height[mid_idx] ret += l * h # print(f"{l} * {h}, {ret}, ({left_idx}, {mid_idx}, {i})") stk.append(i) return ret39 组合总和经典回溯class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: candidates.sort() ret = [] n = len(candidates) def backtrace(idx, path, left): if left == 0: ret.append(path.copy()) return for i in range(idx, n): if candidates[i] > left: path.append(candidates[i]) break backtrace(i, path, left - candidates[i]) path.pop() backtrace(0, [], target) return ret543 二叉树的直径递归简单题class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: ret = 0 def dfs(root): if root is None: return 0 l = dfs(root.left) r = dfs(root.right) nonlocal ret ret = max(l + r, ret) return max(l, r) + 1 dfs(root) return ret34 在排序数组中查找元素的第一个和最后一个位置这道题目很好，涉及到了二分查找的本质，我们可以从中抽象出二分查找的通用模板二分查找边界的本质：一个结构，对某一个 bool 表达式的值呈现单调性，我们通过对半取区间来找到第一个发生变化的区间False False False True True True ↑ 我们要找的点所以说，找下界就是找到第一个让 nums[i] >= target 从 false 变为 true 的点，上界就是第一个让 nums[i] > target 从 false 变为 true的点我们列出循环不变量的表达式（伪代码）：bool [0, l) == Talse , bool [r, n) == True所以有这个通用公式（面向于我们从 False 转到 True 的数组单调性）：if f(mid) == True: # f(mid) == True, 保证了 [r, n) 是 True r = mid else: # 保证了 [0, mid + 1) 是 False l = mid + 1最后这道题的解法是class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: # 二分查找, 一个是 [0, l) <= target, 另一个是 [l, n) > target n = len(nums) def lower(): # 找到第一个 nums[i] >= target l, r = 0, n while l < r: # [l, r) mid = (l + r) >> 1 if nums[mid] >= target: r = mid else: l = mid + 1 return l def upper(): # 找到第一个 nums[i] > target l, r = 0, n while l < r: # [l, r) mid = (l + r) >> 1 if nums[mid] > target: r = mid else: l = mid + 1 return l l = lower() u = upper() if l == n or nums[l] != target: return(-1, -1) else: return(l, u - 1)33 搜索旋转排序数组两次二分，实际上和上一题目同类型，理解了二分就很快写得出来class Solution: def search(self, nums: List[int], target: int) -> int: n = len(nums) last = nums[-1] def find_split(): l, r = 0, n while l < r: mid = (l + r) // 2 if nums[mid] <= last: r = mid else: l = mid + 1 return l pivot = find_split() def bin_search(l, r): # 等值二分查找 while l < r: mid = (l + r) // 2 if nums[mid] == target: return mid if nums[mid] < target: l = mid + 1 else: r = mid return -1 if target <= last: return bin_search(pivot, n) else: return bin_search(0, pivot)32 最长有效括号这道题有两种写法，一个是 dp （讨论两种情况），另一个是双向扫描贪心（太难想到了）由于 dp 虽然不是最优解但是也有一定的参考价值，这里把两种方式都写一下class Solution: def longestValidParentheses(self, s: str) -> int: n = len(s) dp = [0] * n # dp[i]: 以 i 结尾的最长有效括号长度 ret = 0 for i in range(1, n): if s[i] == '(': continue # 以 '(' 结尾不可能是有效括号 if s[i - 1] == '(': # 情况1：紧邻 () dp[i] = (dp[i - 2] if i >= 2 else 0) + 2 else: # 情况2：...)) 尝试跨过 dp[i-1] 那段去找 '(' pre = dp[i - 1] j = i - pre - 1 # 可能与 s[i] 匹配的 '(' 位置 if j >= 0 and s[j] == '(': dp[i] = pre + 2 + (dp[j - 1] if j >= 1 else 0) ret = max(ret, dp[i]) return ret遇到 '('：left += 1，遇到 ')'：right += 1若 right > left：说明右括号过多，当前段不可能再变合法，重置 left = right = 0若 left == right：当前段合法，长度 2 * right，更新答案左右各扫描一次就能补齐所有答案class Solution: def longestValidParentheses(self, s: str) -> int: ans = 0 # left -> right left = right = 0 for ch in s: if ch == '(': left += 1 else: right += 1 if right > left: left = right = 0 elif left == right: ans = max(ans, 2 * right) # right -> left left = right = 0 for ch in reversed(s): if ch == '(': left += 1 else: right += 1 if left > right: left = right = 0 elif left == right: ans = max(ans, 2 * left) return ans31 下一个排列模拟思路题目，写过一遍就好了class Solution: def nextPermutation(self, nums: List[int]) -> None: n = len(nums) pre = -1 i = n - 1 def reverse_nums(nums, a, b): while a < b: nums[a], nums[b] = nums[b], nums[a] a += 1 b -= 1 while i >= 0: if nums[i] < pre: break pre = nums[i] i -= 1 else: reverse_nums(nums, 0, n - 1) # 重新排列最小值 return # 找到第一个 比 nums[i] 大的交换一下 for j in range(n - 1, i, -1): if nums[i] < nums[j]: nums[i], nums[j] = nums[j], nums[i] break reverse_nums(nums, i + 1, n - 1)538 把二叉搜索树转换为累加树这道题有一个 Moris 遍历的方法，可以使用 O(1) 的空间，后面可以学习一下，这里先放一个普通DFS 解法class Solution: def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]: total = 0 def dfs(root): if root is None: return # 右中左 nonlocal total dfs(root.right) total += root.val root.val = total dfs(root.left) dfs(root) return root23 合并 K 个升序链表这里直接使用最小堆，注意 heapq 中没有 cmp 的 key 只能自行构造元组class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: heap = [] heapq.heapify(heap) uid = 0 for node in lists: if node: uid += 1 heapq.heappush(heap, (node.val, uid, node)) dummy = ListNode() curr = dummy while heap: # 只要非空 _, _, nd = heapq.heappop(heap) curr.next = nd curr = curr.next if nd.next is not None: uid += 1 heapq.heappush(heap, (nd.next.val, uid, nd.next)) return dummy.next560 和为 K 的子数组这不是一个 dp 题目，连续子数组求和是前缀和的应用场景class Solution: def subarraySum(self, nums: List[int], k: int) -> int: total = 0 count = defaultdict(int) count[0] = 1 ret = 0 for n in nums: total += n # 当前位置的前缀和 ret += count[total - k] # 找已经遇到的更小的前缀和点 count[total] += 1 return ret21 合并两个有序链表白给题目class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode() curr = dummy l1, l2 = list1, list2 while l1 and l2: if l1.val < l2.val: curr.next = l1 l1 = l1.next else: curr.next = l2 l2 = l2.next curr = curr.next curr.next = l1 if l1 is not None else l2 return dummy.next20 有效的括号白给题经典栈解法，注意最后栈一定要保持是空的class Solution: def isValid(self, s: str) -> bool: mp = {')' : '(', '}' : '{', ']' : '['} stk = [] for c in s: if c not in mp: stk.append(c) else: if not stk or stk.pop() != mp[c]: return False return not stk # 最后栈必须是空的 19 删除链表的倒数第 N 个结点简单的双指针题目，但是要注意的边界条件其实蛮多的，建议是实际手写一次试一下class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: dummy = ListNode(0, head) slow, fast = dummy, dummy for i in range(n): fast = fast.next while fast.next is not None: slow = slow.next fast = fast.next slow.next = slow.next.next return dummy.next 17 电话号码的字母组合相对简单好想到的回溯算法class Solution: def letterCombinations(self, digits: str) -> List[str]: mp = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'] n = len(digits) ret = [] if not digits: return [] def backtrace(path, idx): if idx == n: ret.append("".join(path)) return for c in mp[int(digits[idx])]: path.append(c) backtrace(path, idx + 1) # 下一个字母 path.pop() backtrace([], 0) return ret
Hot 100 第一部分Hot 100 指的是 LeetCode 上的一个题单一共 100 题，第一部分撰写第 1 ~ 33 题个别没写的后续再补160 相交链表这里给出最标准的写法（Python 风格）为什么不会无限循环的原因是，两个节点走的总长度都是 a + b，最后一定会同时移动到 None 然后退出循环class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]: # 快捷方法，直接到对方的头节点，然后统计第一个相等的数值 # 本质上是将差值自动应用 if not headA or not headB: return None pA, pB = headA, headB while pA is not pB: pA = pA.next if pA else headB pB = pB.next if pB else headA return pA236 二叉树的公共祖先后序遍历，上浮答案需要明确向外传递节点的逻辑另外可以考虑一下节点本身就是 LCA 的情况：直接把自身返回，另一个节点永远不会被返回，所以永远上报的一个是 None 一个是 LCA，最终返回的就是 LCA，这个逻辑很难想class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': # 后序遍历 if not root or root is p or root is q: # 1. root 为 None，说明这一支没找到 # 2. root 是 p 或 q，找到目标之一，向上返回 return root left = self.lowestCommonAncestor(root.left, p, q) right = self.lowestCommonAncestor(root.right, p, q) # 两边都有东西，说明 p 和 q 分布在 root 的不同子树，root 就是 LCA if left and right: return root # 只有一边非空，说明 p、q 都在这一边，或者只找到一个，继续向上传递 return left if left else right234 回文链表有两种方式，如果需要 O(1) 的空间复杂度需要对原来的链表进行修改如果不允许修改就使用栈的方式重点在于计算清除中间节点和终止数量，一般推荐从0开始+对0空节点的特殊判断（本题题目限定了不会有空节点）另外如果使用了翻转链表的方式，注意使用快慢指针的方式来找到中间节点class Solution: def reverseList(self, head): # 从 head 开始翻转后续所有的链表 curr = head pre = None while curr: temp = curr.next curr.next = pre pre = curr curr = temp return pre def isPalindrome(self, head: Optional[ListNode]) -> bool: # 快慢指针找到中间位置，原地翻转 slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next # 如果 fast 不为空，说明是奇数长度，需要跳过中间节点 if fast: slow = slow.next second = self.reverseList(slow) first = head while second is not None: if first.val != second.val: return False first = first.next second = second.next return True739 每日温度这里遇到了如何通过下标的方式来访问一个列表，答案是使用 enumeratre如果一个 list 是空的就自动变成 Falsepython 中的 pop 是会返回被弹出的值的class Solution: def dailyTemperatures(self, temperatures: List[int]) -> List[int]: # 单调栈 stk = [] ret = [0] * len(temperatures) for i, num in enumerate(temperatures): while (stk and num > temperatures[stk[-1]]): # list 为空自动变成 False idx = stk.pop() # list 的 pop 会自动返回弹出的元素 ret[idx] = i - idx stk.append(i) return ret226 翻转二叉树简单题，后序遍历递归class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: # 后序遍历 if root is None: return None self.invertTree(root.left) self.invertTree(root.right) # 本层逻辑 root.left, root.right = root.right, root.left return root221 最大正方形经典 dp 的写法：用某个结尾值来表示 dp 矩阵的意义，同时控制连续性class Solution: def maximalSquare(self, matrix: List[List[str]]) -> int: # 定义一个以(x, y)为右下角的最大正方形的边长大小 m = len(matrix) n = len(matrix[0]) dp = [[0] * (n + 1) for _ in range(m + 1)] ret = 0 for i in range(1, m + 1): for j in range(1, n + 1): if matrix[i - 1][j - 1] == "1": # 这个格子是 1 dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1 else: dp[i][j] = 0 ret = max(ret, dp[i][j]) return ret * ret215 数组中的第 k 个最大元素使用最小堆进行操作注意：应该学会优先级队列的底层操作逻辑（堆，一种基于完全二叉树的数据结构）class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: # 最小堆，使用 heapq 实现，默认就是最小堆 heap = [] for x in nums: heapq.heappush(heap, x) if len(heap) > k: heapq.heappop(heap) return heap[0]208 实现 Trie 前缀树使用 dict 可以省去一个 标记 curr 节点代表的字符class Trie: def __init__(self): self.children = {} # 下一个的一组树形 self.is_node = False def insert(self, word: str) -> None: node = self for c in word: node = node.children.setdefault(c, Trie()) node.is_node = True def search(self, word: str) -> bool: node = self for s in word: node = node.children.get(s, None) if node is None: return False return node.is_node def startsWith(self, prefix: str) -> bool: node = self for s in prefix: node = node.children.get(s, None) if node is None: return False return True207 课程表图没有学完，日后补206 反转链表交换 next 注意不能动下一个，因为下一个动了，下一次循环的时候就丢失了 next 信息想起来简单，但是实际操作有要注意的点class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: curr = head pre = None while curr: tmp = curr.next curr.next = pre pre = curr curr = tmp return pre200 岛屿数量简单的遍历，这里写DFS 算法class Solution: def numIslands(self, grid: List[List[str]]) -> int: direction = [(1, 0), (0, 1), (-1, 0), (0, -1)] m = len(grid) n = len(grid[0]) def dfs(x, y): if not (0 <= x < m and 0 <= y < n): return if grid[x][y] == '0': return grid[x][y] = '0' # 标记访问过 for dx, dy in direction: dfs(x + dx, y + dy) count = 0 for i in range(m): for j in range(n): if grid[i][j] == '1': count += 1 dfs(i, j) return count198 打家劫舍经典 dp 表示收益最大的情况class Solution: def rob(self, nums: List[int]) -> int: l = len(nums) dp = [0] * l dp[0] = nums[0] if l == 1: return dp[0] dp[1] = max(nums[1], nums[0]) for i in range(2, l): dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]) return dp[l - 1]169 多数元素使用投票法，只要是候选人他的票数一定超过一半，很巧妙的方法求众数或者也可以使用排序算法（应该都能想到把）class Solution: def majorityElement(self, nums: List[int]) -> int: can = None count = 0 for n in nums: if count == 0: can = n # 换人和改票数一定要绑定 count = 1 elif n == can: count += 1 else: count -= 1 return can238 除自身以外最大数组成绩扫描两边，分别使用前后缀class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: l = len(nums) pre = 1 after = 1 ret = [1] * l for i in range(l): ret[i] = pre pre *= nums[i] for i in reversed(range(l)): ret[i] *= after after *= nums[i] return ret155 最小栈维护两个栈即可，没有实际难度，见过就会class MinStack: def __init__(self): self.stack = [] self.ministack = [] def push(self, val: int) -> None: self.stack.append(val) if self.ministack: self.ministack.append(min(val, self.ministack[-1])) else: self.ministack.append(val) def pop(self) -> None: self.stack.pop() self.ministack.pop() def top(self) -> int: return self.stack[-1] def getMin(self) -> int: return self.ministack[-1]152 乘积最大子数组注意要同时维护最大值和最小值，因为负数可以乘以负数来逆袭这里用的是 O(1) 复杂度的，但是实际上一般是写完 O(n) 再优化为滚动数组的class Solution: def maxProduct(self, nums: List[int]) -> int: lastmin = nums[0] lastmax = nums[0] ret = nums[0] for i in range(1, len(nums)): x = nums[i] tmp_min = min(x, lastmax * x, lastmin * x) lastmax = max(x, lastmax * x, lastmin * x) lastmin = tmp_min ret = max(ret, lastmax) return ret148 排序链表链表的排序是归并排序算法反复二分法，直到只有两个节点（链表的二分法使用快慢指针实现的）比较两个链表的头，把较小的那个接到结果链表后面（此时两个链表各自内部已经排序完毕，只要左右各自轮流比较即可）注意这里不涉及到反转操作，反转一定会出现 cur.next = prev这种操作这个递归还是想了很久，感觉掌握还是不够好，要多练习递归class Solution: @staticmethod def _find_mid(head): slow = head fast = head.next while fast and fast.next: slow = slow.next fast = fast.next.next return slow # 左半尾，方便断开 @staticmethod def merge(l1, l2): dummy = ListNode(0) curr = dummy while l1 and l2: if l1.val > l2.val: curr.next = l2 l2 = l2.next else: curr.next = l1 l1 = l1.next curr = curr.next curr.next = l1 or l2 return dummy.next def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]: if not head or not head.next: return head mid = self._find_mid(head) right = mid.next mid.next = None # 断链 left = self.sortList(head) right = self.sortList(right) return self.merge(left, right)146 LRU 缓存用 hash 表实现快速查找，另外就是对于 LRU 需要频繁的将某一个值移动到最头处，所以最合适的其实是链表数据，这里使用双端链表，一个头一个尾分别代表最后使用和最先使用这里用到了 OrderedDict 的 API，没有单独写 hash 链表，可以放到单独 707, 641 去写from collections import OrderedDict class LRUCache: def __init__(self, capacity: int): self.od = OrderedDict() self.max = capacity def get(self, key: int) -> int: if key in self.od: self.od.move_to_end(key) return self.od.get(key) else: return -1 def put(self, key: int, value: int) -> None: if key in self.od: # 对于已经存在的情况 self.od[key] = value self.od.move_to_end(key) # 移动到队伍尾 return elif len(self.od) >= self.max: # 满了要删除一个 self.od.popitem(last=False) # 删除队伍头（最近未使用） self.od[key] = value # 新插入，默认在队伍尾部142 环形链表II经典数学题，需要理清楚环的步数和入环点的位置关系（是 mod 整倍数关系）这里有个 while else 的用法，是在没有 break 的时候触发的，可以注意下class Solution: def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]: if head is None: return None slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow is fast: # 有环相遇了 break else: # 到结尾了还没有相遇 return None slow = head while slow is not fast: slow = slow.next fast = fast.next return slow141 环形链表快慢指针，方法同上一题，省略139 单词拆分写这道题目前要先写 518 零钱对换II，可能更好理解点完全背包问题中的排列问题，因为 aab 和 aba 不是同一个字符串，这构成了排列关系class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: m = len(wordDict) n = len(s) dp = [False] * (n + 1) # 前 i 个字符 s[:i] 是否可以拆分 dp[0] = True # 递推的起点，可以拆分 for j in range(1, n + 1): for w in wordDict: L = len(w) if dp[j - L] == True and s[j - L:j] == w: dp[j] = True break # 一旦找到就去下一个分割点了 return dp[n]136 只出现一次的数字抽象题，见过就秒，没见过就想不出，利用异或运算性质x ^ x = 0 # 和自身异或是 0 x ^ 0 = x # 和 0 异或不影响自身 x ^ y ^ z = x ^ z ^ y # 结合律class Solution: def singleNumber(self, nums: List[int]) -> int: return reduce(lambda x, y: x ^ y, nums)647 回文子串这题的边界条件比较难，我建议多做两遍因为是左下推右上，所以外层从左到右，内层从下到上同时通过计算距离来杜绝越界的情况，这个边界条件还是很巧妙的class Solution: def countSubstrings(self, s: str) -> int: n = len(s) dp = [[False] * n for _ in range(n)] ret = 0 for r in range(n): for l in range(r, -1, -1): if s[l] == s[r]: if r - l <= 2 or dp[l + 1][r - 1]: dp[l][r] = True ret += 1 return ret128 最长连续序列可以用 排序 + dp 的方式，但是有点太慢了，正确做法使用 setclass Solution: def longestConsecutive(self, nums: List[int]) -> int: s = set(nums) ret = 0 for n in s: if n - 1 not in s: curr = n while curr in s: curr += 1 ret = max(ret, curr - n) return ret124 二叉树中最大路径和后序遍历模拟，注意就是向上传递的值不允许分叉，但是计算最大结果处允许分叉class Solution: def maxPathSum(self, root: Optional[TreeNode]) -> int: ret_max = float("-inf") def backTraversal(root): if root is None: return 0 # 后序遍历, 屏蔽负数 left = max(backTraversal(root.left), 0) right = max(backTraversal(root.right), 0) # 向上传递的值包含 root ret = max(root.val + left, root.val + right) # 不能够左右都包含，向上路径不能分叉 nonlocal ret_max ret_max = max(ret_max, root.val + left + right) # 允许分叉的点就是全局最大值 return ret backTraversal(root) return ret_max322 零钱兑换完全背包中，不在乎顺序，先遍历物品后遍历背包，内层正序遍历class Solution: def coinChange(self, coins: List[int], amount: int) -> int: dp = [float('inf')] * (amount + 1) dp[0] = 0 # 初始化为0 # 完全背包，先物品后背包，正序遍历 for c in coins: for j in range(c, amount + 1): dp[j] = min(dp[j], dp[j - c] + 1) return dp[amount] if dp[amount] != float('inf') else -1494 目标和数学计算一下可以发现所有的正数和应为：(sum + target) / 2，其中 sum 是数组全正的求和这就可以简化为一个零一背包的问题，先遍历物品后遍历背包，内层需要倒序class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: s = sum(nums) n = len(nums) if abs(target) > s or (s + target) % 2 != 0: return 0 # 无解的情况 tar = (s + target) // 2 dp = [0] * (tar + 1) # 凑出和为 j 的可能的个数（零一背包） dp[0] = 1 # 初始化： 0 个数凑出 0 的个数都是 1（等价于第0轮的遍历结果） for num in nums: for j in range(tar, num - 1, -1): # 零一背包内层需要倒序 dp[j] += dp[j - num] return dp[tar]461 汉明距离就是计算取异或然后计算 1 的个数，这里 py 直接有 bit_count() 的 apiclass Solution: def hammingDistance(self, x: int, y: int) -> int: # 取异或统计 1 的个数 return (x ^ y).bit_count()但是 底层一般考核的不是这个算法，而是Brian Kernighan 算法实际逻辑是这样的x = ?????1000...000 x - 1 = ?????0111...111 ---------------------- & = ?????0000...000底层代码是这样的def bit_count(x): cnt = 0 while x: x &= (x - 1) cnt += 1 return 448 找到所有数组中消失的数字经典背诵题，标记法，取模还原class Solution: def findDisappearedNumbers(self, nums: List[int]) -> List[int]: n = len(nums) for num in nums: idx = (num - 1) % n # -1 再取模，保证 0..n-1 nums[idx] += n return [i + 1 for i, x in enumerate(nums) if x <= n]438 找到字符串中所有字母异位词滑动窗口，这里直接写优化版本的，只统计差异值就行，可以将空间复杂度降低到 O(1)class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: offset = ord('a') m, n = len(s), len(p) if n > m: return [] diff = [0] * 26 for c in p: diff[ord(c) - offset] += 1 for c in s[:n]: diff[ord(c) - offset] -= 1 diff_count = sum(1 for x in diff if x != 0) ret = [] for i in range(m - n + 1): if diff_count == 0: ret.append(i) if i == m - n: break # 最后一个窗口不需要再滑动，和初始化结合控制边界 out_idx = ord(s[i]) - offset in_idx = ord(s[i + n]) - offset # out：窗口移出一个字符 => diff[out] += 1 before = diff[out_idx] diff[out_idx] += 1 after = diff[out_idx] if before == 0 and after != 0: diff_count += 1 elif before != 0 and after == 0: diff_count -= 1 # in：窗口移入一个字符 => diff[in] -= 1 before = diff[in_idx] diff[in_idx] -= 1 after = diff[in_idx] if before == 0 and after != 0: diff_count += 1 elif before != 0 and after == 0: diff_count -= 1 return ret437 路径总和 III有两种方法，DFS 遍历或者使用前缀和，使用前缀和的方法蛮难想的，建议多复习DFS ：使用内外两层递归，一层遍历所有的节点，第二层以该节点为起点，遍历到所有的叶子结点的位置求和前缀和：将 root -> 当前节点中的所有路径的前缀和放进一个 hash 表，查找前缀和为 prevSum = currSum - target的值即可为什么可以用 Hash？因为不需要严格有序的顺序，只需要计数是否存在就行了class Solution: def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int: # 前缀和, target = prefix[curr] - prefix[x] 表示从 x 到 curr 这两个值之间区间 from collections import defaultdict prefix = defaultdict(int) prefix[0] = 1 # 允许某个节点自己达成目标 def dfs(root, currSum): if root is None: return 0 ret = 0 currSum += root.val # 前缀和求值 ret += prefix[currSum - targetSum] prefix[currSum] += 1 # 加入前缀表 ret += dfs(root.left, currSum) ret += dfs(root.right, currSum) prefix[currSum] -= 1 # 退出节点的时候要回溯，因为前缀已经消失了 return ret return dfs(root, 0)416 分割等和子集零一背包，公式题class Solution: def canPartition(self, nums: List[int]) -> bool: total = sum(nums) if total % 2 != 0: return False target = total // 2 dp = [False] * (target + 1) # 是否存在一个子集，其元素和恰好为 j dp[0] = True # 什么都不选就是 0，必定存在 for num in nums: for j in range(target, num - 1, -1): dp[j] |= dp[j - num] if dp[target]: return True return dp[target]406 根据身高重建队列这个题是个很抽象的贪心题目，感觉算是背诵题关键：在一个人前面插入比他更矮的人， 不会影响这个人的定位，所以可以从大到小重建返回列表class Solution: def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]: people.sort(key=lambda x: (-x[0], x[1])) # 身高降序，编号升序 ret = [] for h, k in people: ret.insert(k, [h, k]) return ret
单调栈1 简介单调栈就是一个栈中元素保持单调性单调栈适合解决：求当前元素左或者右边第一个更大/小的元素重点需要确定栈是递增（从栈顶向栈底看）还是递减的属性：递增求的是第一个比他大的元素单调栈的作用是存放之前遍历过的数据，而数据的单调性有保证了一定不会漏掉之前已经放进来过的元素，这个过程比较巧妙，通过模拟一遍流程应该能能够理解这个步骤单调栈的本质是当新元素 x 进来时，如果它比结构里的某些元素“更优”，那些元素就永远不可能再成为答案，所以可以直接去除了2 题目节选2.1 每日温度LeeCode 739单调栈入门题，为了保证我们能够获取到之前放入的数据的具体信息，我们需要放入的是下标，而通过下标我们可以同时访问到元素的值class Solution { public: vector<int> dailyTemperatures(vector<int>& temperatures) { stack<int> stk; // 单调栈 vector<int> ret(temperatures.size(), 0); stk.push(0); for (int i = 1; i < temperatures.size();) { int idx = 0; if (stk.empty()) { stk.push(i++); continue; } else { idx = stk.top(); } if (temperatures[i] <= temperatures[idx]) { stk.push(i++); // 入栈，下一个数检查 } else { ret[idx] = i - idx; // 找到了某个数下一个最大值，更新 ret stk.pop(); // 继续检查这个数是不是还有比他小的 } } return ret; } };2.2 下一个更大的元素LeetCode 496哈希表 + 单调栈，并优化了一部分单调栈的循环逻辑这里注意一下使用 vector 模拟栈的操作class Solution { public: vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) { // 简化逻辑，每个元素进行一次入栈和出栈 unordered_map<int, int> mp; int m = nums1.size(); mp.reserve(m); for (int i = 0; i < m; i++) { mp[nums1[i]] = i; } vector<int> ret(nums1.size(), -1); vector<int> stk; // 这里不可以执行初始化大小 stk.reserve(nums2.size() / 2); for (int& x : nums2) { while(!stk.empty() && x > stk.back()) { // 只有非空且大于 才需要弹出 int val = stk.back(); stk.pop_back(); unordered_map<int, int>::iterator it = mp.find(val); if (it != mp.end()) { ret[it->second] = x; } } // 终归需要放进去 stk.push_back(x); } return ret; } };2.3 下一个更大的元素 IILeeCode 503环的下标，可以用取模来进行模拟单调栈每一个数字只入栈一次，每个数字在出栈的时候对结果数组进行赋值class Solution { public: vector<int> nextGreaterElements(vector<int>& nums) { int n = nums.size(); vector<int> ret(n, -1); vector<int> stk; stk.reserve(n / 2); for (int i = 0; i < 2 * n - 1; i++) { int j = i % n; // nums 的下标 while (!stk.empty() && nums[j] > nums[stk.back()]) { int idx = stk.back(); stk.pop_back(); ret[idx] = nums[j]; } if (i / n == 0) { // 只有第一次入栈 stk.push_back(j); } } return ret; } };2.4 接雨水LeetCode 42经典的单调栈题目，重点在于找到左右比他大（可以等于，其实不影响结果，因为都要减去中间柱子的高度）的值这是单调栈的做法，其实同时找左右两边更大的只用一个栈就可以了，因为栈里面存放了已经访问过的元素的数据class Solution { public: int trap(vector<int>& height) { // 1. 单调栈计算所有更大的值的相对位置 vector<int> higher(height.size(), -1); stack<int> stk; // 找右边大的（允许相等） for (int i = 0; i < height.size(); i++) { int curr = height[i]; while (!stk.empty() && curr > height[stk.top()]) { int idx = stk.top(); stk.pop(); higher[idx] = i - idx; } stk.push(i); } int ret = 0; for (int i = 0; i < higher.size(); i++) { // 有 -1 就漏水 if (higher[i] == -1) continue; // 对区间范围内全部累加 + 1 ret += higher[i] - 1; } return ret; } };接雨水还有一种双指针的算法，这个在刷 Hot 100 时候再写2.5 柱状图中的最大矩形LeetCode 84这里面混合一点点贪心的思想：最后的结果一定是某一个柱子的高度为什么呢？因为如果不是某个柱子的高度的话，一定就可以再往上顶一顶，也就是说一定会把某一个柱子的高度吃满要注意一下清空 栈的策略这里写的比较复杂，实际有更简单一点的写法class Solution { public: int largestRectangleArea(vector<int>& heights) { // 从某一个柱子开始计算左右两边的最低点 stack<int> stk; int n = heights.size(); int ret = heights[0]; for (int i = 0; i < n; i++) { int curr = heights[i]; // 从栈顶看是单调递减的栈 while(!stk.empty() && curr < heights[stk.top()]) { // 以 mid_idx 为核心高度，左右扩展计算面积 int mid_idx = stk.top(); int wide = 0; stk.pop(); if (stk.empty()) { // 左边没有更小的 wide = i; } else { // 左边还有更小的 wide = i - stk.top() - 1; } // cout << wide << " * " << heights[mid_idx] << endl; ret = max(ret, wide * heights[mid_idx]); } stk.push(i); // cout << heights[i] << ' ' << ret << endl; } // 把栈里面的剩下的统计一下 while(!stk.empty()) { int wide = 0; int mid_idx = stk.top(); stk.pop(); if (stk.empty()) { // 左边没有更小的了 wide = n; } else { wide = n - stk.top() - 1; } ret = max(ret, wide * heights[mid_idx]); } return ret; } };
动态规划1 解题步骤Dynamic Programming 动态规划真正理解 DP 应该注意一下几点：DP 数组中每一个值，或者索引的意义递推公式DP 数组的如何初始化遍历顺序打印 DP 数组（主要用于分析错误）1.1 什么时候用判断所有可能的状态中（图）是不是有环，有环一定不是 DP数据量极大的情况下不太能用 DPDP 的核心是，递推关系要固定不变，能找到让关系保持不变的 dp 数组定义，这点也是最难的2 背包问题2.1 零一背包 （二维数组）给定 n 件物品，每件物品有价值 value[i] 和重量 weight[i]在容量为 W 的背包中选择若干件物品，使得总价值最大，每件物品最多选一次。先用没有空间简化的方式进行分析（二维 dp）数组的定义：[0, i] 个物品，任选放入容量为 j 背包中的最大价值为 dp[i][j]递推公式：不放物品 i 则和 i - 1 一致如果放入 dp[i - 1][j - weight[i]] + value[i]，也就是不放入之前的最大价值（注意要改重量）+ 放入后的最大价值取上述两种情况的最大值，就是递推公式记得需要检查 j - weight[i]] + value[i]是否成立，也就是当前容量是否能够放入这个物品初始化需要先分析递推公式需要的前置条件需要的是 [i - 1][j] 或者 [i - 1][j - n] 的数据，因此初始化横纵坐标即可其他位置初始化，实际上这个值和后面的求值没有关系，初始化为任何值都可以其实初始化还可以横纵坐标都用 0 作为边界条件，不过代码随想录里并没有这么做遍历顺序，根据递推公式前置条件可以得到，实际上二维 dp 是没有顺序要求的，正序倒序以及背包物品顺序都可以颠倒// 假设：dp 的维度是 dp[N][C+1]，并且已初始化为 0 // dp[i][j]：用前 i 个物品（下标 0..i），在容量 j 下的最大价值 for (int j = 0; j <= C; j++) { if (j >= w[0]) dp[0][j] = v[0]; // else dp[0][j] = 0; // 已初始化可省略 } for (int i = 1; i < N; i++) { for (int j = 0; j <= C; j++) { dp[i][j] = dp[i-1][j]; // 不选第 i 个，先继承 if (j >= w[i]) { dp[i][j] = max(dp[i][j], dp[i-1][j - w[i]] + v[i]); // 选第 i 个 } } }2.2 零一背包（滚动数组）可以发现一个问题，就是 dp[i] 一直使用的是 dp[i - 1] 相关的数据进行计算的但是要注意遍历的顺序，检查递推公式：dp[i - 1][j - weight[i]] + value[i] 和 dp[i - 1][j] 其中之一，可以发现j 依赖于 上一轮次的 j 或者 j - weight[i]，这两个都是小于等于 j 的，因此 dp[j] 的遍历要用到上一轮的更小值，应该是从大到小遍历才可以！数组定义：在第 i 次循环中dp[j] 容量为 j 的背包的最大价值递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]) （注意其实 i 这个索引还是存在的，只是把 p 数组压缩一个维度）初始化：dp[0]肯定是 0，其他数值初始化为可能的数值中的最小值（为了防止覆盖其他值），看题目，一般也是 0遍历顺序：先遍历物品数量，再遍历背包容量，第二层循环需要倒序（因为不可以对依赖项进行覆写）代码部分可以参考本文中 分割等和子集 题目// w 和 v 下标从 0 开始 for (int i = 0; i < N; i++) { for (int j = C; j >= w[i]; j--) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } }2.3 完全背包每一个物品可以使用无数次的背包对于二维的情况下，直接改成就是完全背包，表示允许重复选取某一个数dp[i][j] = max( dp[i-1][j], // 不选第 i 个物品 dp[i][j - w[i]] + v[i] // 选第 i 个物品（可重复） )把内层 for 循环改成正序遍历就可以让物品使用无限次for (int i = 0; i < N; ++i) { for (int j = w[i]; j <= C; ++j) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } }这里要明确清楚为什么，因为在正序遍历的时候 dp[j - w[i]] + v[i]这个数值中的 dp[j - w[i]] 是在本轮（外层 i 循环）之前遍历的，有可能是已经添加过物品 i 的一个状态。这时候的递推是基于本轮的状态实现的，可以在此基础上再添加一个物品 i，因此就构成了每个物品可以无限取用的情况，也就是完全背包另外要注意一点：纯完全背包的遍历顺序（物品和背包）是可以颠倒的！原因就是一个：递推公式中可以由前面的数值推出当前的数值，我的建议是如果理解的话还是需要手动模拟一下横纵的顺序，就可以发现颠倒顺序后仍然可以用前面的状态推出当前的状态// 先遍历背包，再遍历物品 for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量 for(int i = 0; i < weight.size(); i++) { // 遍历物品 if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } }2.4 完全背包的排列组合但是如果涉及到了排列组合问题，就会导致遍历顺序需要注意假设我们的物品重量为 w[] = [1, 2, 3];，对于取物品恰好满足和为 target 的题目，递推公式为dp[j] += dp[j - w[i]];这个递推公式是通用的，关键在于 dp[j - w[i]]代表的数值是什么对于 先遍历物品后遍历背包的场景（01 背包通用方式）：在 1 物品选择依次放满所有的背包在 12 物品中选择依次放满，这个情况下只会有先 1 后 2的放入情况意思是放入 2 以后，必定只会放入 >= 2 的物品，不会再回去放入 1，这种情况是组合对于 先遍历背包后遍历物品的场景：我认为这个有点抽象，所以这里用了手写的方式来解释这里 dp 数组中是一个个确认过去的，内层循环中会反复对同一个 dp[j] 进行状态的累加，因此参考下图可以发现重叠的问题就是因为取物品的顺序不是固定的，i 的循环表示最后补上这个物品（没有圈的数值），但这就会导致每个物品都有可能为那个“补充值”，但是补充值本身会在 0 + j的情况下被计算一次：举例来说：3 = 1 + 2， 这里的 2 当做“补充值”，表示在所有和为 1 的情况上末尾补充一个 2 可以达成和为 3，但是当我们求补充值为 1 的时候，计算所有和为 2 的情况个数的时候，会和补充值为 2 的情况重复3 股票问题股票问题的关键仍然在于 dp 数组的定义定义 dp[i][0] 和 dp[i][1] 分别表示股票的持有和未持有，而不是统计买入与卖出，这是唯一的关键4 子序列问题如果是连续子序列问题，可以查看 KMP 算法如果是两个字符串相关的比较，将连个字符串构成一个 二维的数组可罗列所有的状态一般来说永远推荐把 dp[j]定义为 nums[j - 1]为结尾的 xxx 状态，这样可以省去一个初始化特判的过程之后的 for 循环只需要从 1 遍历到 nums.size() + 1即可4.1 LCS 最长子序列最长子序列问题：考虑删除这唯一一个操作删除表示不在某一个字符串中考虑这个字符，也就是在对应的 dp 数组中向上回退一个数字不同的题目需要注意删除这个操作对 dp 数组内容的影响4.2 编辑距离编辑距离就是 删除操作会导致一个操作数 + 1编辑距离的另一个主要特点就是： 操作是相互的，也就是删除 a 的一个元素，等价于给 b 增加一个元素另外，如果替换一个字符，等于消耗一个操作，将两个字符变成相等因此总结来看，终究还是删除和相等两种操作，关键在于需要学会定义 dp 数组为 nums[i - 1] 对应的 xxx4.3 回文串回文串的特点是他的状态转移不是取决于某一个值的加入，而是第一个值和最后一个值的加入意思是状态转移时设定 dp[i][j] 代表 [i, j) 的字符串是不是回文串的时候，其依赖的状态是 dp[i + 1][j - 1]5 经典题目之前从来没有接触过动态规划，所以可能选择的题目相对多一些5.1 爬楼梯LeetCode 70统计爬楼梯次数，例如 第 3 层只能由第 2 层或者第 1 层爬上来，这就构成了递推关系dp 数组：索引代表第几个台阶，数值代表需要的步数递推公式： 上两个台阶的次数求和数组初始化：dp[1] = 1, dp[2] = 2遍历顺序：顺序如果使用循环变量的方式，实际使用方法是和斐波那契的反过来的（因为初始值不同了所有有影响）其实 dp 的题目也不一定要优化，那样初始化逻辑会更加清晰明了class Solution { public: int climbStairs(int n) { // 同样使用两个内存就可以了 vector<int> dp(2, 0); dp[0] = 1; dp[1] = 2; int ret = 0; if (n < 3) return n; for (int i = 2; i < n; i++) { // 注意这里的滚动 ret = dp[0] + dp[1]; dp[0] = dp[1]; dp[1] = ret; } return ret; } };5.2 不同的二叉搜索树LeetCode 96可能从这里开始递归关系相对开始复杂了遍历所有数值作为根节点，然后左右子树的 dp 数量相乘这里似乎能够看出来，dp 的本质是用过去的状态推导现在的状态（有点像递归经典汉诺塔？）class Solution { public: int numTrees(int n) { vector<int> dp(n + 1 , 0); dp[0] = 1; dp[1] = 1; for (int i = 2; i < n + 1; i++) { for (int j = 1; j <= i; j++) { // 左右子树分别数量相乘 dp[i] += dp[j - 1] * dp[i - j]; } } return dp[n]; } };5.3 分割等和子集LeetCode 416这是一个 01 背包问题，将数值同时视作价值和重量，在理解这个的问题上花了很多时间，实际上是在给定的上限中尽可能的取到最靠近上限的指标，只不过上限和指标都是同一个数值组成的如果把 容量和价值都设置为数值，那么就指的是在给定的上限下，取到最靠近上限的一个值dp 数组的含义是背包容量为 j 能够装下物品的最大价值，class Solution { public: bool canPartition(vector<int>& nums) { // 01 背包，容量和价值相等，滚动数组方式 int sum = 0; for (int& a : nums) sum += a; if (sum % 2) return false; // 容量下标直接代表容量，所以要 + 1 int items = nums.size(); int volume = sum / 2; vector<int> dp(volume + 1, 0); // 初始化应该全部是0，已经完成了 for (int i = 0; i < items; i++) { for (int j = volume; j>= nums[i]; j--) { // 这里要保证当前物品放得进去，并把判断放进循环 dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); // 这里第二个 num[i] 是价值 } } return dp[volume] == volume; } };5.4 目标和LeetCode 494本题的关键点在于，所有的正数之和应该等于 (sum + target) / 2， 随后转化为 01 背包问题指定 dp 数组的含义是 dp[i][j] 代表 选取前 i 个物品构成和为 j 的可能性计数可以得到递推公式 dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]]，分别表示是否加入当前数组随后就可以简化为 一维数组class Solution { public: int findTargetSumWays(vector<int>& nums, int target) { int sum = 0; for (int &a : nums) sum += a; // 如果 target 绝对值大于 sum，肯定无解 if (abs(target) > sum) return 0; if ((sum + target) % 2 != 0) return 0; int pos = (sum + target) / 2; // 所有被赋予正号的数之和 vector<int> dp(pos + 1, 0); dp[0] = 1; // 装满容量为 0 的背包有 1 种方法：什么都不选 for (int i = 0; i < (int)nums.size(); i++) { for (int j = pos; j >= nums[i]; j--) { // 当前位置 j 的方案数 += 选择当前物品后的方案数 dp[j] += dp[j - nums[i]]; } } return dp[pos]; } };5.5 完全平方数LeetCode 279注意递推关系， + 1 并取最最小值class Solution { public: int numSquares(int n) { // 完全背包，最小值 int max = sqrt(n) + 1; vector<int> dp(n + 1, INT_MAX); dp[0] = 0; for (int i = 1; i <= max; i++) { int sq = i * i; for (int j = sq; j <= n; j++) { dp[j] = min(dp[j], dp[j - sq] + 1); // 不要忘了这里 + 1 } } return dp[n]; } };5.6 单词拆分本质还是把每一个小词当作一个物品，背包容量是整个字符串这里可以记忆一下 string 的库函数比较s.compare(pos, len, target) 表示 从字符串 s 的位置 pos 开始，取长度 len 的字串进行比较 target注意这个返回值是 int 不是 bool ，在两者相等的时候返回 0class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { int n = s.size(); vector<bool> dp(n + 1, false); dp[0] = true; for (int j = 1; j <= n; j++) { for (const auto& w : wordDict) { int len = w.size(); if (j >= len && dp[j - len]) { // s 的子串 [j-len, j) 是否等于 w if (s.compare(j - len, len, w) == 0) { dp[j] = true; break; } } } } return dp[n]; } };5.7 打家劫舍 IIILeetCode 337树形 dp 的基础题目，之前一直使用的是在一维数组中进行 dp 的规划，现在是树形中的通过递归可以实现每个层单独一个 dp 数组，但是因为递归会自动保留参数，所以每层中间信息是共享的dp[0] 是不偷， dp[1] 是偷的最大金钱class Solution { public: int rob(TreeNode* root) { // 左右的孩子节点，递归返回 dp 数组 vector<int> ret = reverseTraversal(root); return max(ret[0], ret[1]); } vector<int> reverseTraversal(TreeNode* root) { // 0 代表没有偷， 1 代表偷了 vector<int> dp(2, 0); if (root == nullptr) return dp; vector<int> left = reverseTraversal(root->left); vector<int> right = reverseTraversal(root->right); dp[1] = left[0] + right[0] + root->val; dp[0] = max(left[0], left[1]) + max(right[0], right[1]); // 这里要注意，取最大的，不一定要偷左右孩子 return dp; } };5.8 买卖股票的最佳时机LeetCode 121这道题简单，但是我们抛砖引玉一下，用 dp 的方法来计算这一类的问题这个 dp 数组的定义比较抽象，主要是为了能够包含所有的状态（例如定义第 i 天卖出的收益，那么什么都不做，怎么用第 i 天卖出这个定义表示呢？）dp[i][0] 表示第 i 天不持有这个股票的最大现金，而 dp[i][1]表示持有下的最大现金，注意这里是持有，不一定是当天进行了买卖初始化：dp[0][0] = 0, dp[0][1] = - price[0]递推公式：dp[i][0] = dp[i - 1][0] 表示今天不执行任何操作dp[i][0] = dp[i - 1][1] + price[i] 表示把股票卖了dp[i][1] = dp[i - 1][0]- price[i] 表示第 i 天买入了这个股票（本题只买卖一次，所以必须等于 - price[i]）dp[i][1] = dp[i - 1][1] 不执行任何操作上述分别取最大值就是递推公式递归顺序：常规从前到后即可class Solution { public: int maxProfit(vector<int>& prices) { vector<vector<int>> dp(prices.size(), vector<int>(2, 0)); dp[0][1] = -prices[0]; for (int i = 1; i < prices.size(); i++) { dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]); dp[i][1] = max(dp[i - 1][1], - prices[i]); // 只允许买入一次 } return dp[prices.size() - 1][0]; } };5.9 最长递增子序列LeetCode 300这题目是很经典的 dp 题目，难点在怎么定义 dp 数组很多题目都用 结尾 作为 dp 数组的定义，实际原因是，这类题型只有末尾才能够构成严格递推关系，因为很多时候长度不固定的，定义开头无法确定递推；但是由于前 n 个的最优解一定包含在前 n+1 当中定义：以 num[i] 结尾的最长子序列的长度，因为计算递增一定要有一个末尾固定才好算递推公式：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1; ，每一个都要把前面的数字的全部统计一次初始化：序列的长度肯定至少都是 1，剩下的取最大值就可以更新遍历顺序：根据公式肯定是从前向后这是这道题的 dp 写法，复杂度 $O(n^2)$ 这道题实际上还有个二分优化的方法，不过日后再写吧class Solution { public: int lengthOfLIS(vector<int>& nums) { // dp vector<int> dp(nums.size(), 1); // 全部初始化为1 int ret = 1; for (int i = 1; i < nums.size(); i++) { for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) // 从前面取一个末尾小于本体，然后 + 1 dp[i] = max(dp[i], dp[j] + 1); } ret = max(ret, dp[i]); } return ret; } };5.10 最长重复子数组LeetCode 718这里能够总结出一个经验，就是把无效的状态全部都塞进 0 的位置，可以省去很多麻烦的初始化步骤例如本题目把 dp[i][j] 定义为 下标 [i - 1] [j - 1] 的数组的最长重复子数组，可以省去初始化部分class Solution { public: int findLength(vector<int>& nums1, vector<int>& nums2) { int n = nums1.size(), m = nums2.size(); // 初始化注意要 + 1 vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0)); int ret = 0; // 从 1 开始，不用考虑边界，同时覆盖了所有可能的解 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (nums1[i - 1] == nums2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; ret = max(ret, dp[i][j]); } } } return ret; } };5.11 编辑距离LeetCode 72编辑距离，这是一维优化后的解法，详细可以参考开头的内容class Solution { public: int minDistance(string word1, string word2) { // 编辑距离 一维优化 // 尤其注意在横纵的初始值都不是 0 的时候，纵向初始值在 1 维 dp 每一轮都要修正 int m = word1.size(); int n = word2.size(); vector<int> dp(n + 1, 0); for (int j = 0; j <= n; j++) dp[j] = j; for (int i = 1; i <= m; i++) { int pre = dp[0]; // 对于本轮来说是 dp[1 - 1][j - 1]; dp[0] = i; // dp[0] 需要随着 i 轮次进行更新，为下一轮的 pre 准备 for (int j = 1; j <= n; j++) { int tmp = dp[j]; // 保存下一回的 dp[i - 1][j - 1]; if (word1[i - 1] == word2[j - 1]) { dp[j] = pre; // 来自上一回的 dp[i - 1][j - 1] } else { dp[j] = min({dp[j - 1], dp[j], pre}) + 1; } pre = tmp; // cout << dp[j] << ' '; } // cout << endl; } return dp[n]; } };5.12 最长回文子序列LeetCode 516看到子序列基本上就是 dp 的解法了具体的状态转移可以参见开头写的子序列问题，这是 LeetCode 的官方解法class Solution { public: int longestPalindromeSubseq(string s) { int n = s.length(); vector<vector<int>> dp(n, vector<int>(n)); for (int i = n - 1; i >= 0; i--) { dp[i][i] = 1; for (int j = i + 1; j < n; j++) { 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][n - 1]; } };6 总结这类题目的难点在于是不是能够合理的猜想出一个可行的 dp 数组定义，这很依赖经验另外，如果有了一个 dp 数组定义的想法了，我的建议是写一个 一般一点的例子 来列出整个 dp 数组我的意思是，相比于对着逻辑进行直接推到状态转移的关系，有时候瞪眼法看看数组找规律也许很有效（也就是猜一个转移过程来证明一下，对于复杂一点的题目可能会好写一点）
贪心算法1 简介贪⼼的本质是选择每⼀阶段的局部最优，从⽽达到全局最优。和贪心像对应的是动态规划，例如经典的背包问题，会在下一次笔记中记录什么时候用贪心，什么时候用动态规划呢？通过局部最优实现整体最优的情况一般来说很难证明这一点，只能通过经验判断2 解题步骤将问题分解为若⼲个⼦问题找出适合的贪⼼策略求解每⼀个⼦问题的最优解将局部最优解堆叠成全局最优解但是实际上只要想清楚局部最优和全局最优，就已经足够了3 经典题目3.1 摆动序列Leetcode 376摆动序列有三种情况：正常的上下坡度有平坡的上下摆动单调坡度中出现了平坡对每一个情况单独分析即可class Solution { public: int wiggleMaxLength(vector<int>& nums) { int prediff = 0; // 构造个虚拟的 pre 处理第一个 int curdiff = 0; int result = 1; // 最后一个自动计算 // 最后一个数字不进入循环 for (int i = 0; i < nums.size() - 1; i++) { curdiff = nums[i] - nums[i + 1]; // 使用 = 表示一边出现平坡，这种节点需要计算 if ((prediff <= 0 && curdiff > 0) || (prediff >= 0 && curdiff < 0)) { result++; prediff = curdiff; // 只在坡度变化时记录，避免单调平坡 } } return result; } };3.2 跳跃游戏 IILeetcode 45维护两个距离，如果到达了前一个距离的最大值，就要更新步数，同时把下一个改成前一个class Solution { public: int jump(vector<int>& nums) { // 维护一个两个最大位置，只要到达了 currdis 的最大距离，就需要 + 1 步数 int currdis = 0; int nextdis = 0; int ans = 0; if (nums.size() == 1) return 0; for (int i = 0; i < nums.size(); i++) { nextdis = max(i + nums[i], nextdis); // 这里记得取最大值 // 走到了最远的距离，需要更新 if (i == currdis) { ans++; currdis = nextdis; } if (currdis >= nums.size() - 1) { return ans; } } return -1; } };3.3 分发糖果Leetcode 135贪心，分为正向和反向两种，第一次考虑正向局部最优，第二次考虑反向局部最优化在第二次的时候徐需要使用 max 来同时不破坏第一次的局部最优化#include <vector> using namespace std; class Solution { public: int candy(vector<int>& ratings) { // 先全部设置为1 // 直接计算相邻的就行 int sum = 0; int pre = 0; // 上一个人的糖果数量 // 正向遍历 vector<int> candy(ratings.size(), 0); for (int i = 0; i < ratings.size(); i++) { if (i > 0 && ratings[i] > ratings[i - 1]) { // 比上一个分高 candy[i] = candy[i - 1] + 1; } else { // 不高或者第一个，只给 1 candy[i] = 1; } } // 反过来再来一次 for (int i = ratings.size() - 1; i >= 0; i--) { if (i < ratings.size() - 1 && ratings[i] > ratings[i + 1]) { // 比上一个分高，有可能会更新，两者取最大值 candy[i] = max(candy[i], candy[i + 1] + 1); } } for (int c : candy) { sum += c; } return sum; } };3.4 根据身高重建队列Leetcode 406这道题目有两个维度，如果出现了两个维度，一定要将一个维度确定了再考虑另一个尝试将两个维度都分别排序，然后发现按照身高进行排序能够直接确定一个维度（实际解题可以两者都尝试）有两个关键特性：如果身高比前面的小，那么可以随意插队，不影响已经排序的数据（所以要先按照身高排序）在已经排序的情况下，按照 k 进行重定位，一定能保证被插入的元素前面符合条件（按顺序插入）综上两条，如果先排序，再按照顺序插入，则可以满足整个队伍的条件#include <vector> #include #include <algorithm> using namespace std; class Solution { public: static bool cmp(vector<int> a, vector<int> b) { // 比较身高，身高从大到小，相同则k从小到大 if (a[0] != b[0]) { return a[0] > b[0]; } else { return a[1] < b[1]; } } vector<vector<int>> reconstructQueue(vector<vector<int>>& people) { // 使用链表，操作完毕更改成vector sort(people.begin(), people.end(), cmp); list<vector<int>> que; for (vector<int> p : people) { auto it = que.begin(); // list 的 it 只能一个个加 for (int j = 0; j < p[1]; j++) it++; que.insert(it, p); } return vector<vector<int>>(que.begin(), que.end()); } };3.5 单调递增的数字LeetCode 738关键还是想清楚逻辑一旦高位出现不递增的情况，高位 - 1，同时全部低位直接设置成 9 即可class Solution { public: int monotoneIncreasingDigits(int n) { // 如果高位不符合，改全部低位为9，将高位 - 1 string nums = to_string(n); int flag = nums.size(); // 表示低位全部标记为9 for (int i = nums.size() - 1; i > 0; i--) { if (nums[i] < nums[i - 1]) { nums[i - 1]--; flag = i; } } for (int i = flag; i < nums.size(); i++) { nums[i] = '9'; } return stoi(nums); } };3.6 监控二叉树LeetCode 968劲爆尾杀，做这题要很强的抽象建模能力，总结来是有两点：从叶子节点出发，每两个放一个摄像头，可以尽可能的监控更多将每一个节点状态分成：摄像头，被覆盖，无覆盖三种情况，并分别讨论每种情况的处理既然是叶子结点，那就是后序遍历，然后返回值设置为状态class Solution { public: // 0 无覆盖 1 有摄像头 2 有覆盖 // 使用后序遍历 int minCameraCover(TreeNode* root) { int count = 0; int r = last_traversal(root, count); if (r == 0) count++; // 根节点没有被覆盖 return count; } // Post Order Traversal int last_traversal(TreeNode* root, int& count) { if (!root) return 2; // null 视为有覆盖 // 后序遍历，可以获得子节点的状态信息 int l = last_traversal(root->left, count); int r = last_traversal(root->right, count); // 注意这三个顺序不可以颠倒！ // 只要有个未被覆盖就需要装摄像头 if (l == 0 || r == 0) { count++; return 1; } // 装了摄像头就不用装 if (l == 1 || r == 1) return 2; // 有覆盖 需要交给父节点装摄像头 if (l == 2 || r == 2) return 0; return -1; } };4 总结贪心没有什么特定的套路，倒不如说更加考验问题抽象建模的能力也许是我做题太少，我还没能力进行很好的总结，也许日后再写这一部分吧
回溯算法回溯算法是暴力算法的一种，实际效率并不高，只是一种没有办法的办法1 解题步骤回溯算法可以说就是递归 + for 循环，大多都可以抽象成树的形式，在上一章的基础上构建 for 循环解决的都是在集合中递归查找⼦集，集合的⼤⼩就构成了树的宽度，递归的深度，构成的树的深度。回溯算法三部曲：回溯的返回一般都是 void，⼀般是先写逻辑，然后需要什么参数，就填什么参数终止条件，一般是找到一个符合条件的数值的时候遍历过程：横向外层 for 遍历宽度，纵向递归遍历深度void backtracking(参数) { if (终⽌条件) { 存放结果; return; } for (选择：本层集合中元素（树中节点孩⼦的数量就是集合的⼤⼩）) { 处理节点; backtracking(路径，选择列表); // 递归 回溯，撤销处理结果 }2 题目选取2.1 组合总和 II带去重的组合，需要理解组合的本质同一层上，不允许取两个相同的数：因为不同 case 取同一个数，本质没有区别在深度上，允许取两个相同的数字：因为同一个 case 内，同个数字取值本质上有区别注意：树层的去重，需要进行排序class Solution { /* 横向不允许相同数字，去重需要排序 纵向允许相同数字，用 start 实现 */ public: vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { path.clear(); ret.clear(); sort(candidates.begin(), candidates.end()); traceback(0, candidates, target); return ret; } vector<bool> used; vector<int> path; vector<vector<int>> ret; void traceback(int start, const vector<int>& candidates, int remain) { if (remain < 0) return; if (remain == 0) { ret.push_back(path); return; } for (int i = start; i < candidates.size(); i++) { // 注意这里的去重逻辑，要和 start 比较 if (i > start && candidates[i - 1] == candidates[i]) { // 表示存在上一个数字, 且相等，横向跳过，不可以修改循环边界 start continue; } // 数组排序剪枝 if (candidates[i] > remain) break; remain -= candidates[i]; path.push_back(candidates[i]); // 纵向，使用 used 去重？ traceback(i + 1, candidates, remain); remain += candidates[i]; path.pop_back(); } } };2.2 分割字符串类（回文串）这类问题主要关注 不同的 path 定义，以及循环的条件实际上就是放隔板问题，但是要考虑好隔板怎么能够在代码中实现这里使用思路：左闭右开区间，左有两个索引固定，在循环开始时候分割，重点位置在注释中标出class Solution { public: vector<vector<string>> partition(string s) { auto curr = s.begin(); traceback(s, curr); return ret; } vector<vector<string>> ret; vector<string> path; void traceback(const string& s, string::iterator curr) { if ((curr - s.begin()) >= s.size()) { // 数量满足，终止条件 ret.push_back(path); return; } // 这里的 for 循环已经实现了 + 1 逻辑，外层不能 + 1 // 左闭右开区间，+ 1 代表仅纳入了一个字符 for (auto i = curr + 1; i <= s.end(); i++) { if (is_palindrome(curr, i)) { // 是回文，加入并递归，（也就是先判断再加入组合 path） path.push_back(string(curr, i)); traceback(s, i); // 左闭右开， + 1 逻辑在 for 循环实现 path.pop_back(); } else { continue; } } } bool is_palindrome(string::iterator first, string::iterator last) { if (first == last) return true; // 空串 --last; // 右开变右闭 while (first < last) { if (*first != *last) return false; ++first; --last; } return true; } };2.3 非递减子序列本题是横向去重的典型例子主要在于如何进行层内去重，重点是掌握层内的作用区间：for 循环内，调用递归值之前#include <vector> #include <unordered_set> class Solution { public: vector<vector<int>> findSubsequences(vector<int>& nums) { ret.clear(); path.clear(); backtrack(0, INT_MIN, nums); return ret; } vector<vector<int>> ret; vector<int> path; void backtrack(int start, int pre, vector<int>& nums) { // pre 代表上一数字 if (path.size() > 1) { ret.push_back(path); } int i = start; unordered_set<int> used; // 递归层内变量 for (int i = start; i < nums.size(); i++) { // 本层内去重 if (used.count(nums[i])) continue; if (pre > nums[i]) continue; used.insert(nums[i]); path.push_back(nums[i]); backtrack(i + 1, nums[i], nums); path.pop_back(); } } }; 2.4 全排列去重非常独特的一个横纵结合的去重逻辑排列不可以使用 startIndex，因为要遍历所有的节点纵向不可以使用用过的下标值横向去重需要考虑纵向是否使用过该数值，使用过则解禁，没用过则需要去重注意条件满足需要返回，因为需要在叶子节点切断递归class Solution { public: vector<vector<int>> permuteUnique(vector<int>& nums) { ret.clear(); path.clear(); sort(nums.begin(), nums.end()); vector<bool> used(nums.size(), false); traceback(used, nums); return ret; } vector<vector<int>> ret; vector<int> path; // 纵向不可以使用相同元素 // 横向去除同数值但下标不同元素 void traceback(vector<bool>& used, const vector<int>& nums) { if (path.size() == nums.size()) { ret.push_back(path); return; // 这里要切断递归，是终止条件 } for (int i = 0; i < nums.size(); i++) { if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) { // 指的是纵向没有使用过，并且横向数值相同（所以要排序） // 纵向使用过就可以再次使用了 continue; } if (used[i]) continue; // 纵向去重 int curr = nums[i]; path.push_back(curr); used[i] = true; traceback(used, nums); used[i] = false; path.pop_back(); } } };3 总结3.1 什么时候需要 startIndex？需要横向去重的时候，有时候会配合排序来执行数值去重3.2 纵向横向去重分别怎么实现？3.2.1 纵向纵向去重，使用 bool 类型 used 标记即可，注意 used 是全局变量vector<bool> used; // 需要初始化为全 fasle void backtrace() { if (...) {} for (int i = 0; i < value.size(); i++) { if (used[i]) continue; used[i] = true; backtrace(); // 使用 used 包裹，回溯退出需要回退状态 used[i] = false; } }3.2.2 横向没有重复元素，在递归时候传递 startIndex + 1 即可void backtrace(int startIndex) { if (...) {} for (int i = startIndex; i < end; i++) { ...; backtrace(startIndex + 1); ...; } }有重复元素，可以排序后额外判断与上一个是否相等sort(value.begin(), value.end()); void backtrace(int startIndex) { if (...) {} for (int i = startIndex; i < value.size(); i++) { if (i > 0 && value[i] == value[i - 1]) continue; // 去重 ...; backtrace(startIndex + 1); } }3.3 返回值3.3.1 什么时候 returnreturn 的唯一逻辑是：无路可走这条节点已经失败了3.3.2 不同位置的 returnif终止条件：需要继续搜索 → return（存答案以后继续兄弟分支）不需要继续搜索 → return true（直接停止整个搜索）for 循环内部：当前分支无效但下一分支还有希望 → continue当前分支无效且后续分支也无希望 → return（剪枝）如果需要获取所有节点，可以在 if 下写 return 而是通过 for 的逻辑进行控制3.3.3 返回值设置绝大多数情况都是 void除非找到一种情况立刻返回，此时使用 bool，同时递归写法也会改变if (traceback(...)) return true;
二叉树二叉树是常见的底层数据结构，也是递归的重要应用场景1 种类满二叉树：所有节点都齐全的一个二叉树完全二叉树：除了底层全部都满，并且 从左到右 连续有节点，满二叉树一定是完全二叉树 二叉搜索树：搜索效率是 O(log n)，节点元素有顺序，可以是左小右大平衡二叉树：左子树高度和右子树高度差绝对值 小于 1在 C++ 中 std::set / std::multiset / std::map / std::multimap 都由红黑树（自平衡二叉搜索树）下方演示了如何判断平衡二叉搜索树2 存储方式2.1 链式使用左右指针即可，如果没有孩子则为 nullptr代码实现如下：struct TreeNode { int val; // 节点值 TreeNode* left; // 左子节点 TreeNode* right; // 右子节点 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} // 构造函数 };2.2 线性线性存储唯一要注意的就是如何计算左右孩子，（实际上不太会用这种方式存储）假设根节点是编号 i ，左孩子的 2i + 1， 右孩子 2i + 23 遍历方式3.1 深度优先搜索（DFS）一般使用的 前中后序遍历都属于 DFS，可以使用递归或者迭代的方式实现，本质是栈 FILO前中后指的是父节点的访问顺序前序遍历： 中左右，前序遍历是按照数据结构来顺序处理节点，迭代逻辑最简单中序遍历：左中右，中序遍历对二叉搜索树有排序的作用后序遍历：左右中，后序遍历有回溯的功能，能够实现类似从下向上遍历的功能下面是两种方式实现中序遍历，注意中序遍历能够获得二叉搜索树排序后的结果#include <vector> void inorderRecursive(TreeNode* root, std::vector<int>& res) { if (!root) return; inorderRecursive(root->left, res); res.push_back(root->val); inorderRecursive(root->right, res); }前序遍历的 DFS （迭代）要更加简单一点，因为访问和处理的节点都是同一个#include <vector> #include <stack> using namespace std; class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> ret; if (!root) return ret; stack<TreeNode*> stk; stk.push(root); while (!stk.empty()) { TreeNode* curr = stk.top(); stk.pop(); ret.push_back(curr->val); if (curr->right) stk.push(curr->right); if (curr->left) stk.push(curr->left); } return ret; } };后序遍历有两步：将前序左右子树访问顺序交换： 中左右 -> 中右左将结果翻转（双指针）： 左右中中序遍历要复杂一点，需要借助指针深度访问到底，再进行对应处理// 迭代法中序遍历 #include <stack> #include <vector> std::vector<int> inorderIterative(TreeNode* root) { std::vector<int> res; std::stack<TreeNode*> st; TreeNode* curr = root; while (curr || !st.empty()) { // 一直向左走 while (curr) { st.push(curr); curr = curr->left; } // 访问栈顶节点 curr = st.top(); st.pop(); res.push_back(curr->val); // 转向右子树 curr = curr->right; } return res; }也有一种使用标记法的方式，可以使用同一个代码结构完成 3 种遍历，稍微难理解一点3.2 广度优先搜索 （BFS）层序遍历，就是使用迭代法进行，本质是使用队列的 LIFO注意的是需要记住每一层的队列中的元素个数#include <vector> #include <queue> class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { queue<TreeNode*> q; vector<vector<int>> ret; if (!root) return ret; q.push(root); while(!q.empty()) { // 取出所有的子节点 vector<int> ret_layer; int current = q.size(); for (int i = 0; i < current; i++) { TreeNode* cur = q.front(); q.pop(); if (cur->left) q.push(cur->left); if (cur->right) q.push(cur->right); ret_layer.push_back(cur->val); } ret.push_back(ret_layer); } return ret; } };4 题目选取挑选一些初见不是很顺利的题记录一下递归的要义：返回值和输入参数终止条件递归细化逻辑4.1 平衡二叉树（求深度）力扣平衡二叉树平衡二叉树是左右子树 高度 差 不大于 1主要知识点：求 高度 需要使用 后序遍历 ， 求 深度 使用 前序遍历 原因： 后序遍历，根节点最后遍历，层层向上返回，根节点根据左右孩子的数据来计算；反之则是孩子获取到根节点的深度#include <cmath> class Solution { public: bool isBalanced(TreeNode* root) { if(getHeight (root) >= 0) { return true; } else { return false; } } int getHeight(TreeNode *curr) { // 获取高度，如果不平衡直接返回 -1 // 高度要使用后序遍历 if (curr == nullptr) return 0; int left = getHeight(curr->left); int right = getHeight(curr->right); if (left == -1 || right == -1) return -1; if (abs(left - right) > 1) { return -1; } else { return (left > right ? left : right) + 1; } } };4.2 中序后序构造二叉树总体逻辑是轮流进行分割，需要注意的是先要确定返回条件，设置为 root 节点后序遍历最后一个就是根节点的值根据这个值来构造一个节点根据这个值去将中序数组切割成左右两部分根据中序的值将后序的左右部分分开进一步递归（中序左，后序左）（中序右，后序右），分别是左右孩子注意到这里为了代码可读性，每次都进行一个复制操作。实际可以优化为每次都传递索引值class Solution { public: TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { if (!postorder.size()) return nullptr; return _buildTree(inorder, postorder); } TreeNode* _buildTree(vector<int> inorder, vector<int> postorder) { // 数组为空代表已经完毕 if (postorder.size() == 0) { return nullptr; } // 1 后序遍历最后一个数字取出，构造根节点 int sz = postorder.size(); int cut1 = postorder[sz -1]; postorder.pop_back(); TreeNode* root = new TreeNode(cut1); // 2. 分割中序 int i = 0; for (; i < inorder.size(); i++) { if (inorder[i] == cut1) break; } vector<int> in_left(inorder.begin(), inorder.begin() + i); vector<int> in_right(inorder.begin() + i + 1, inorder.end()); // 3. 按照左边 size 分割后序 vector<int> post_left(postorder.begin(), postorder.begin() + i); vector<int> post_right(postorder.begin() + i, postorder.end()); // 递归并构造 root->left = _buildTree(in_left, post_left); root->right = _buildTree(in_right, post_right); return root; } };4.3 二叉搜索树 BST判断一个 BST 是否是有效，使用递归关键在于想清楚 当前最大值的逻辑class Solution { public: bool isValidBST(TreeNode* root) { long long maxVal = LONG_MIN; return _isValidBST(root, maxVal); } bool _isValidBST(TreeNode* root, long long& max) { if (!root) return true; // 中序遍历 bool left = _isValidBST(root->left, max); if (root->val <= max) return false; else max = root->val; bool right = _isValidBST(root->right, max); return left && right; } };4.4 二叉树的最近公共祖先这道题的回溯返回值很精妙，应该时常复习因为二叉树只能从根节点从上往下，所以使用回溯的思想，也就是后序遍历左右子树如果出现了目标元素就返回值，否则返回空；如果一个节点左右子树都出现了返回值，那代表是公共祖先参数返回：根节点，返回 nullptr或者对应的节点终止条件：返回节点则继续上报class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { // 终止递归条件：空节点或者已经找到 if (!root) return nullptr; if (root == p || root == q) return root; TreeNode* left = lowestCommonAncestor(root->left, p, q); TreeNode* right = lowestCommonAncestor(root->right, p, q); // 已经找到 if (left && right) { return root; } // 传递返回已经找到的值, nullptr 也会正确返回 return left ? left : right; } };4.5 二叉搜索树的插入添加节点相对简单，不需要改变原有的树结构使用递归方法可能会把方法想的很复杂，但是实际上很简单，记住就行class Solution { public: TreeNode* insertIntoBST(TreeNode* root, int val) { if (root == nullptr) { TreeNode* ret = new TreeNode(val); return ret; } if (val > root->val) root->right = insertIntoBST(root->right, val); if (val < root->val) root->left = insertIntoBST(root->left, val); return root; } };4.6 删除二叉搜索树的节点情况很多，比添加复杂得多，需要考虑很多的情况一共有五种情况：没有找到，不用删除删除叶子节点，直接设为 nullptr左非空右空，将父节点的左孩子指向被删的孩子左空右非空，同理跳过被删节点直接指向孩子左右都非空，最复杂的，让右子树继位，左子树找到右子树的最左侧的节点（右子树中最小的位置），接上。返回值设置为节点指针，外层需要接住，这样可以很方便地修改二叉树的结构class Solution { public: TreeNode* deleteNode(TreeNode* root, int key) { // 返回的节点通过外层接住 // 终止条件就是所有的删除逻辑 if (root == nullptr) return nullptr; if (root->val == key) { // 找到了 if (!root->right && !root->left) { delete root; return nullptr; } else if (!root->right && root->left) { // 只有左边节点 TreeNode* tmp = root->left; delete root; return tmp; } else if (!root->left && root->right) { // 只有右边节点 TreeNode* tmp = root->right; delete root; return tmp; } else { // 右节点继承，左子树全移动到最左下方 TreeNode* curr = root->right; while (curr->left) { curr = curr->left; } curr->left = root->left; TreeNode* tmp = root->right; delete root; return tmp; } } // 递归逻辑 if (root->val < key) root->right = deleteNode(root->right, key); if (root->val > key) root->left = deleteNode(root->left, key); return root; } };4.7 修剪二叉搜索树让节点中所有的数值保持在给定的区间内，同时不应该改变原有的树的结构修建二叉树对结构需要重新修改，会稍微复杂一点不可以在某个节点不符合条件时候直接删除并返回nullptr，因为其孩子是有可能符合区间条件的注意：不需要在 LeetCode 中处理内存释放问题正确逻辑：如果本节点小于下界，应该向右遍历（其右孩子是有可能符合条件的），大于同理如果符合条件，正常处理左右子树class Solution { public: TreeNode* trimBST(TreeNode* root, int low, int high) { if (!root) return nullptr; if (root->val < low) { // 从右子树继续递归，删除本节点 return trimBST(root->right, low, high); } else if (root->val > high) { return trimBST(root->left, low, high); } root->right = trimBST(root->right, low, high); root->left = trimBST(root->left, low, high); return root; } };4.8 有序数组转换为二叉平衡搜索树有一些点需要注意，思考一下什么时候不需要将根节点传入作为参数？为什么本题不需要通过判断传入参数来 return nullptrclass Solution { public: TreeNode* sortedArrayToBST(vector<int>& nums) { int left = 0; int right = nums.size(); TreeNode* root = nullptr; root = _build(nums, left, right); return root; } TreeNode* _build(vector<int>& nums, int left, int right) { // 组里面没有元素了 if (left >= right) return nullptr; int mid = ((right - left) / 2) + left; // 构建中点，外层接住 TreeNode* curr = new TreeNode(nums[mid]); curr->left = _build(nums, left, mid); curr->right = _build(nums, mid + 1, right); return curr; } };5 易混淆点5.1 节点指针参数5.1.1 不需要传递节点指针当每次递归都独立创建或遍历子树，父节点仅需接收返回值挂接：TreeNode* build(const vector<int>& nums, int l, int r) { if (l >= r) return nullptr; int m = (l + r) / 2; TreeNode* root = new TreeNode(nums[m]); root->left = build(nums, l, m); root->right = build(nums, m + 1, r); return root; }每一层都独立产生节点，不依赖外层状态，不传当前节点指针。这种结构用于：构建树（如 sortedArrayToBST）查找并返回新根（如 trimBST、invertTree）需要改变结构并返回新子树时5.1.2 需要传递节点指针当函数要在原有节点基础上修改或统计信息，且操作依赖父层状态：void dfs(TreeNode* node, int depth, int& sum) { if (!node) return; if (!node->left && !node->right) sum += depth; dfs(node->left, depth + 1, sum); dfs(node->right, depth + 1, sum); }典型用途：访问或统计整棵树（遍历）回溯时要恢复状态需要知道父节点信息或方向（左/右）5.2 递归返回值不要返回值：搜索整棵⼆叉树且不用处理递归返回值需要返回值：搜索整棵⼆叉树且需要处理递归返回值必须有返回：遇到符合条件的路径了就要及时返回，例如搜索其中⼀条符合条件的路径只需要搜索⼀条边if (递归函数(root->left)) return ; if (递归函数(root->right)) return ;搜索整个树left = 递归函数(root->left); // 左 right = 递归函数(root->right); // 右 left与right的逻辑处理; // 中 5.2.1 返回 void当递归只是访问、打印、统计、累积而不改变结构，这种函数只是向外输出或修改外部变量，不需要返回子树。void preorder(TreeNode* node) { ... } void dfs(TreeNode* node, int& sum) { ... }5.2.2 返回 TreeNode*父节点要拿到新的子树根进行挂接，递归会改变树结构（删除、修剪、构造）：TreeNode* trimBST(TreeNode* root, int low, int high); TreeNode* invertTree(TreeNode* root); TreeNode* deleteNode(TreeNode* root, int key);5.2.3 返回 bool用于存在性判断 / 条件是否满足，当子树满足条件时应提前终止或者向上报告一旦有一个分支返回 true，整棵递归可结束。常用于“是否存在路径”、“是否对称”、“是否平衡”等问题。bool hasPathSum(TreeNode* node, int sum, int target) { if (!node) return false; sum += node->val; if (!node->left && !node->right) return sum == target; return hasPathSum(node->left, sum, target) || hasPathSum(node->right, sum, target); }5.2.4 返回其他类型常用于值的累积 / 特征汇总，常用于求高度、节点数、直径、最大路径和等。int maxDepth(TreeNode* node) { if (!node) return 0; int l = maxDepth(node->left); int r = maxDepth(node->right); return std::max(l, r) + 1; }