1合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 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] 可被视为重叠区间。
提示：
1 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 104
思路:本题是判断重叠区间问题 先排序，让所有的相邻区间尽可能的重叠在一起，按左边界，或者右边界排序都可以.
-
排序： 首先，根据每个区间的左边界，对给定的区间集合
intervals进行升序排序。这是为了确保处理区间时，可以按顺序考虑它们的位置关系。 -
合并过程： 排序完成后，使用一个结果集合
result来存储最终合并后的区间。开始时，将排序后的第一个区间直接放入result中。 -
遍历区间： 从第二个区间开始遍历，与
result中的最后一个区间比较：- 如果当前区间与
result中的最后一个区间有重叠（即当前区间的左边界小于等于result中最后一个区间的右边界），则更新result中最后一个区间的右边界为两者的最大值，以实现合并。 - 如果当前区间与
result中的最后一个区间没有重叠，则直接将当前区间加入result。
- 如果当前区间与
代码
class Solution {
public:
// 定义一个静态函数作为比较函数，用于排序
static bool cmp(const vector<int>& a, const vector<int>& b) {
return a[0] < b[0]; // 按照区间的左边界进行升序排序
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> result;
if (intervals.empty()) return result; // 如果区间集合为空直接返回空结果
// 使用cmp函数对区间进行排序
sort(intervals.begin(), intervals.end(), cmp);
// 第一个区间直接放入结果集合中
result.push_back(intervals[0]);
for (int i = 1; i < intervals.size(); i++) {
if (result.back()[1] >= intervals[i][0]) { // 发现重叠区间
// 合并区间，只需要更新结果集合中最后一个区间的右边界
result.back()[1] = max(result.back()[1], intervals[i][1]);
} else {
result.push_back(intervals[i]); // 区间不重叠，将当前区间加入结果集合
}
}
return result;
}
};
2 单调递增的数字
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
示例 1:
输入: n = 10 输出: 9
示例 2:
输入: n = 1234 输出: 1234
示例 3:
输入: n = 332 输出: 299
提示:
0 <= n <= 109
思路:
举个例子，数字：332，从前向后遍历的话，那么就把变成了329，此时2又小于了第一位的3了，真正的结果应该是299。
那么从后向前遍历，就可以重复利用上次比较得出的结果了，从后向前遍历332的数值变化为：332 -> 329 -> 299
- 将整数
N转换为字符串strNum，便于按位处理。 - 从右向左遍历字符串
strNum，找到第一个出现递减的位置i，即满足strNum[i-1] > strNum[i]。 - 将第
i-1位减一，并标记flag为i，表示从这里开始需要调整。 - 将从
flag开始的所有位置的字符设为 ‘9’，以确保得到最大的单调递增数。 - 将处理后的字符串转换为整数并返回作为结果。
代码:
class Solution {
public:
int monotoneIncreasingDigits(int N) {
string strNum = to_string(N);
// flag用来标记需要修改的位置，初始化为字符串长度，防止第二个循环在未赋值的情况下执行
int flag = strNum.size();
// 从倒数第二位开始向前遍历
for (int i = strNum.size() - 1; i > 0; i--) {
// 如果当前位大于前一位，则前一位需要减一，并更新flag
if (strNum[i - 1] > strNum[i]) {
flag = i; // 记录需要减一的位置
strNum[i - 1]--; // 前一位减一
}
}
// 将flag位置及之后的所有位数变为9，以获得最大的单调递增数
for (int i = flag; i < strNum.size(); i++) {
strNum[i] = '9';
}
return stoi(strNum); // 转换为整数并返回
}
};3监控二叉树
给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
示例 1：
输入：[0,0,null,0,0] 输出：1 解释：如图所示，一台摄像头足以监控所有节点。
示例 2：
输入：[0,0,null,0,null,0,null,null,0] 输出：2 解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。
提示：
- 给定树的节点数的范围是
[1, 1000]。 - 每个节点的值都是 0。
思路:我们要从下往上看，局部最优：让叶子节点的父节点安摄像头，所用摄像头最少，整体最优：全部摄像头数量所用最少！可以使用后序遍历也就是左右中的顺序，这样就可以在回溯的过程中从下到上进行推导了.
给定一个二叉树，节点状态有三种：未被覆盖、已被覆盖（无需额外摄像头）、已安装摄像头。目标是找出最少需要安装的摄像头数量，覆盖整棵树的所有节点。
定义递归函数 traversal，对当前节点进行处理：
- 如果左右子树有任意一个是未被覆盖的状态（返回2），则当前节点需要安装摄像头，返回1表示当前节点已安装摄像头。
- 如果左右子树都已被覆盖（返回0），则当前节点不需要额外的摄像头覆盖。
- 如果左右子树有一个已安装摄像头（返回1），则当前节点被覆盖，返回0。
-
根节点处理： 调用
traversal函数处理根节点。如果根节点未被覆盖（返回2），则需要额外安装一个摄像头。 -
终返回
result，即安装摄像头的总数量。
代码:
class Solution {
private:
int result; // 记录需要安装摄像头的数量
// 递归函数，返回当前节点的状态：
// 0 - 节点已被覆盖
// 1 - 节点安装了摄像头
// 2 - 节点未被覆盖
int traversal(TreeNode* cur) {
if (cur == NULL) return 2; // 空节点默认已覆盖
int left = traversal(cur->left); // 处理左子树
int right = traversal(cur->right); // 处理右子树
// 如果左右子树有任意一个未被覆盖，当前节点需要安装摄像头
if (left == 2 || right == 2) {
result++; // 安装摄像头
return 1; // 当前节点已安装摄像头
}
// 如果左右子树的状态都是已覆盖，当前节点不需要额外摄像头覆盖
else if (left == 0 && right == 0) {
return 2; // 当前节点未被覆盖
} else {
return 0; // 当前节点已被覆盖
}
}
public:
int minCameraCover(TreeNode* root) {
result = 0; // 初始化摄像头数量为0
if (traversal(root) == 2) { // 如果根节点未被覆盖，则需额外安装摄像头
result++;
}
return result; // 返回最终需要安装的摄像头数量
}
};
