1.leetcode 56.合并區間

題目鏈接

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) {vector<vector<int>> result;if(intervals.size()==0) return result;// 區間集合為空直接返回sort(intervals.begin(),intervals.end(),cmp);// 第一個區間就可以放進結果集里，后面如果重疊，在result上直接合并result.push_back(intervals[0]);for(int i=1;i<intervals.size();i++){if(intervals[i][0]<=result.back()[1]){// 發現重疊區間// 合并區間，只更新右邊界就好，因為result.back()的左邊界一定是最小值，因為我們按照左邊界排序的result.back()[1]=max(result.back()[1],intervals[i][1]);}else{result.push_back(intervals[i]);// 區間不重疊,直接放進去就可以了}}return result;}
};

思路總結:本題的本質還是判斷重疊區間的問題

一樣的套路，先排序，讓所有的相鄰區間盡可能的重疊在一起，按左邊界，或者右邊界排序都可以，處理邏輯稍有不同。

按照左邊界從小到大排序之后，如果?intervals[i][0] <= intervals[i - 1][1]?即intervals[i]的左邊界 <= intervals[i - 1]的右邊界，則一定有重疊。（本題相鄰區間也算重貼，所以是<=）

其實就是用合并區間后左邊界和右邊界，作為一個新的區間，加入到result數組里就可以了。如果沒有合并就把原區間加入到result數組。

2.leetcode 738.單調遞增的數字

題目鏈接

class Solution {
public:int monotoneIncreasingDigits(int n) {//把數字n轉化成字符串類型string strNum=to_string(n);// flag用來標記賦值9從哪里開始// 設置為這個默認值，為了防止第二個for循環在flag沒有被賦值的情況下執行int flag=strNum.size();//從后往前開始遍歷for(int i=strNum.size()-1;i>0;i--){if(strNum[i-1]>strNum[i]){strNum[i-1]--;flag=i;}}for(int i=flag;i<strNum.size();i++){strNum[i]='9';}//把字符串類型轉化成整型int result=stoi(strNum);return result;}
};

思路總結:

題目要求小于等于N的最大單調遞增的整數，那么拿一個兩位的數字來舉例。

例如：98，一旦出現strNum[i - 1] > strNum[i]的情況（非單調遞增），首先想讓strNum[i - 1]--，然后strNum[i]給為9，這樣這個整數就是89，即小于98的最大的單調遞增整數。

這一點如果想清楚了，這道題就好辦了。

此時是從前向后遍歷還是從后向前遍歷呢？

從前向后遍歷的話，遇到strNum[i - 1] > strNum[i]的情況，讓strNum[i - 1]減一，但此時如果strNum[i - 1]減一了，可能又小于strNum[i - 2]。

這么說有點抽象，舉個例子，數字：332，從前向后遍歷的話，那么就把變成了329，此時2又小于了第一位的3了，真正的結果應該是299。

那么從后向前遍歷，就可以重復利用上次比較得出的結果了，從后向前遍歷332的數值變化為：332 -> 329 -> 299

確定了遍歷順序之后，那么此時局部最優就可以推出全局，找不出反例，試試貪心。

本題只要想清楚個例，例如98，一旦出現strNum[i - 1] > strNum[i]的情況（非單調遞增），首先想讓strNum[i - 1]減一，strNum[i]賦值9，這樣這個整數就是89。就可以很自然想到對應的貪心解法了。

想到了貪心，還要考慮遍歷順序，只有從后向前遍歷才能重復利用上次比較的結果。

最后代碼實現的時候，也需要一些技巧，例如用一個flag來標記從哪里開始賦值9。

這里解釋一下兩個特殊的函數,分別是to_string和stoi函數

to_string函數就是將一個整型變量轉化為一個字符串變量,這樣方便我們進行計算統計處理

stoi函數就是to_string函數的反向操作,將一個字符串變量轉化為一個整型變量

一般都是這兩個函數相互使用,這樣容易我們寫出一些題目

3.leetcode 968.監控二叉樹

題目鏈接

這道題是力扣里面名副其實的hard題目,大家可以感受感受,這里就直接給出題解了,就不總結了

/*** 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 result;int traversal(TreeNode* current){// 空節點，該節點有覆蓋if(current==NULL) return 2;int left=traversal(current->left);//左int right=traversal(current->right);//右// 情況1// 左右節點都有覆蓋if(left==2&&right==2) return 0;// 情況2// left == 0 && right == 0 左右節點無覆蓋// left == 1 && right == 0 左節點有攝像頭，右節點無覆蓋// left == 0 && right == 1 左節點有無覆蓋，右節點攝像頭// left == 0 && right == 2 左節點無覆蓋，右節點覆蓋// left == 2 && right == 0 左節點覆蓋，右節點無覆蓋if(left==0||right==0){result++;return 1;}// 情況3// left == 1 && right == 2 左節點有攝像頭，右節點有覆蓋// left == 2 && right == 1 左節點有覆蓋，右節點有攝像頭// left == 1 && right == 1 左右節點都有攝像頭// 其他情況前段代碼均已覆蓋if(left==1||right==1) return 2;// 以上代碼我沒有使用else，主要是為了把各個分支條件展現出來，這樣代碼有助于讀者理解// 這個 return -1 邏輯不會走到這里。return -1;}int minCameraCover(TreeNode* root) {result=0;//情況4if(traversal(root)==0){//root無覆蓋result++;}return result;}
};

4.貪心算法總結

貪心算法本身沒有什么規律,能寫的出來真的很不容易

貪心算法的簡單題可能往往過于簡單甚至感覺不到貪心,但是貪心的難題又真的有點難,而且貪心也沒有什么框架和套路,所以對刷題的順序沒有什么要求

1.貪心很簡單,就是常識?

跟著刷題的同學們就會發現,貪心思路往往很巧妙,并不簡單

2.貪心有沒有固定的套路?

貪心無套路，也沒有框架之類的，需要多看多練培養感覺才能想到貪心的思路。

3.究竟什么題目是貪心呢？

個人認為：如果找出局部最優并可以推出全局最優，就是貪心，如果局部最優都沒找出來，就不是貪心，可能是單純的模擬。（并不是權威解讀，一家之辭哈）

但我們也不用過于強調什么題目是貪心，什么不是貪心，那就太學術了，畢竟學會解題就行了。

4.如何知道局部最優推出全局最優,有數學證明嗎?

在做貪心題的過程中，如果再來一個數據證明，其實沒有必要，手動模擬一下，如果找不出反例，就試試貪心。面試中，代碼寫出來跑過測試用例即可，或者自己能自圓其說理由就行了

就像是 要用一下 1 + 1 = 2，沒有必要再證明一下 1 + 1 究竟為什么等于 2。（例子極端了點，但是這個道理）

很多沒有接觸過貪心的同學都會感覺貪心有啥可學的,但只要跟著這個博客堅持下來可以發現,貪心是一種很重要的算法思維而且并不簡單,貪心往往妙的出其不意,猝不及防

這也是我認為判斷這是一道貪心題目的依據，如果找不出局部最優，那可能就是一道模擬題。