leetcode贪心算法题总结(三)

本章目录

1.合并区间
2.无重叠区间
3.用最少数量的箭引爆气球
4.整数替换
5.俄罗斯套娃信封问题
6.可被三整除的最大和
7.距离相等的条形码
8.重构字符串

1.合并区间

合并区间
在这里插入图片描述

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {int n = intervals.size();//先按左端点进行排序sort(intervals.begin(),intervals.end());int left = intervals[0][0],right = intervals[0][1];vector<vector<int>> ret;//进行区间合并for(int i=1;i<n;i++){int a = intervals[i][0],b = intervals[i][1];if(a<=right) right = max(right,b);else{ret.push_back({left,right});left = a;right = b;}}ret.push_back({left,right});return ret;}
};

2.无重叠区间

无重叠区间
在这里插入图片描述

class Solution {
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {int n = intervals.size();//按照左端点进行排序sort(intervals.begin(),intervals.end());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;}
};

3.用最少数量的箭引爆气球

用最少数量的箭引爆气球
在这里插入图片描述

class Solution {
public:int findMinArrowShots(vector<vector<int>>& points) {int n = points.size();//按左端点进行排序sort(points.begin(),points.end());//求交集int ret = 0;int right = points[0][1];for(int i=1;i<n;i++){int a = points[i][0],b = points[i][1];if(a<=right){right = min(right,b);}else{ret++;right = b;}}return ret+1;//最后一个也需要一支箭}
};

4.整数替换

整数替换
在这里插入图片描述

class Solution {unordered_map<long long,long long> hash;//存储某一个数到1的最小步数
public:int integerReplacement(int n) {//法一：递归+记忆化搜索return dfs(n);}long long dfs(long long n){if(hash.count(n)) return hash[n];if(n == 1){hash[1] = 0;return hash[1];}if(n%2==0){hash[n] = 1+dfs(n/2);return hash[n];}else{hash[n] = 1+min(dfs(n+1),dfs(n-1));return hash[n];}}
};

class Solution {
public:int integerReplacement(int n) {//法二：贪心+找规律int ret = 0;while(n>1){if(n%2 == 0){n /= 2;ret++;}else{if(n == 3) {ret += 2;n =1;}else if(n%4 ==1){ret +=2;n /=2;}else{ret += 2;n = n/2 +1;}}}return ret;}
};

5.俄罗斯套娃信封问题

俄罗斯套娃信封问题
在这里插入图片描述

class Solution {
public:int maxEnvelopes(vector<vector<int>>& e) {//法一：动态规划 O(n^2) 超时//状态表示：dp[i]表示：以i位置的信封为结尾的所有套娃序列中，最长的套娃序列的长度int n = e.size();vector<int> dp(n,1);sort(e.begin(),e.end());int ret = 1;for(int i=1;i<n;i++){for(int j=0;j<i;j++){if(e[i][0]>e[j][0]&&e[i][1]>e[j][1]){dp[i] = max(dp[i],dp[j]+1);}}ret = max(ret,dp[i]);}return ret;}
};

在这里插入图片描述

class Solution {
public:int maxEnvelopes(vector<vector<int>>& e) {//法二：重写排序+贪心+二分int n = e.size();sort(e.begin(),e.end(),[&](const vector<int>& v1,const vector<int>& v2){return v1[0]!=v2[0]?v1[0]<v2[0]:v1[1]>v2[1];});//此时问题转化成我们之前写过的最长递增子序列问题vector<int> ret;ret.push_back(e[0][1]);for(int i=1;i<n;i++){int a = e[i][1];if(a>ret.back()){ret.push_back(a);}else{int left = 0,right = ret.size()-1;while(left<right){int mid = (left+right)>>1;if(ret[mid]>=a) right = mid;else left = mid+1;}ret[left] = a;}}return ret.size();}
};

6.可被三整除的最大和

可被三整除的最大和
在这里插入图片描述

class Solution {
public:int maxSumDivThree(vector<int>& nums) {//正难则反 //把所有的数都累加起来，根据累加和进行删除const int INF = 0x3f3f3f3f;int x1 = INF,x2 = INF,y1 = INF,y2 = INF,sum = 0;for(auto x:nums){sum+=x;if(x%3 ==1){if(x<x1){x2 = x1;x1 = x;}else if(x<=x2){x2 = x;}}else if(x%3 ==2){if(x<y1){y2 = y1;y1 = x;}else if(x<=y2){y2 = x;}}}//分类讨论if(sum%3==0) return sum;else if(sum%3 ==1) return max(sum-x1,sum-y1-y2);else return max(sum-y1,sum-x1-x2);}
};

7.距离相等的条形码

距离相等的条形码
在这里插入图片描述

class Solution {
public:vector<int> rearrangeBarcodes(vector<int>& barcodes) {unordered_map<int,int> hash;//统计每个数字出现的次数int maxVal = 0,maxCount = 0;for(auto x:barcodes){if(maxCount<++hash[x]){maxCount = hash[x];maxVal = x;}}//先处理出现次数最多的哪个数int n = barcodes.size();vector<int> ret(n);int index = 0;for(int i=0;i<maxCount;i++){ret[index] = maxVal;index += 2;}//再处理其他的数hash.erase(maxVal);for(auto&[x,y] : hash){for(int i=0;i<y;i++){if(index>n-1) index = 1;ret[index] = x;index += 2;}}return ret;}
};

8.重构字符串

重构字符串
在这里插入图片描述

class Solution {
public:string reorganizeString(string s) {//模拟+贪心int hash[26] = {0};char maxChar = ' ';int maxCount = 0;for(auto x:s){if(maxCount<++hash[x-'a']){maxCount = hash[x-'a'];maxChar = x;}}//先判断int n = s.size();if(maxCount>(n+1)/2) return "";string ret(n,' ');int index = 0;//先处理出现次数最多的那个字符for(int i=0;i<maxCount;i++){ret[index] = maxChar;index += 2;}//再处理其他字符hash[maxChar-'a'] = 0;for(int i=0;i<26;i++){for(int j=0;j<hash[i];j++){if(index>n-1) index = 1;ret[index] = 'a'+i;index += 2;}}return ret;}
};