基礎貪心算法集合2（10題）

1.單調遞增的數字

2.壞了的計算器

?3.合并區間

4.無重疊區間

5. 用最少數量的箭引爆氣球

?6.整數替換

解法1：模擬+記憶化搜索

解法2位運算+貪心

7.俄羅斯套娃信封問題

補充.堆箱子

8.可被3整除的最大和

?9.距離相等的條形碼

?10.重構字符串

1.單調遞增的數字

?738. 單調遞增的數字 - 力扣（LeetCode）

但是如果只這么處理會出現bug?

例如如下這種情況，我們需要找到最前面的5.

因此

class Solution {
public:int monotoneIncreasingDigits(int n) {string num = to_string(n);int sz = num.size();int i = 0;while(i+1 < sz && num[i] <= num[i+1])i++;if(i+1 == sz)return n;//如果全遞增直接返回，或者處理nums[i]的時候判斷一下while(i - 1 >= 0 && num[i-1] == num[i])i--;num[i]--;for(int k = i + 1; k < sz; k++){num[k] = '9';}return stoi(num);//std::stoi 會忽略前導零，只返回字符串表示的整數值}
};

2.壞了的計算器

?991. 壞了的計算器 - 力扣（LeetCode）

看到這題我們首先就想到正向推導。

我們貪心地想到，如果想讓初始數字以盡可能少的次數變成目標數字，可以多用*2操作。

但是我們發現這種貪心是不對的，對于*2和-1的操作，判斷標準不是很明確。?用正向的方法比較難解決這個問題

????????于是我們想到正難則反，而*2 和-1的操作正好有相反的/2和+1操作。?

????????這一題有個非常重要的點就是它里面的數據是沒有小數的，從起始數據到目標數據，不斷*2，-1操作下是不能產生小數的。

? ? ? ? ? 所以我們在面對奇數的時候，就不能進行/2操作了，只能進行+1操作。

整理思路，我們得出以下結論：

1.當end <= begin

當?end <= begin時，end要想達到begin，肯定不可能進行/2操作，只能進行+1操作，這時候無論奇數偶數，都只有+1的選擇。我們需要進行begin-end次操作

?2.當end > begin 的時

當end > begin 的時候

?我們如果想要先+1再/2，那么我們必須要加偶數個1，我們才能/2.最后，我們通過k+1次操作得到了（x+k）/2.

而如果我們先/2，那么我們只需要1+k/2 次就能得到（x+k）/2。

我們很容易得到先進行除法是更優的。

因此在end > begin的時候，我們奇數仍然是只能+1，偶數則是只進行/2操作

class Solution {
public:int brokenCalc(int startValue, int target) {int ret = 0;while(target > startValue){if(target % 2 == 0){target /= 2;ret++;}else{target++;ret++;}}ret += startValue - target;return ret;}
};

?3.合并區間

56. 合并區間 - 力扣（LeetCode）

區間問題解法

我們為了思路統一，統一采用左端點排序

?假設我們有一個區間，從left 到right

那么我們下一個區間有以下這些情況。

整體分為有重疊部分和沒有重疊部分。

當有重疊部分時，我們保存左端點，取較大的右端點。(因為進行排序后，左端點是升序排序的)

當沒有重疊部分時，我們把{left，right}加入ret數組，然后更新left和right。

class Solution {
public:static bool cmp(vector<int> a, vector<int> b){return a[0] < b[0];}vector<vector<int>> merge(vector<vector<int>>& intervals) {//排序sort(intervals.begin(), intervals.end(), cmp);//合并區間vector<vector<int>> ret;int left = intervals[0][0];int right = intervals[0][1];for(int i = 1; i < intervals.size(); i++){if(intervals[i][0] <= right)//有重疊部分{right = max(right,intervals[i][1]);//合并}else//無重疊{ret.push_back({left, right});//加入到結果中left = intervals[i][0];right = intervals[i][1];}}ret.push_back({left, right});return ret;}
};

4.無重疊區間

?435. 無重疊區間 - 力扣（LeetCode）

仍然是先按照左端點排序。

我們要移除最少的區間，那也就是說要保留更多的區間。

因此我們可以采用以下策略來保留更多區間。

當存在區間重疊時，我們保留較小的右端點，這樣它和后面的?區間有重疊的可能性就會變小。

當區間無重疊，我們更新left right并把count++即可。

遍歷數組結束后要記得加上最后存在left right里面的那段區間。

最后，因為我們求的是移除的區間，因此把數組的長度減去count就是我們的返回值

class Solution {
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {int count = 0;sort(intervals.begin(), intervals.end());int left = intervals[0][0];int right = intervals[0][1];for(int i = 1; i < intervals.size(); i++){if(intervals[i][0] < right){right = min(right,intervals[i][1]);}else{count++;left = intervals[i][0];right = intervals[i][1];}}count ++;return intervals.size() - count;}
};

5. 用最少數量的箭引爆氣球

452. 用最少數量的箭引爆氣球 - 力扣（LeetCode）

理解題意，我們發現這也是一個區間問題。

我們發現這題找的實際上是交集。

class Solution {
public:int findMinArrowShots(vector<vector<int>>& points) {sort(points.begin(), points.end());int cover = 0;int right = points[0][1];for(int i = 1; i < points.size(); i++){if(points[i][0] <= right)//和上一個區間有交集{cover++;//重疊部分++right = min(right, points[i][1]);//右端點較小的同時也是是重疊區間的右端點}else{right = points[i][1];//無交集，以新的區間為基準再求重疊部分}}return points.size() - cover;}
};

?6.整數替換

解法1：模擬+記憶化搜索

就是暴力枚舉每種情況，對于偶數直接除以2，對于奇數則是取?min(hash[n-1], hash[n+1])

需要注意的地方是，為了防止INT_MAX + 1 溢出，我們dfs函數的類型使用long long，哈希表也是一樣。

class Solution {
public:unordered_map<long long, int> hash;int integerReplacement(int n) {return dfs(n);}int dfs(long long n){if(n == 1)return 0;if(n % 2 == 0){if(!hash.count(n/2)){hash[n/2] = dfs(n/2);}return 1 + hash[n/2];}else{if(!hash.count(n+1) ){hash[n+1] = dfs( n+1 );}if(!hash.count( n-1 ) ){hash[ n-1 ] = dfs( n-1 );}return 1  + min(hash[n-1], hash[n+1]);}}
};

解法2位運算+貪心

對于偶數我們進行/2操作即可。

對于奇數操作，當其為01結尾的時候，我們采用-1操作操作數會更少。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 當其為11結尾的時候，-1操作會使得一位1變為0，而+1操作可能會使得多于一位的1變為0，因此采用+1的操作會更快捷地得到最終值。

最后有一個例外，即3，我們應該采用-1操作。

要判斷最后兩位是01還是11，我們只需要把這些數對4取余即可，看余數是1還是3即可判斷。

這道題的貪心就貪在不同的奇數是+1還是-1，已經在過程中證明好了

?同樣需要加一個longlong

class Solution {
public:int integerReplacement(int num) {int ret = 0;long long n = num;while(n > 3){if(n % 2 == 0){ret++;n  = n >> 1;}else{if(n % 4 == 3){n = n + 1;ret++;}else if(n % 4 == 1){n = n - 1;ret++;}}}if(n == 3)return ret + 2;else if(n == 2)return ret + 1;else return ret;}
};

7.俄羅斯套娃信封問題

?解法1：區間排序+動態規劃（超時）

解法2：區間排序 + 貪心 + 二分

我們嚴格按照左端點排序后，實際上已經不用看左端點了，因為總是遞增的。?

那么這道題經過這樣處理，就變成了一個最長遞增子序列問題。

????????但是當左端點有重復的時候需要注意，這時候如果我們的右端點按照升序排，我們就會把一些不該加的元素加入。

?????????這時候就需要我們在左端點相同的時候把右端點降序排序

????????這樣的好處是，我們就不會有可能把這些數字全部接到原數組后面了。因為如果有更小的數，那么我們會將其與原來的數替換。例如上一個數是3，按照升序排序的話，4679都會排到它后面。

????????可是如果我們降序，則我們在將9加入數組后，后面的764都只是更新數組末尾的9而已，讓9不斷被替換為764.

class Solution {
public:static bool cmp(const vector<int> & a, const vector<int> & b){if(a[0] != b[0])return a[0] < b[0];else return a[1] > b[1];}int maxEnvelopes(vector<vector<int>>& env) {sort(env.begin(), env.end(), cmp);vector<int> ret;ret.push_back(env[0][1]);for(int i = 1; i < env.size(); i++){if(env[i][1] > ret.back()){ret.push_back(env[i][1]);}else{int left = 0; int right = ret.size() - 1;while(left < right){int mid = left + (right-left) / 2;if( env[i][1] <= ret[mid]){right = mid;}else{left = mid + 1;}}ret[left] = env[i][1];}}return ret.size();}
};

補充.堆箱子

?雖然俄羅斯套娃信封中的解法1會超時，但是在堆箱子這題中是可以通過的

面試題 08.13. 堆箱子 - 力扣（LeetCode）

?排序后的思路和最長遞增子序列相同

有兩個需要注意的問題

class Solution {
public:static bool cmp(vector<int> a, vector<int> b){return a[0] < b[0];}int pileBox(vector<vector<int>>& box) {sort(box.begin(), box.end(),cmp);//1.需要自己手動寫一個排序函數，按照某一維度來排。 //默認排序會出問題int n = box.size();if(n == 0)return 0;vector<int> dp(n , 0);for(int i = 0; i < n; i++)//2.初始化dp表的時候，每個箱子最小的堆疊高度是自己的高度{dp[i] = box[i][2];}int ret = dp[0];for(int i = 1; i < n; i++){for(int j = i - 1; j >= 0; j--){if(box[j][0] < box[i][0] && box[j][1] < box[i][1] && box[j][2] < box[i][2]){dp[i] = max(dp[i], dp[j] + box[i][2]);}}ret = max(ret, dp[i]);}return ret;}
};

8.可被3整除的最大和

?1262. 可被三整除的最大和 - 力扣（LeetCode）

我們正難則反，根據累加和的不同情況，刪去一些數即可，而我們只需要貪心地刪除最小值即可。 ?

????????分類情況中，?我們把第二種情況拿來舉例子，可能我們有1個或者4個或者7個除以3余1的數，但是我們只需要取出最小的那個。整體來看是把這一組數分成兩塊，一塊是一個除以3余1的數，另一塊是可以被3整除的。

? ? ? ? 下面的另外三種也是一樣的分組方式。

? ? ? ? 但是我們要注意，這些情況有可能不會全都有，因此我們可以先將x1 x2 y1 y2等賦值為

10010（題目中數組元素最大為10000），這樣我們在最后取max的時候就必然不會取到無效情況。

更新最小值以及次小值只需要分類討論即可?

class Solution {
public:int maxSumDivThree(vector<int>& nums) {int sum = 0;int n = nums.size();for(int i = 0; i < n; i++){sum += nums[i];}if(sum % 3 == 0){return sum;}else if(sum % 3 == 1){int x1,y1,y2;x1 = y1 = y2 = 1e4 + 10;for(int i = 0; i < n; i++){int tmp = nums[i];if(tmp % 3 == 1){x1 = min(x1, tmp);}else if(tmp % 3 == 2){if(tmp <= y1){y2 = y1;y1 = tmp;}else if(tmp > y1 && tmp <= y2){y2 = tmp;}}}return max(sum - x1, sum - y1 - y2);}else//取余等于2{int x1,x2,y1;x1 = x2 = y1 = 1e4 + 10;for(int i = 0; i < n; i++){int tmp = nums[i];if(tmp % 3 == 2){y1 = min(y1, tmp);}else if(tmp % 3 == 1){if(tmp <= x1){x2 = x1;x1 = tmp;}else if(tmp > x1 && tmp <= x2){x2 = tmp;}}}return max(sum - x1 - x2, sum - y1);}}
};

class Solution {
public:int maxSumDivThree(vector<int>& nums) {int sum = 0;int n = nums.size();for(int i = 0; i < n; i++){sum += nums[i];}if(sum % 3 == 0){return sum;}else if(sum % 3 == 1){int x1,y1,y2;x1 = y1 = y2 = 1e4 + 10;for(int i = 0; i < n; i++){int tmp = nums[i];if(tmp % 3 == 1){x1 = min(x1, tmp);}else if(tmp % 3 == 2){if(tmp <= y1){y2 = y1;y1 = tmp;}else if(tmp > y1 && tmp <= y2){y2 = tmp;}}}return max(sum - x1, sum - y1 - y2);}else//取余等于2{int x1,x2,y1;x1 = x2 = y1 = 1e4 + 10;for(int i = 0; i < n; i++){int tmp = nums[i];if(tmp % 3 == 2){y1 = min(y1, tmp);}else if(tmp % 3 == 1){if(tmp <= x1){x2 = x1;x1 = tmp;}else if(tmp > x1 && tmp <= x2){x2 = tmp;}}}return max(sum - x1 - x2, sum - y1);}}
};

?9.距離相等的條形碼

?1054. 距離相等的條形碼 - 力扣（LeetCode）

如果出現最多的數超過（n+1）/2，那么必定有兩個相同元素會相鄰?

我們只需要把最大的那個元素先排好，然后去排其它的即可，我們的i如果越界，那么將其置為1即可?

class Solution {
public:vector<int> rearrangeBarcodes(vector<int>& barcodes) {int maxval = -1; int maxcount = 0;unordered_map<int, int> hash;for(auto ch : barcodes ){if( maxcount < ++hash[ch] ){maxval = ch;maxcount = hash[ch];}}int n = barcodes.size();int i;vector<int> ret(n);for(i = 0; i < n && maxcount > 0; i += 2){ret[i] = maxval;maxcount --;}hash.erase(maxval);for(auto& [x, y] : hash){for(int j = 0; j < y; j++){if(i >= n)i = 1;ret[i] = x;i += 2;}}return ret;}
};

?10.重構字符串

767. 重構字符串 - 力扣（LeetCode）?

????????這道題和上一道題是一模一樣的的，唯一的不同就是這道題可能無解，因此我們需要判斷一些maxcount 會不會大于（s.size（）?+ 1）/2.?

class Solution {
public:string reorganizeString(string s) {int n = s.size();char maxval;int maxcount = 0;string ret = s;unordered_map<char, int> hash;for(auto ch: s){if(maxcount < ++hash[ch]){maxval = ch;maxcount = hash[ch];}}if(maxcount > (n + 1) / 2)return "";int i;for(i = 0; i < n && maxcount > 0; i += 2){ret[i] = maxval;maxcount--;}hash.erase(maxval);for(auto &[x, y] : hash){for(int j = 0; j < y; j++){if(i >= n)i = 1;ret[i] = x;i += 2;}}return ret;}
};