小雨淅沥 - 算法思路
type: channel
link: https://rainerseventeen.cn/index.php/category/Algorithm/
description: LeetCode 随笔
items: Hot 100 题解（二）
items: Hot 100 题解（一）
items: 算法题型：单调栈
items: 算法题型：动态规划
items: 算法题型：贪心算法
items: 算法题型：回溯算法
items: 算法题型：二叉树

Hot 100 题解（二）
type: item
date: 2026-01-10T12:55:00+08:00
description: 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) 之间的最优解…

Hot 100 题解（一）
type: item
date: 2026-01-05T20:19:00+08:00
description: 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): wh…

算法题型：单调栈
type: item
date: 2025-12-20T17:15:00+08:00
description: 单调栈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经典的单调栈题目，重点在于找到左右比他大（可以等于，其实不影响结果，因为都要减去中间柱子的高度）的值这是单调栈的…

算法题型：动态规划
type: item
date: 2025-12-15T14:36:00+08:00
description: 动态规划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…

算法题型：贪心算法
type: item
date: 2025-11-23T18:19:00+08:00
description: 贪心算法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这道题目有两个维度，如果出现了两个维度，一定要将一个维度确定了再考虑另一个尝试将两个维度都分别排序，然后发现按照身高进行排序能够直接确定一个维度（实际解题可以两者都尝试）有两个关键特性：如果身高比前面的小，那么可以随意插队，不影响已经排序的数据（所以要先…

算法题型：回溯算法
type: item
date: 2025-11-15T20:35:00+08:00
description: 回溯算法回溯算法是暴力算法的一种，实际效率并不高，只是一种没有办法的办法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); // 左…

算法题型：二叉树
type: item
date: 2025-10-24T20:29:00+08:00
description: 二叉树二叉树是常见的底层数据结构，也是递归的重要应用场景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(TreeNo…