27.贪默算法5

归并区间

1. class Solution {
2. public:
3.     static bool cmp(const vector<int> & a,const vector<int> & b){
4.         return a[0]<b[0];
5.     }
6.     vector<vector<int>> merge(vector<vector<int>>& intervals) {
7.         sort(intervals.begin(),intervals.end(),cmp);
8.         vector<int> tmp=intervals[0];
9.         vector<vector<int>> res;
10.         int n=intervals.size();
11.         for(int i=1;i<n;i++){
12.             if(tmp[1]>=intervals[i][0]){
13.                 tmp[1]=tmp[1]>intervals[i][1]?tmp[1]:intervals[i][1];
14.             }else{
15.                 res.push_back(tmp);
16.                 tmp=intervals[i];
17.             }
18.         }
19.         res.push_back(tmp);
20.         return res;
21.     }
22. };

复制代码

  和分割字符串那个一样
  单调递增的数字

1. class Solution {
2. public:
3.     int monotoneIncreasingDigits(int k) {
4.         string s=to_string(k);
5.         int index=-1;
6.         int n=s.size();
7.         for(int i=0;i<n-1;i++){
8.             if(s[i]>s[i+1]){
9.                 s[i]--;
10.                 index=i+1;
11.                 while(index>1&&s[index-1]<s[index-2]){
12.                     index--;
13.                     s[index-1]--;
14.                 }
15.                 break;
16.             }
17.         }
18.         for(int i=index;i>=0&&i<n;i++){
19.             s[i]='9';
20.         }
21.         int res=stoi(s);
22.         return res;
23.     }
24. };

复制代码

监控二叉树

1. class Solution {
2. public:
3.    
4.     int minCameraCover(TreeNode* root) {
5.     unordered_map<TreeNode* ,int> mymap;
6.     stack<TreeNode*> sta;
7.     sta.push(root);
8.     TreeNode* cur=root;
9.     int count=0;
10.     while(!sta.empty()){
11.         cur=sta.top();
12.         sta.pop();
13.         if(cur){
14.             sta.push(cur);
15.             sta.push(nullptr);
16.             if(cur->left){
17.                 sta.push(cur->left);
18.             }
19.             if(cur->right){
20.                 sta.push(cur->right);
21.             }
22.         }else{
23.             cur=sta.top();
24.             sta.pop();
25.             bool put=0;
26.             if(cur->right){
27.                 if(mymap[cur->right]==0){
28.                     put=1;
29.                 }else if(mymap[cur->right]==2){
30.                     mymap[cur]=1;
31.                 }
32.             }
33.             if(cur->left){
34.                 if(mymap[cur->left]==0){
35.                     put=1;
36.                 }else if(mymap[cur->left]==2){
37.                     mymap[cur]=1;
38.                 }
39.             }
40.             if(put){
41.                 mymap[cur]=2;
42.                 count++;
43.                 mymap[cur->left]=mymap[cur->right]=1;
44.             }else if(cur==root&&!mymap[cur]){
45.                 mymap[cur]=2;
46.                 count++;
47.             }
48.         }
49.     }   
50.         return count;
51.     }
52. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。