27.贪心算法5

合并区间

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) {
        sort(intervals.begin(),intervals.end(),cmp);
        vector<int> tmp=intervals[0];
        vector<vector<int>> res;
        int n=intervals.size();
        for(int i=1;i<n;i++){
            if(tmp[1]>=intervals[i][0]){
                tmp[1]=tmp[1]>intervals[i][1]?tmp[1]:intervals[i][1];
            }else{
                res.push_back(tmp);
                tmp=intervals[i];
            }
        }
        res.push_back(tmp);
        return res;
    }
};

和分割字符串那个一样

单调递增的数字

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

监控二叉树

class Solution {
public:
    
    int minCameraCover(TreeNode* root) {
    unordered_map<TreeNode* ,int> mymap;
    stack<TreeNode*> sta;
    sta.push(root);
    TreeNode* cur=root;
    int count=0;
    while(!sta.empty()){
        cur=sta.top();
        sta.pop();
        if(cur){
            sta.push(cur);
            sta.push(nullptr);
            if(cur->left){
                sta.push(cur->left);
            }
            if(cur->right){
                sta.push(cur->right);
            }
        }else{
            cur=sta.top();
            sta.pop();
            bool put=0;
            if(cur->right){
                if(mymap[cur->right]==0){
                    put=1;
                }else if(mymap[cur->right]==2){
                    mymap[cur]=1;
                }
            }
            if(cur->left){
                if(mymap[cur->left]==0){
                    put=1;
                }else if(mymap[cur->left]==2){
                    mymap[cur]=1;
                }
            }
            if(put){
                mymap[cur]=2;
                count++;
                mymap[cur->left]=mymap[cur->right]=1;
            }else if(cur==root&&!mymap[cur]){
                mymap[cur]=2;
                count++;
            }
        }
    }    
        return count;
    }
};