56. 合并区间

56. 合并区间

class Solution {
public:static bool cmp(vector<int>& a, vector<int>& b) {if(a[0] == b[0]) {return a[1] < b[1];}return a[0] < b[0];}vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end(), cmp);vector<vector<int>> res;int start = intervals[0][0];int end = intervals[0][1];for (int i = 1; i < intervals.size(); i++) {if (intervals[i][0] >= start && intervals[i][0] <= end) { // 与前面的区间有重叠if(intervals[i][1] >= end) { // 更新重叠区间的右端点end = intervals[i][1];}} else if (intervals[i][0] > end) { // 与前面的区间无重叠res.push_back({start, end});start = intervals[i][0];end = intervals[i][1];}}res.push_back({start, end});return res;}
};

738. 单调递增的数字

738. 单调递增的数字
当发现当前数字大于下一个数字时，就把当前数字减1，后面的所有数字都设置成 9

class Solution {
public:int monotoneIncreasingDigits(int n) {if (n >= 0 && n <= 9) {return n;}string s = to_string(n);for (int i = s.size() - 2; i >=  0; i--) {if(s[i] > s[i + 1]) {s[i]--;for (int j = i + 1; j < s.size(); ++j){s[j] = '9';}}}return stoi(s);}
};

第二个for循环存在重复赋值；如：304537，在检测到5<4时，数字改为303999；在遇到0<3时，数字改为299999，最后两位数同样被再次赋值；
设置flag来标记赋值9从哪里开始，同时将赋值循环分离出来；

class Solution {
public:int monotoneIncreasingDigits(int n) {string s = to_string(n);int flag = s.size();for (int i = s.size() - 2; i >=  0; i--) {if(s[i] > s[i + 1]) {s[i]--;flag = i + 1;}}for (int j = flag; j < s.size(); ++j){s[j] = '9';}return stoi(s);}
};

968. 监控二叉树

968. 监控二叉树

给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。

局部最优：让叶子节点的父节点安摄像头，所用摄像头最少
全局最优：全部摄像头数量所用最少

class Solution {
private:int res;int traversal(TreeNode* cur) {if (cur == NULL) return 2;int left = traversal(cur->left);    // 左int right = traversal(cur->right);  // 右if (left == 2 && right == 2) return 0;else if (left == 0 || right == 0) {res++;return 1;} else return 2;}
public:int minCameraCover(TreeNode* root) {res= 0;if (traversal(root) == 0) { // root 无覆盖res++;}return res;}
};