做网站需要用什麼服务器,爱站网挖掘关键词,长沙网页制作模板,wordpress自带主题下载刷题记录 56. 合并区间*738. 单调递增的数字*968. 监控二叉树 56. 合并区间
leetcode题目地址
排序后遇到有重合的区间选择最大的区间保存即可#xff0c;结果集中保存的是离当前区间最近的区间#xff0c;因此使用当前区间与结果集中的最后一个集合比较查看是否有重合结果集中保存的是离当前区间最近的区间因此使用当前区间与结果集中的最后一个集合比较查看是否有重合若有重合则将右区间扩大为两个区间中最大的右区间若没有重合则将当前集合放入结果集中。
时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( 1 ) O(1) O(1)
// c
class Solution {
public:static bool cmp(const vectorint a, const vectorint b){if(a[0]b[0]) return a[1] b[1];return a[0] b[0];}vectorvectorint merge(vectorvectorint intervals) {vectorvectorint result;sort(intervals.begin(), intervals.end(), cmp);for(int i0; iintervals.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(n) O(n) 空间复杂度 O ( 1 ) O(1) O(1)
// c
class Solution {
public:int monotoneIncreasingDigits(int n) {string s to_string(n);int flag s.size();for(int is.size()-1; i0; i--){if(s[i-1] s[i]) {flag i;s[i-1]--;}}for(int iflag; is.size(); i)s[i] 9;return stoi(s);}
};*968. 监控二叉树
leetcode题目地址
借助后序遍历每个结点三种状态无覆盖、有监控、被覆盖分别用0、1、2标识。
若孩子节点都是被覆盖则当前节点没有被覆盖返回0若孩子节点有一个未被覆盖则当前节点需要加装监控计数器1返回1若孩子节点有一个装了监控则当前节点是被覆盖的状态返回2
空节点需要返回被覆盖状态即2。 因为空节点的父结点可能是叶结点若返回无覆盖状态则会把监控装在叶结点而正确的位置应该装在叶结点的父节点若返回有监控则会导致单分支节点未被覆盖。因此只能返回2.
时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( n ) 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(left2 right2) {return 0;}return -1;}int minCameraCover(TreeNode* root) {int result 0;int res Traverse(root, result);// 根节点未被覆盖if(!res) result;return result;}
};
