56. 合并区间
给出一个区间的集合，请合并所有重叠的区间。
示例 1:
- 输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
- 输出: [[1,6],[8,10],[15,18]]
- 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
- 输入: intervals = [[1,4],[4,5]]
- 输出: [[1,5]]
- 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
- 注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。
解题思路
先排序，然后直接把第一个区间用left，right表示；然后开始循环，每次比较下一个区间与用left与right表示。
1、如果right小于下一个区间的左边界，把当前left，right放入res；更新left right到下一个区间；
2、如果right大于下一个区间的左边界，把right更新为下一个区间的右边界；
循环结束后记得保存最后一组left，right；最后输出res
class Solution {
public:
static bool cmp(vector<int>& a, vector<int>& b) {
return a[0] < b[0];
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.empty()) return {};
sort(intervals.begin(), intervals.end(), cmp);
vector<vector<int>> res;
int left = intervals[0][0];
int right = intervals[0][1];
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i][0] > right) {
res.push_back({left, right});
left = intervals[i][0];
right = intervals[i][1];
} else {
right = max(right, intervals[i][1]);
}
}
// Add the last interval
res.push_back({left, right});
return res;
}
};738.单调递增的数字
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
示例 1:
输入: n = 10 输出: 9
示例 2:
输入: n = 1234 输出: 1234
示例 3:
输入: n = 332 输出: 29
解题思路：
从后往前遍历，下一个数字比当前数字大（不满足单调递增的条件），就让下一个数字减一，当前数字的位数记录到flag；遍历结束后；最后将flag位之后的所有数字都写成‘9’。最后进行string向int的强制转换，输出。
小技巧：改写flag的操作因为flag的初值=strNum.size()；如果遍历过程中都满足单调递增条件，就不会激活改写'9'的语句。
class Solution {
public:
int monotoneIncreasingDigits(int n) {
string strNum=to_string(n);
int flag=strNum.size();
for(int i=strNum.size()-1;i>0;i--){
if(strNum[i-1]>strNum[i]){
strNum[i-1]--;
flag=i;
}
}
for(int j=flag;j<strNum.size();j++){
strNum[j]='9';
}
return stoi(strNum);
}
};968.监控二叉树
给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
示例 1：
- 输入：[0,0,null,0,0]
- 输出：1
- 解释：如图所示，一台摄像头足以监控所有节点。
解题思路
每个节点有三种状态0、无覆盖1、有摄像头2、有覆盖。
遍历方向需要从底部往上，所以采用后序遍历（左右中）
递归三部曲
1、确定参数返回值
参数是根节点 返回该节点的三种状态之一int
2、确定终止条件
叶子节点的子节点为NULL，这个节点需要视为已覆盖。
3、单层递归逻辑
左 用left接收左儿子的状态
右 用right接收右儿子的状态
中 有三种情况
1）两个儿子都是2有覆盖，那么返回0无覆盖
2）有一个儿子有摄像头，返回2有覆盖
3）有一个儿子无覆盖0，返回1有摄像头。
最后在主函数中需要判断根节点是否为无覆盖0，如果无覆盖还需要额外加一个摄像头；其他的情况就可以直接输出res。
class Solution {
public:
int res=0;
int traversal(TreeNode* cur){
if(cur==NULL)return 2;//2表示有覆盖
int left=traversal(cur->left);
int right=traversal(cur->right);
if(left==2&&right==2)return 0;//0表示无覆盖
if(left==0||right==0){
res++;
return 1;//1表示有摄像头
}
if(left==1||right==1)return 2;//2表示有覆盖
return -1;
}
int minCameraCover(TreeNode* root) {
if(traversal(root)==0)res++;
return res;
}
};