打卡记录

56. 合并区间 链接：56. 合并区间 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 区间判重，更新 end； 看完题解后的想法 – 实现中遇到的困难 – 代码 class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { sort(intervals.begin(), intervals.end()); // 核心，先排序 int start = intervals[0][0]; int end = intervals[0][1]; vector<vector<int>> res; for (int i = 1; i < (int)intervals.size(); i++) { int left = intervals[i][0]; int right = intervals[i][1]; if (left <= end) { if (right > end) { end = right; } else { continue; } } else { res.push_back({start, end}); start = left; end = right; } } // 最后一组元素需要手动push res.push_back({start, end}); return res; } }; 738. 单调递增的数字 链接：738. 单调递增的数字 文章：代码随想录 视频：B站讲解 状态：⚠️ 第一想法 第一想法是拿个 vector 把数字都装起来，但是之后怎么做不明白； ...

452. 用最少数量的箭引爆气球 链接：452. 用最少数量的箭引爆气球 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 不断地调整起点和终点范围，如果任意一边（其实是起点，排序之后有序）在范围内，就可以被引爆； 注意如果终点也在范围内就要调整终点位置； 看完题解后的想法 – 实现中遇到的困难 – 代码 class Solution { public: int findMinArrowShots(vector<vector<int>>& points) { sort(points.begin(), points.end()); int sum = 1; int start = points[0][0]; int end = points[0][1]; for (int i = 1; i < points.size(); i++) { if (points[i][0] <= end) { start = points[i][0]; if (points[i][1] <= end) { end = points[i][1]; } } else { start = points[i][0]; end = points[i][1]; sum++; } } return sum; } }; 435. 无重叠区间 链接：435. 无重叠区间 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 跟 LC452 挺像的； ...

134. 加油站 链接：134. 加油站 文章：代码随想录 视频：B站讲解 状态：❌ 第一想法 没想出来； 看完题解后的想法 很巧妙，其实是思维盲区； 既然总油量大于等于总消耗有解，那么只要找到开始盈余的部分，这样剩下的油总能够支持消耗； 这里很巧妙，因为如果总量只要是大于等于，那不管前面亏了多少，后面一定剩了多少，只要不断舍去亏损的位置就行了； 和 LC53 是一个思想； 实现中遇到的困难 – 代码 class Solution { public: int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { int totalDiff = 0; int curDiff = 0; int start = 0; // 1. 如果总油量小于总消耗，不可能跑完 // 2. 既然总油量大于等于总消耗有解，那么就要找到开始盈余的部分，这样才能支撑跑完全程 for (int i = 0; i < gas.size(); i++) { totalDiff += gas[i] - cost[i]; curDiff += gas[i] - cost[i]; if (curDiff < 0) { start = i + 1; curDiff = 0; } } return totalDiff >= 0 ? start : -1; } }; 135. 分发糖果 链接：135. 分发糖果 文章：代码随想录 视频：B站讲解 状态：❌ 第一想法 没啥思路； ...

122. 买卖股票的最佳时机II 链接：122. 买卖股票的最佳时机II 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 连续上涨的利润等于每天差价之和 看完题解后的想法 – 实现中遇到的困难 – 代码 class Solution { public: int maxProfit(vector<int>& prices) { int profit = 0; for (int i = 1; i < prices.size(); i++) { // 只要后一天的股价高于前一天的股价就可以买进卖出，这样一定获利 // 多次交易只是把一段长的收入拆分成了几段小的 if (prices[i] > prices[i - 1]) { profit += prices[i] - prices[i-1]; } } return profit; } }; 55. 跳跃游戏 链接：55. 跳跃游戏 文章：代码随想录 视频：B站讲解 状态：❌ 第一想法 最开始在思考如何到达右边，然后写了一串复杂的判断； 看完题解后的想法 要点不是能不能过去，而是中间会不会断 那么如果某个点的坐标大于了之前所有点的坐标+跨度，就说明这个点到达不了，就断了 所以要维护一个 最大可达坐标 实现中遇到的困难 – 代码 class Solution { public: bool canJump(vector<int>& nums) { int maxReach = 0; for (int i = 0; i < nums.size(); i++) { // 如果当前最大可达坐标小于当前index，说明过不来，错误 if (i > maxReach) { return false; } // 更新当前最大可达坐标，这里的作用就是在这个点之后的点的跨度如果小于该点，也在该点的包括范围内 maxReach = max(maxReach, nums[i] + i); if (maxReach >= nums.size() - 1) { return true; } } return false; } }; 45. 跳跃游戏II 链接：45. 跳跃游戏II 文章：代码随想录 视频：B站讲解 状态：⚠️ 第一想法 可跳区域的左右是否夹了一个更大的可以跳出这个区域的点，如果有就说明可以去这个点，跳到更远的地方； ...

贪心算法理论基础 贪心算法没有固定套路，本质就是选择每一阶段的局部最优，从而达到全局最优。 文章：代码随想录 - 贪心算法理论基础 455. 分发饼干 链接：455. 分发饼干 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 始终用最小可满足的条件去满足匹配； 整体复杂度由排序主导； 看完题解后的想法 – 实现中遇到的困难 – 代码 class Solution { public: int findContentChildren(vector<int>& g, vector<int>& s) { // 排序后贪心 sort(g.begin(), g.end()); sort(s.begin(), s.end()); int index = 0; int res = 0; for (int i = 0; i < g.size(); i++) { while (index < s.size() && s[index] < g[i]) { index++; // 无法满足，skip } if (index < s.size()) { // 满足条件且index合法，分配 res++; index++; // 分配之后也要前进 } } return res; } }; 376. 摆动序列 链接：376. 摆动序列 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 遍历序列，找到每一个拐点；但是很难说清楚为什么这就是最长的； ...

491. 递增子序列 链接：491. 递增子序列 文章：代码随想录 视频：B站讲解 状态：❌ 第一想法 这题不能排序，同层去重又不会了； 看完题解后的想法 使用 set 记录本层使用过的数据，这是更加一般的同层去重； 实现中遇到的困难 不会非排序的同层去重； 代码 class Solution { public: vector<vector<int>> res; vector<int> path; void backtracking(vector<int>& nums, int index) { if (path.size() >= 2) { res.push_back(path); } unordered_set<int> used; // 每层一个，记录本层用过的值 for (int i = index; i < nums.size(); i++) { if ((!path.empty() && nums[i] < path.back()) || used.count(nums[i])) { continue; } used.insert(nums[i]); // 注意退栈不用 erase，因为还在当前层 path.push_back(nums[i]); backtracking(nums, i+1); path.pop_back(); } } vector<vector<int>> findSubsequences(vector<int>& nums) { backtracking(nums, 0); return res; } }; 46. 全排列 链接：46. 全排列 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 排列不需要传入 index，因为每次都是从头访问； ...

93. 复原IP地址 链接：93. 复原IP地址 文章：代码随想录 视频：B站讲解 状态：⚠️ 第一想法 和分割回文串类似，不是去构造一个合法的子串，而是去直接分割，不合法就 skip； 看完题解后的想法 – 实现中遇到的困难 最开始 path 是一个 str，对于 IP 地址要求的四段判断比较复杂； path 在这里也需要是 vector，这样回溯才方便；最后直接构造一个返回字符串就行； 代码 class Solution { public: bool isValid(string& s) { if (s.size() > 1 && s[0] == '0') return false; if (stoi(s) > 255) return false; return true; } vector<string> res; vector<string> path; void backtracking(string s, int index) { if (path.size() == 4) { if (index == s.size()) { res.push_back(path[0] + "." + path[1] + "." + path[2] + "." + path[3]); } return; // 不管是否收集，4段了就不再递归 } for (int i = index; i < s.size() && i - index < 3; i++) { string str = s.substr(index, i - index + 1); if (isValid(str)) { path.push_back(str); backtracking(s, i+1); path.pop_back(); } else { break; // 当前不合法后面更长也不合法 } } } vector<string> restoreIpAddresses(string s) { if (s.size() > 12 || s.size() < 4) { return res; } backtracking(s, 0); return res; } }; 78. 子集 链接：78. 子集 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 自己做的时候考虑到符合条件的子集大小是变动的，就在回溯外面套了一个 while 循环去增加 size； ...

39. 组合总和 链接：39. 组合总和 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 回溯三部曲； 看完题解后的想法 可以用排序加速剪枝； 实现中遇到的困难 – 代码 class Solution { public: vector<vector<int>> res; vector<int> path; void backtracking(vector<int>& candidates, int target, int index, int sum) { if (sum == target) { res.push_back(path); return; } for (int i = index; i < candidates.size() && sum + candidates[i] <= target; i++) { sum += candidates[i]; path.push_back(candidates[i]); backtracking(candidates, target, i, sum); sum -= candidates[i]; path.pop_back(); } } vector<vector<int>> combinationSum(vector<int>& candidates, int target) { sort(candidates.begin(), candidates.end()); backtracking(candidates, target, 0, 0); return res; } }; 40. 组合总和II 链接：40. 组合总和II 文章：代码随想录 视频：B站讲解 状态：⚠️ 第一想法 依旧回溯三部曲，但是注意同层去重逻辑； ...

回溯算法理论基础 文章：代码随想录 - 回溯算法理论基础 视频：B站讲解 77. 组合 链接：77. 组合 文章：代码随想录 视频：B站讲解 剪枝：B站讲解 状态：❌ 第一想法 第一想法是回溯，但是对于如何存 path，如何回溯有点摸不着头脑; 看完题解后的想法 不用复杂的递归返回，只把递归作为前进的路径，直接使用外部空间保存路径; 外部空间必须在退出递归时 pop 数据，这就是回溯; 实现中遇到的困难 剪枝条件写起来很复杂，但是搞清楚了如何剪枝就能马上写出来; 代码 class Solution { public: /* 回溯的模板可以这样理解： 1. 路径 (path)：当前已经选了哪些数 2. 选择列表：从 start 到 n，还能选哪些数 3. 结束条件：path.size() == k 时，收集结果 */ vector<vector<int>> res; vector<int> path; void backtracking(int n, int k, int start) { // 返回条件：找到k个数 if (path.size() == k) { res.push_back(path); return; } /* 剪枝优化： 当前已有数字 path.size() 个, 还需数字 k - path.size() 个 在 i 到 n 之间有 n - i + 1个数字 n - i + 1 >= k - path.size() */ for (int i = start; i <= n + 1 + path.size() - k; i++) { path.push_back(i); backtracking(n, k, i + 1); path.pop_back(); } } vector<vector<int>> combine(int n, int k) { backtracking(n, k, 1); return res; } }; 216. 组合总和III 链接：216. 组合总和III 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 回溯三部曲： ...

669. 修剪二叉搜索树 链接：669. 修剪二叉搜索树 文章：代码随想录 视频：B站讲解 状态：❌ 第一想法 在小于low的节点，节点和左树全部抛掉，返回右树（如果右树不存在一样返回）； 大于high的节点，节点和右树全部抛掉，返回左树（如果左树不存在一样返回）； 看完题解后的想法 要学会运用返回节点简化操作，这题和LC450类似，都是用返回节点简化了左右判断，因为BST自带左右； 实现中遇到的困难 – 代码 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); } if (root->val > high) { return trimBST(root->left, low, high); } root->left = trimBST(root->left, low, high); root->right = trimBST(root->right, low, high); return root; } }; 108. 将有序数组转换为二叉搜索树 链接：108. 将有序数组转换为二叉搜索树 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 不断取中点构造二叉树; ...