*算法训练（leetcode）第二十七天 | 56. 合并区间、738. 单调递增的数字、968. 监控二叉树

56. 合并区间

leetcode题目地址

排序后遇到有重合的区间选择最大的区间保存即可，结果集中保存的是离当前区间最近的区间，因此使用当前区间与结果集中的最后一个集合比较查看是否有重合，若有重合则将右区间扩大为两个区间中最大的右区间，若没有重合则将当前集合放入结果集中。

时间复杂度： $O(n)$
空间复杂度： $O(1)$

// c++
class Solution {
public:static bool cmp(const vector<int> & a, const 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) {vector<vector<int>> result;sort(intervals.begin(), intervals.end(), cmp);for(int i=0; i<intervals.size(); i++){if(result.size()>0){int last = result.size()-1;if(intervals[i][0]<=result[last][1])result[last][1] = max(result[last][1], intervals[i][1]);else{result.emplace_back(intervals[i]);}}else{result.emplace_back(intervals[i]);}}return result;}
};

*738. 单调递增的数字

leetcode题目地址

一开始想着暴力求解，但超时了，然后就没思路了。

思路来源

时间复杂度： $O(n)$
空间复杂度： $O(1)$

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

*968. 监控二叉树

leetcode题目地址

借助后序遍历，每个结点三种状态：无覆盖、有监控、被覆盖，分别用0、1、2标识。

• 若孩子节点都是被覆盖，则当前节点没有被覆盖，返回0；
• 若孩子节点有一个未被覆盖，则当前节点需要加装监控，计数器+1，返回1；
• 若孩子节点有一个装了监控，则当前节点是被覆盖的状态，返回2；

空节点需要返回被覆盖状态，即2。
因为空节点的父结点可能是叶结点，若返回无覆盖状态，则会把监控装在叶结点，而正确的位置应该装在叶结点的父节点；若返回有监控，则会导致单分支节点未被覆盖。因此只能返回2.

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// c++
/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*//*
三种状态：
无覆盖：0
当前节点有摄像头：1
当前节点有被覆盖：2
*/
class Solution {
public:int Traverse(TreeNode* root, int &result){if(!root) return 2;int left = Traverse(root->left, result);int right = Traverse(root->right, result);// 左右节点有一个未被覆盖 则当前节点需要加摄像头if(!left || !right){result++;return 1;}// 左右节点有监控 则当前节点被覆盖if(left == 1 || right == 1){return 2;}// 子节点都是覆盖 则当前节点未被覆盖if(left==2 && right==2) {return 0;}return -1;}int minCameraCover(TreeNode* root) {int result = 0;int res = Traverse(root, result);// 根节点未被覆盖if(!res) result++;return result;}
};