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;
if (intervals.empty())return res;
res.push_back(intervals[0]);
for (int i=1;i<intervals.size();i++){
if (intervals[i][0]<=res.back()[1]){
res.back()[1]=max(intervals[i][1],res.back()[1]);
}
else{
res.push_back(intervals[i]);
}
}
return res;
}
};
总结
昨天的思路今天就用不了了。
738.单调递增的数字
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]<s[i-1]){
flag=i;
s[i-1]--;
}
}
for (int i=flag;i<s.size();i++){
s[i]='9';
}
return stoi(s);
}
};
总结
整数类型无法修改的时候,应该想到用string。
968.监控二叉树 (可跳过)
本题是贪心和二叉树的一个结合,比较难,一刷大家就跳过吧。
/**
* 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) {}
* };
*/
class Solution {
public:
int res=0;
int traversal(TreeNode* node){
if (!node)return 2;
int left=traversal(node->left);
int right=traversal(node->right);
if (left==2 && right==2)return 0;
if (left==0 || right==0){
res++;
return 1;
}
if (left==1 || right==1)return 2;
return -1;
}
int minCameraCover(TreeNode* root) {
if (traversal(root)==0)res++;
return res;
}
};
总结
自己写思路全无,一看答案就觉得妙极了。看来还要三刷。