贪心算法【3】
·
1. (991.) 坏了的计算器
思路：
如果按照题目给定要求来操作，那么每一步的操作是不确定的，二选一需要额外判断条件复杂很多。采取正难则反的思想，刚好操作符号相对应并且题目要求为整数，所以对于奇数和偶数的操作都是固定的，思路清晰代码简洁
2. (56.) 合并区间
思路：
贪⼼策略：
a. 先按照区间的左端点排序：此时会发现，能够合并的区间都是连续的；
b. 然后从左往后，按照求并集的⽅式，合并区间。
如何求并集：
由于区间已经按照左端点排过序了，因此当两个区间合并的时候，合并后的区间：
a. 左端点就是前⼀个区间的左端点；
b. 右端点就是两者右端点的最⼤值。
如果无法求得并集就更新做右端点继续往后循环往复求并集
- 该题属于区间问题，区间问题做法先按照左端点或右端点进行排序，然后再根据排序结果找规律得出解决问题策略
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> ret;
sort(intervals.begin(),intervals.end());
int left=intervals[0][0],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;
}
};
3. (435.) ⽆重叠区间
贪⼼策略：
a. 按照左端点排序；
b. 当两个区间重叠的时候，为了能够在移除某个区间后，保留更多的区间，我们应该把区间范围较⼤的区间移除
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(),intervals.end());
int ret=0,left=intervals[0][0],right=intervals[0][1];
for(int i=1;i<intervals.size();i++)
{
int a=intervals[i][0],b=intervals[i][1];
if(a<right) {
right=min(right,b);//查找并移除重复区间较大的那一个
ret++;
}
else{//没有重叠区间，更新端点继续比较
left=a,right=b;
}
}
return ret;
}
};
4. (452.) ⽤最少数量的箭引爆⽓球
贪⼼策略：
a. 按照左端点排序，排序后有这样⼀个性质：互相重叠的区间都是连续的；
b. 这样，在射箭的时候，要发挥每⼀⽀箭最⼤的作⽤，应该把互相重叠的区间统⼀
引爆。
如何求互相重叠区间？
由于我们是按照左端点排序的，因此对于两个区间，我们求的是它们的交集：
a. 左端点为两个区间左端点的最⼤值（但是左端点不会影响我们的合并结果，所以可以忽略）；
b. 右端点为两个区间右端点的最⼩值。
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
sort(points.begin(),points.end());
int ret=1,right=points[0][1];
for(int i=1;i<points.size();i++)
{
int a=points[i][0],b=points[i][1];
if(a<=right){//区间存在重叠
right=min(right,b);//求交集
}
else//不存在重叠部分
{
ret++;//初始引爆需要一支箭，后续每一个重叠区间需要一支
right=b;
}
}
return ret;
}
};
5. (397) 整数替换
- 递归+记忆化搜索
- 这段代码的递归核心是分治 + 记忆化：将大问题（n→1）拆解为小问题（n/2→1、n±1→1），用哈希表缓存小问题的结果避免重复计算；
- 递归终止条件是n==1（返回 0），分支逻辑是：偶数直接除以 2，奇数选择加 1 / 减 1 中步骤更少的路径；
- long long参数解决了n=INT_MAX时加 1 溢出的问题，是递归能正确执行的关键细节。
class Solution {
// 哈希表：key是n的值，value是n转为1的最小步骤数，用于缓存已计算结果
unordered_map<int,int> hash;
public:
int integerReplacement(int n) {
return dfs(n);
}
int dfs(long long n)
{
if(hash.count(n)) return hash[n];
if(n==1) return 0;
if(n%2==0)
{
hash[n]=dfs(n/2)+1;//当前除二这个操作也要加上
return hash[n];
}
else
{
hash[n]=1+min(dfs(n+1),dfs(n-1));
return hash[n];
}
}
};
- 贪心：
贪心在于对奇数的处理，递归是±都计算一遍取最优结果，贪心是直接选最好的一种去计算，利用二进制表示的最后两位判断最优结果，通过%4操作可以判断二进制表示种最后两位的类型，注意n=3时需要单独判断，选择能让末尾连续 0 最多”的操作加减 1，从而最大化后续的右移次数，最小化总操作数；
class Solution {
public:
int integerReplacement(long long n) {
int ret=0;
while(n!=1)
{
if(n%4==1) n-=1;
else if(n%4==3&&n!=3) n+=1;
else if(n%2==0) n/=2;
else if(n==3) n-=1;
ret++;
}
return ret;
}
};
6. (354.) 俄罗斯套娃信封问题
- 思路1：动态规划
与贪心算法【1】中的最长递增子序列动态规划思路一样
将数组按照左端点排序之后，问题就转化成了最⻓上升⼦序列模型，那接下来我们就可以⽤解决最⻓上升⼦序列的经验，来解决这个问题（会超时）
- 状态表⽰：
dp[i] 表⽰：以 i 位置的信封为结尾的所有套娃序列中，最⻓的套娃序列的⻓度； - 状态转移⽅程：
dp[i] = max(dp[j] + 1,dp[i]) 其中 0 <= j < i && e[i][0] > e[j][0] && e[i][1] > e[j][1] ； - 初始化：
全部初始化为 1 ； - 填表顺序：
从左往右； - 返回值：
整个 dp 表中的最⼤值
- 思路2：贪心+二分
左端点不同的时候：按照左端点从⼩到⼤排序；
左端点相同的时候：按照右端点从⼤到⼩排序(为了避免左端点全相同的情况，默认排序出来的结果再用右端点排序可能不满足题意)
我们发现，问题就变成了仅考虑信封的右端点，完完全全的变成的最⻓上升⼦序列的模型。那么我们就可以⽤贪⼼ + ⼆分优化我们的算法。
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& e) {
//重写排序，分情况讨论
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<e.size();i++)
{
if(e[i][1]>ret.back()) ret.push_back(e[i][1]);
else{
int l=0,r=ret.size()-1;
while(l<r)
{
int mid=(l+r)/2;
if(e[i][1]>ret[mid]) l=mid+1;
else r=mid;
}
ret[l]=e[i][1];
}
}
return ret.size();
}
};
7. (1262.) 可被三整除的最⼤和
思路：
题目要求返回相加后能被3整除的最大和，采取正难则反的思想，先全部相加。再判断通过慢慢减数来实现，这样思维更简单
class Solution {
public:
int maxSumDivThree(vector<int>& nums) {
const int INF=0x3f3f3f3f;//因为存在减两个数的操作所以用最大值会溢出
int sum=0,x1=INF,x2=INF,y1=INF,y2=INF;
for(auto x:nums)
{
sum+=x;
//求最小值和次小值
if(x%3==1)
{
if(x<x1)x2=x1,x1=x;
else if(x>=x1&&x<x2) x2=x;
}
if(x%3==2)
{
if(x<y1) y2=y1,y1=x;
else if(x>=y1&&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);//注意这里else不能加条件，否则编译器会认为最后else路径没有返回值，只检查语法
}
};
8. (1054.) 距离相等的条形码
贪⼼策略：
1.每次处理⼀批相同的数字，往 n 个空⾥⾯摆放；
2.每次摆放的时候，隔⼀个格⼦摆放⼀个数；
3.优先处理出现次数最多的那个数(确保相邻数不等)。剩下数处理顺序无所谓，间隔摆放即可
题目要求一定有解，将两个位置看成一组，多余位置自成一组，出现最多次数的那个数肯定不超过分组数，如图所示
class Solution {
public:
vector<int> rearrangeBarcodes(vector<int>& barcodes) {
unordered_map<int,int> hash;
int maxval=0,maxcount=0;
//统计出现最多的那个数
for(auto x:barcodes)
{
hash[x]++;
if(maxcount<hash[x])
{
maxval=x;
maxcount=hash[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 &[a,b]:hash)
{
for(int i=0;i<b;i++)
{
if(index>=n) index=1;//判断是否越界
ret[index]=a;
index+=2;
}
}
return ret;
}
};
9. (767.) 重构字符串
与上题贪心思想一样，每次处理同一批数，先排出现次数最多的字符，插空排序，再处理剩余字符
class Solution {
public:
string reorganizeString(string s) {
unordered_map<char,int> hash;
char maxval='0';
int maxcount=0;
for(auto x:s)
{
hash[x]++;
if(maxcount<hash[x]) maxcount=hash[x],maxval=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]=maxval;
index+=2;
}
//hash表中删除出现次数最多的那个字符
hash.erase(maxval);
//处理剩余字符
for(auto &[a,b]:hash)
{
for(int i=0;i<b;i++)
{
if(index>=n) index=1;
ret[index]=a;
index+=2;
}
}
return ret;
}
};
更多推荐
12
0- 0
已为社区贡献2条内容
所有评论(0)