題目考點: 貪心 區間

解題思路

排序,找重疊區間,然后標記排除

我來按照右邊界排序，從左向右記錄非交叉區間的個數。最后用區間總數減去非交叉區間的個數就是需要移除的區間個數了。

此時問題就是要求非交叉區間的最大個數。

這里記錄非交叉區間的個數還是有技巧的，如圖：

class Solution {
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(),intervals.end(),[](const vector<int>&a,const vector<int>&b) {return a[0] < b[0];});if (intervals.size() == 0) return 0;int cnt = 0;int end = intervals[0][1];for(int i = 1; i < intervals.size(); i++) {if (intervals[i][0] >= end) end = intervals[i][1]; //無重疊情況else {end = min(end,intervals[i][1]);cnt++; //記錄重疊情況}}return cnt;}
};

題目考點: 貪心

在遍歷的過程中相當于是要找每一個字母的邊界，如果找到之前遍歷過的所有字母的最遠邊界，說明這個邊界就是分割點了。此時前面出現過所有字母，最遠也就到這個邊界了。

可以分為如下兩步：

• 統計每一個字符最后出現的位置
• 從頭遍歷字符，并更新字符的最遠出現下標，如果找到字符最遠出現位置下標和當前下標相等了，則找到了分割點

代碼

class Solution {
public:vector<int> partitionLabels(string S) {int hash[27] = {0}; // i為字符，hash[i]為字符出現的最后位置for (int i = 0; i < S.size(); i++) { // 統計每一個字符最后出現的位置hash[S[i] - 'a'] = i;}vector<int> ans;int left = 0;int right = 0;for (int i = 0; i < S.size(); i++) {right = max(right, hash[S[i] - 'a']); // 找到字符出現的最遠邊界if (i == right) {ans.push_back(right - left + 1);left = i + 1;}}return ans;}
};

題目考點: 區間 貪心

題解

對區級左右端點的一個端點進行排序, 然后查找重疊區間

這幾道題都是判斷區間重疊，區別就是判斷區間重疊后的邏輯，本題是判斷區間重貼后要進行區間合并。

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

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

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> ans;sort(intervals.begin(),intervals.end(),[](const vector<int>&a,const vector<int>&b) {return a[0] < b[0];});for (int i = 1; i < intervals.size(); i++) {if (intervals[i][0] <= intervals[i-1][1]) {intervals[i][1] = max(intervals[i][1], intervals[i-1][1]);intervals[i][0] = intervals[i-1][0];} else {ans.push_back({intervals[i-1][0],intervals[i-1][1]});}}ans.push_back({intervals.back()[0], intervals.back()[1]});return ans;}
};

題目考點: 貪心 數據

解題思路
題目要求小于等于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

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

代碼

class Solution {
public:int monotoneIncreasingDigits(int 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] ) {flag = i;strNum[i - 1]--;}}for (int i = flag; i < strNum.size(); i++) {strNum[i] = '9';}return stoi(strNum);}
};