代码随想录 | 刷题-贪心算法5
56. 合并区间
错误分析
- 合并逻辑错误（关键问题）：
1
intervals[i] = (intervals[i-1][0], intervals[i][1]); // 错误写法
- 语法错误：使用逗号运算符
(a, b)实际返回b，导致区间被错误赋值为[0, intervals[i][1]]（起始点丢失）。 - 逻辑错误：合并时结束点未取两者最大值。正确做法：结束点应为
max(intervals[i-1][1], intervals[i][1])，否则可能丢失覆盖范围（如合并[1,5]和[2,3]会得到[1,3]而非[1,5]）。
- 语法错误：使用逗号运算符
- 重叠条件不精确：
1
if(intervals[i-1][1] >= intervals[i][0]) // 边界情况处理不当
- 题目要求：若前区间结束点 等于 后区间起始点（如
[1,2]和[2,3]），应合并为[1,3]。当前条件>=正确，但合并操作错误导致结果异常。
- 题目要求：若前区间结束点 等于 后区间起始点（如
- 性能问题：
- 拷贝开销：
cmp函数参数为传值（vector<int> a, b），应改为 传引用（const vector<int>& a, b）避免不必要的拷贝。 - 额外空间：使用
incl标记数组非必需，经典解法可优化空间复杂度。
- 拷贝开销：
- 边界处理缺失：
- 当输入为空时，应直接返回空数组，但代码未显式处理
intervals.size() == 0的情况（依赖size <= 1返回，逻辑正确但不够清晰）。
- 当输入为空时，应直接返回空数组，但代码未显式处理
比较合并贪心解法（可以ac）
1 | class Solution { |
经典贪心解法思路
- 按起始点排序区间。
- 动态合并：
- 初始化结果数组
merged。 - 遍历每个区间：
- 若
merged为空 或 当前区间与merged最后一个区间不重叠（current[0] > merged.back()[1]），直接加入。 - 否则，更新
merged最后一个区间的结束点：max(merged.back()[1], current[1])。
- 若
- 初始化结果数组
经典贪心解法
1 | class Solution { |
738.单调递增的数字
题目要求小于等于N的最大单调递增的整数，那么拿一个两位的数字来举例。
例如：98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]--，然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数。
> 这一点如果想清楚了，这道题就好办了。
此时是从前向后遍历还是从后向前遍历呢？
从前向后遍历的话，遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]减一，但此时如果strNum[i - 1]减一了，可能又小于strNum[i - 2]。
这么说有点抽象，举个例子，数字：332，从前向后遍历的话，那么就把变成了329，此时2又小于了第一位的3了，真正的结果应该是299。
那么从后向前遍历，就可以重复利用上次比较得出的结果了，从后向前遍历332的数值变化为：332
-> 329 -> 299
处理逻辑易错
- 当发现
digits[i-1] < digits[i]时，代码只修改了当前低位（设为9）和当前高位（减1），但没有处理更高位的影响- 高位减1后可能破坏与更前高位的单调性（例：
100的处理） - 未将所有受影响低位置为
9（例：100的个位未置9）
- 高位减1后可能破坏与更前高位的单调性（例：
- 示例验证（输入
n=100）： 分解 digits = [0, 0, 1] # 个位=0, 十位=0, 百位=1 遍历 i=1：0==0 → 跳过 遍历 i=2：0<1 → 十位置9, 百位减1 → digits=[0,9,0] 结果 = 010⁰ + 910¹ + 0*10² = 90 # 预期应为99
数字组合计算易错
- 错误代码：
res += 10 * (i-1) * digits[i-1] - 问题：
- 错误使用乘法
10*(i-1)而非指数10^(i-1) - 导致计算结果完全错误（如个位贡献
10*0*digits[0]=0）
- 错误使用乘法
- 正确计算：应使用
pow(10, i-1) * digits[i-1]
💡 黄金法则：需要修改数字的每一位时，优先考虑
to_string→ 字符串处理 →stoi流程，比数学运算更直观可靠！
1 | class Solution { |
968.监控二叉树
其实我的思路和题解的想法已经很接近了，但是总结地没有那么到位，导致缺漏数量的情况
确定遍历顺序
在二叉树中可以使用后序遍历也就是左右中的顺序，这样就可以在回溯的过程中从下到上进行推导了。
1
2
3
4
5
6
7
8int traversal(TreeNode* cur) {
// 空节点，该节点有覆盖
if (终止条件) return ;
int left = traversal(cur->left); // 左
int right = traversal(cur->right); // 右
逻辑处理 // 中
return ;
}
返回状态类型
- 0：该节点不在摄像头覆盖范围
- 1：本节点有摄像头
- 2：本节点在摄像头覆盖范围
递归的终止条件应该是遇到了空节点，此时应该返回2（有覆盖），这样就可以在叶子节点的父节点放摄像头了。
1
2// 空节点，该节点有覆盖
if (cur == NULL) return 2;1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class Solution {
public:
int cmr = 0;
int coverStat(TreeNode* root){
if(!root)return 2;
int left = coverStat(root->left);
int right = coverStat(root->right);
if(left == 2 && right == 2){
return 0;
}
if(left == 0 || right == 0){
cmr++;
return 1;
}
if(left == 1 || right == 1){
return 2;
}
return -1;
}
int minCameraCover(TreeNode* root) {
int rcv = coverStat(root);
if(rcv == 0)cmr++;
return cmr;
}
};