专题二十六_贪心策略(3)_算法专题详细总结

目录

贪心策略

1. 单调递增的数字（medium）

解析：

代码编写：

总结：

2. 坏了的计算器（medium）

解析：

解法一：正向推导：

解法二：正难则反

代码编写：

总结：

3. 合并区间（medium）

解析：

代码编写：

总结：

4. ⽆重叠区间（medium）

解析：

代码编写：

总结：

5. ⽤最少数量的箭引爆⽓球（medium）

解析：

代码编写：

总结：

6. 整数替换（medium）

解析：

代码编写：

总结：

7. 俄罗斯套娃信封问题（hard）

解析：

解法一：动态规划，正好拿来复习：300.最长递增子序列

解法二：（重写排序 + 贪⼼ + ⼆分）：

代码编写：

总结：

8. 可被三整除的最⼤和（medium）

解析：

代码编写：

总结：

9. 距离相等的条形码（medium）

解析：

代码编写：

总结：

10. 重构字符串（medium）

解析：

代码编写：

总结：

总结不易，本章对我有很大进步，希望对你也是~

贪心策略

通过前两次学习，我逐渐明白了贪心算法的核心思想。贪心的关键在于每一步都尽可能选择当前情况下的最优解，并期望通过这些局部最优解最终得到全局最优解。在应用贪心算法时，通常需要仔细分析问题，确保所选的贪心策略能够满足全局最优的要求。这种方法虽然简单高效，但并不适用于所有问题，只有当问题具备贪心选择性质和最优子结构时，贪心算法才可行。通过练习，我也逐渐能够判断哪些问题适合使用贪心策略，并学会在编程中灵活运用它。

1. 单调递增的数字（medium）

解析：

如果单纯用暴力，首先就是 -- 每一位，那么肯定会超时的，因为还要判断当前数字是否满足每一位不大于后一位的效果，所以这个肯定行不通~

那么就要考虑，将数字转换为字符串后进行判断：

1.首先判断当前数字是否可以直接进行返回，如果可以那就直接返回；否则，就进行修改后再次判断；

2.从最后一位开始轮流判断，遇到s[i] < s[i-1] 那么就进行修改s[i] = '9' ,s[i-1] -=1；每次进行一次修改就要判断当前数字是否满足条件，不然就会一直修改下去~

所以步骤1，2都有要判断当前数字是否满足条件，那么就单独提取出来为一个函数：

    bool _operator(string& s,int m){for(int i = 0;i < m - 1; i++){if(s[i]-'0' > s[i+1]-'0') break;if(i==m-2) return true;}return false;}

代码编写：

class Solution {
public:int monotoneIncreasingDigits(int n) {string s = to_string(n);int m = s.size();if(_operator(s,m)) return n;for(int i = m - 1; i >= 1; i--){s[i] = '9';s[i-1] -= 1;if(_operator(s,m)) return stoi(s);}return stoi(s);}bool _operator(string& s,int m){for(int i = 0;i < m - 1; i++){if(s[i]-'0' > s[i+1]-'0') break;if(i==m-2) return true;}return false;}
};

总结：

该题贪心就是要贪不能完全暴力，想办法减少时间复杂度的次数，也就是说要在原本的数字上直接进行改动才行！！！所以就是从最后一位开始修改，这样数字才会从最大开始慢慢变小~

2. 坏了的计算器（medium）

一个计算器上只能进行 '+' 和 '*' 两种方法，那么将一个数字用最少的操作次数来得到target

解析：

解法一：正向推导：

正向推导过于复杂，但是还是可以试试：

解法二：正难则反

这个target最终的结果分为奇数和偶数，当该数字为奇数的时候就把他置为偶数，也就是target+=1，因为最后这一步的操作是一定会做的，那么ret++；

i. 当 end <= begin 的时候，只能执⾏「加法」操作；

ii. 当 end > begin 的时候，对于「奇数」来说，只能执⾏「加法」操作；对于「偶数」来说，最好的⽅式就是执⾏「除法」操作

代码编写：

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

总结：

正难则反，这一题我正着推导的时候真的卡了好久！

3. 合并区间（medium）

解析：

a. 先按照区间的「左端点」排序：此时我们会发现，能够合并的区间都是连续的；

b. 然后从左往后，按照求「并集」的⽅式，合并区间。

a. 左端点就是「前⼀个区间」的左端点；

b. 右端点就是两者「右端点的最⼤值」

代码编写：

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {// 首先按照区间的起始点进行排序，确保我们可以依次处理区间sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b) {return a[0] < b[0];  // 按起始点升序排序});// 创建一个空的结果向量 merged，用来存储合并后的区间vector<vector<int>> merged;// 遍历所有区间for (int i = 0; i < intervals.size(); i++) {// 如果 merged 为空，或者当前区间与 merged 中最后一个区间没有重叠if (merged.empty() || merged.back()[1] < intervals[i][0]) {// 如果没有重叠，直接将当前区间加入到 merged 中merged.push_back(intervals[i]);} else {// 如果当前区间与最后一个区间有重叠，则合并它们// 合并的过程是更新 merged 中最后一个区间的结束点merged.back()[1] = max(merged.back()[1], intervals[i][1]);}}// 返回合并后的结果return merged;}
};

总结：

跟以前做过的一模一样，只需要考虑添加的时候这个问题，是否会重复连续出现多个包含问题~

4. ⽆重叠区间（medium）

解析：

a. 按照「左端点」排序；

b. 当两个区间「重叠」的时候，为了能够「在移除某个区间后，保留更多的区间」，我们应该把「区间范围较⼤」的区间移除。

间

代码编写：

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

总结：

要分析哪种情况满足，哪种不满足，想这一题怎么删除最小的次数，那么就得到最长的区间就欧克啦

5. ⽤最少数量的箭引爆⽓球（medium）

解析：

a. 按照左端点排序，我们发现，排序后有这样⼀个性质：「互相重叠的区间都是连续的」；

b. 这样，我们在射箭的时候，要发挥每⼀⽀箭「最⼤的作⽤」，应该把「互相重叠的区间」统⼀引爆。

a. 左端点为两个区间左端点的「最⼤值」（但是左端点不会影响我们的合并结果，所以可以忽略）；

b. 右端点为两个区间右端点的「最⼩值」。

代码编写：

class Solution {
public:int findMinArrowShots(vector<vector<int>>& points) {int n = points.size();sort(points.begin(),points.end());int left=points[0][0],right=points[0][1];int ret=1;for(int i=1;i<n;i++){int a=points[i][0],b=points[i][1];if(right>=a) {right=min(right,b);}else {right=b;ret++;}}return ret;}
};

总结：

这题最难的就是理解题意了，理解后只需要考虑贪心是贪最大的范围还是最小的范围即可，这一题贪心到最小的范围，因为当多个范围加进来后，范围逐渐变小才能一箭射穿多个气球

6. 整数替换（medium）

解析：

i. 当 n== 1 的时候，不⽤执⾏任何操作；

ii. 当 n == 3 的时候，变成 1 的最优操作数是 2 ；

iii. 当 n > 1 && n % 3 == 1 的时候，那么它的⼆进制表⽰是 ......01 ，最优的⽅式应该选择 -1 ，这样就可以把末尾的 1 ⼲掉，接下来执⾏除法操作，能够更快的变成 1 ；

iv. 当 n > 3 && n % 3 == 3 的时候，那么它的⼆进制表⽰是 ......11 ，此时最优的策略应该是 +1 ，这样可以把⼀堆连续的 1 转换成 0 ，更快的变成 1 。

代码编写：

class Solution {
public:int integerReplacement(int _n) {int ret=0;unsigned int n = _n;if(n==1) return 0;if(n==3) return 2;if(n==2) return 1; while(n!=1){if(n==1) return ret;if(n==3) return 2+ret;if(n==2) return 1+ret;if(n%2==1){ret++;if((n+1)%4==0) n+=1;else if((n-1)%4==0) n-=1;else n+=1;}n/=2;ret++;}return ret;}
};

总结：

这一题我是以4为分界点，分别来判断在除2后是否可以继续除2，所以只有这样才能加快当前数字翻倍减小的效率！

7. 俄罗斯套娃信封问题（hard）

解析：

解法一：动态规划，正好拿来复习：300.最长递增子序列

1. 状态表⽰：

dp[i] 表⽰：以 i 位置的信封为结尾的所有套娃序列中，最⻓的套娃序列的⻓度；

2. 状态转移⽅程：

dp[i] = max(dp[j] + 1) 其中 0 <= j < i && e[i][0] > e[j][0] && e[i][1] > e[j][1] ；

3. 初始化：

全部初始化为 1 ；

4. 填表顺序：

从左往右；

5. 返回值：

整个 dp 表中的最⼤值。

动态规划，求最长递增子序列会超时，这一题的数据量太大，时间复杂度是O(N^2)

class Solution {
public:int maxEnvelopes(vector<vector<int>>& envelopes) {int n=envelopes.size();sort(envelopes.begin(),envelopes.end());vector<int> dp(n,1);int ret=0;for(int i=0;i<n;i++){for(int j=0;j<i;j++){if(envelopes[j][0]<envelopes[i][0] && envelopes[j][1]<envelopes[i][1]) dp[i]=max(dp[j]+1,dp[i]);}ret=max(ret,dp[i]);}return ret;}
};

解法二：（重写排序 + 贪⼼ + ⼆分）：

i. 左端点不同的时候：按照「左端点从⼩到⼤」排序；

ii. 左端点相同的时候：按照「右端点从⼤到⼩」排序

型。那么我们就可以⽤「贪⼼ + ⼆分」优化我们的算法。

代码编写：

class Solution {
public:int maxEnvelopes(vector<vector<int>>& envelopes) {int n=envelopes.size();sort(envelopes.begin(),envelopes.end(),[&](vector<int>& a,vector<int>& b){if(a[0]==b[0]) return a[1]>b[1];else return a[0]<b[0];});vector<int> ret;ret.push_back(envelopes[0][1]);for(int i=1;i<n;i++){int b=envelopes[i][1];if(ret.back()<b){ret.push_back(b);}else {int left=0,right=ret.size()-1;while(left<right){int mid=(right-left)/2+left;if(b>ret[mid]) left=mid+1;else right=mid;}ret[left]=b;//直接进行修改}}cout<<ret.size()<<endl;return ret.size();}
};

总结：

该题就是前面讲过的求最长递增子序列的贪心+二分算法，因为动态规划时间复杂度太高，会超时这种办法就能够有效降低时间复杂度，还是学会更好~

8. 可被三整除的最⼤和（medium）

解析：

a. sum % 3 == 0 ，此时所有元素的和就是满⾜要求的，那么我们⼀个也不⽤删除；

b. sum % 3 == 1 ，此时数组中要么存在⼀个 x ，要么存在两个 y 。因为我们要的是最⼤值，所以应该选择 x 中最⼩的那么数，记为 x1 ，或者是 y 中最⼩以及次⼩的两个数，记为 y1, y2 。

那么，我们应该选择两种情况下的最⼤值： max(sum - x1, sum - y1 - y2) ；

c. sum % 3 == 2 ，此时数组中要么存在⼀个 y ，要么存在两个 x 。因为我们要的是最⼤值，所以应该选择 y 中最⼩的那么数，记为 y1 ，或者是 x 中最⼩以及次⼩的两个数，记为 x1, x2 。

代码编写：

class Solution {
public:int maxSumDivThree(vector<int>& nums) {int n = nums.size();sort(nums.begin(),nums.end());int ret=0;vector<int> a;vector<int> b;for(auto e : nums){ret+=e;if(e%3==1) a.push_back(e);else if(e%3==2) b.push_back(e);}if(ret%3==0) return ret;if(n==1) return 0;     int index=0;if(ret%3==1){for(int i=0;i<a.size();i++){ret-=a[i];if(ret%3==0) {index=ret;ret+=a[i];break;}ret+=a[i];}for(int i=0;b.size()>=2&&i<b.size()-1;i++){int j=i+1;ret=ret-b[i]-b[j];if(ret%3==0&&ret>index){index=ret;break;}else if(ret<=index){break;}}}if(ret%3==2){for(int i=0;i<b.size();i++){ret-=b[i];if(ret%3==0) {index=ret;ret+=b[i];break;}ret+=b[i];}for(int i=0;a.size()>=2&&i<a.size()-1;i++){int j=i+1;ret=ret-a[i]-a[j];if(ret%3==0&&ret>index){index=ret;break;}else if(ret<=index){break;}}}return index;}
};

总结：

看懂解析后就是无脑if else 来判断ret最大的和，这里强烈建议自己手敲，先别看我的代码，很锻炼代码能力~

9. 距离相等的条形码（medium）

解析：

但是我觉得我写的有点麻烦了，但是还是很好想的：

首先将所有数字都存入hash后进行计算出现的次数，这里就实现了去重，但是要取到hash内的k和v就可以直接用auto来存入优先级队列内即可~ 

每次都将出现次数最多的数字拿出来摆放，如果前一个数字仍然是当前数字，那么就继续拿一个数字出来摆放，然后减去次数后再重新插入队列内

代码编写：

class Solution {
public:struct compare {bool operator()(pair<int,int>& a, pair<int,int>& b){return a.second<b.second;}};vector<int> rearrangeBarcodes(vector<int>& barcodes) {int n=barcodes.size();// sort(barcodes.begin(),barcodes.end());unordered_map<int,int> hash;//数字-次数for(auto e : barcodes){hash[e]++;}//去重冗余，直接用auto unorder_map<> hash去重// unordered_set<int> b;// for(auto e : barcodes)// {//     b.insert(e);// }vector<int> ret;priority_queue<pair<int,int>,vector<pair<int,int>>,compare> q;//直接用auto unorder_map<> hash去重for(auto& [k,v] : hash){q.push({k,v});}// cout<<q.top().first<<" "<<q.top().second<<endl;while(!q.empty()){pair<int,int> b=q.top();q.pop();int a=b.first;if(ret.empty() || ret.back()!=a){ret.push_back(a);b.second--;}else if(ret.back()==a){pair<int,int> c=q.top();q.pop();ret.push_back(c.first);c.second--;if(c.second) q.push(c);}if(b.second) q.push(b);}return ret;}
};

总结：

这一题其实思路还是很简单的，就是要考虑代码能力，构建优先级队列，包括排序，去重等一些列问题，最后就是贪每次都要取出现次数最多的那一个数

10. 重构字符串（medium）

这一题就跟上面一题一模一样了，只是vector<int> 改成了string

解析：

解法（贪⼼）：

贪⼼策略：

每次处理⼀批相同的数字，往 n 个空⾥⾯摆放；

每次摆放的时候，隔⼀个格⼦摆放⼀个数；

优先处理出现次数最多的那个数。

那这一题就不过多赘述了，全部都是一样的，只需要将string的每一个字符转成int存入vector<int>就行

代码编写：

class Solution {
public:struct compare {bool operator()(pair<int,int>& a, pair<int,int>& b){return a.second<b.second;}};string reorganizeString(string s) {vector<int> barcodes;for(auto e : s) barcodes.push_back(e-'a');int n=barcodes.size();unordered_map<int,int> hash;//数字-次数for(auto e : barcodes) hash[e]++;vector<int> ret;priority_queue<pair<int,int>,vector<pair<int,int>>,compare> q;for(auto& [k,v] : hash){q.push({k,v});}while(!q.empty()){pair<int,int> b=q.top();q.pop();int a=b.first;if(ret.empty() || ret.back()!=a){ret.push_back(a);b.second--;}else if(ret.back()==a){if (q.empty()) return "";  // 队列为空时，无法取出其他字符pair<int,int> c=q.top();q.pop();ret.push_back(c.first);c.second--;if(c.second) q.push(c);}if(b.second) q.push(b);}string str;for(auto e : ret) str+=(e+'a');return str;}
};