目录
最后再按照pair 第二个int的序号进行排序即可~,int>
贪心：每次只要遇到偶数个字符或者大于1个的单字符全都加上它的偶数次数
最开始在想该怎么贪心呢？双指针吗？还是要三指针来记录前后的值？
贪心策略：
有过前面贪心的总结，接下来进入贪心就更加得心应手了：
1. K 次取反后最⼤化的数组和（easy）
题目意思很简单，就是经过k次将数组内容nums[i]取反后，求出最大和的一种情况
解析：
暴力：
每次只考虑最小的那个负数，如果次数还没有用完，就一直将最小的正数进行取反
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
for(int i=0;i<k;i++)
{
sort(nums.begin(),nums.end());
if(k!=1&&nums[0]>=0)
{
nums[0]=(k-i)%2==0?nums[0]:-nums[0];
break;
}
nums[0]=-nums[0];
}
int ret=0;
for(auto e : nums) ret+=e;
return ret;
}
};优化：贪心
代码编写：
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
int ret=0;
int n=nums.size();
int m=0;
for(int i=0;i<n;i++)
{
if(nums[i]<0) m++;
}
if(k<m)
{
sort(nums.begin(),nums.end());
for(int i=0;i<k;i++)
{
nums[i]=-nums[i];
}
for(auto e : nums) ret+=e;
}
else
{
int e=0;
int _min=INT_MAX;
for(int i=0;i<n;i++)
{
if(nums[i]<0) nums[i]=-nums[i],e++;
ret+=nums[i];
_min=min(_min,nums[i]);
}
if((k-e)%2) ret-=2*_min;
}
return ret;
}
};总结：
需要仔细思考每一种情况会出现的问题，这样才能避免很多次没有用的排序，像这一题就是对数组内小于0的个数进行判断，如果操作次数小于数组内小于0的个数，那么就可以直接取反最小的负数；反之就是将所有负数都取反后来判断是否是否还要将最小的正数进行取反
2. 按⾝⾼排序（easy）
解析：
这一题我们在前面的专题写过很多次了，虽然不是贪心，但是是为了给下题进行铺垫的，就是创建一个pair<string,int>的优先级队列，然后进行按照int排序后来获取string的顺序，还是很简单的
最主要的还是排序的compare比较的书写，自定义比较器需要定义一个 bool 类型的 operator() 函数。
代码编写：这里提供两种排序方法：
1.堆排序：
class Solution {
public:
struct compare {
bool operator()(pair<string,int> a,pair<string,int> b)
{
return a.second<b.second;
}
};
vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
priority_queue<pair<string,int>,vector<pair<string,int>>,compare> hash;
int n=names.size();
for(int i=0;i<n;i++)
{
hash.push({names[i],heights[i]});
}
vector<string> ret;
while(!hash.empty())
{
string s;
s=hash.top().first;
hash.pop();
ret.push_back(s);
}
return ret;
}
};2.快排：
class Solution {
public:
vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
vector<pair<string,int>> hash;
int n=names.size();
for(int i=0;i<n;i++)
hash.push_back({names[i],heights[i]});
sort(hash.begin(),hash.end(),[](pair<string,int>& a,pair<string,int>& b)
{
return a.second>b.second;
});
vector<string> ret;
for(auto e : hash)
ret.push_back(e.first);
return ret;
}
};总结：
现在再看这一题，已经可以直接秒杀了，为我开心~
3. 优势洗牌（⽥忌赛⻢）（medium）
解析：
有了上一题的借鉴，这一题简直好太多了~
eg1：
eg2：
那么经过排序后得到的结果分成两种，nums1[i] > nums2[j]的值，就直接添加到ret内，若nums1[i] < nums2[j]的值，就添加到redundant内，表示多余的值，就是要留在最后进行添加到ret内，表示较小的值比上nums2较大的值，因为已经不可能有比当前值还要小的了，这里就是田径赛马的思想了
最后再按照pair<int,int> 第二个int的序号进行排序即可~
代码编写：又成功ac一道~
class Solution {
public:
vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
if(nums1==nums2) return nums1;
int n=nums1.size();
vector<pair<int,int>> hash;
for(int i=0;i<n;i++) hash.push_back({nums2[i],i});
sort(hash.begin(),hash.end(),[&](pair<int,int>& a,pair<int,int>& b)
{
return a.first < b.first;
});
sort(nums1.begin(),nums1.end());
int e=0;
vector<pair<int,int>> ret;
vector<int> redundant;
int j=0;
for(int i=0;i<n;i++)
{
if(nums1[i]>hash[j].first)
{
ret.push_back({nums1[i],hash[j++].second});
}
else
{
redundant.push_back(nums1[i]);
}
}
int m=redundant.size();
for(int i=0;i<m;i++)
{
ret.push_back({redundant[i],hash[n-m+i].second});
}
sort(ret.begin(),ret.end(),[&](pair<int,int>& a,pair<int,int>& b)
{
return a.second < b.second;
});
vector<int> _ret;
for(auto e : ret) _ret.push_back(e.first);
return _ret;
}
};总结：
这一道题还是很有趣的，主要还是要在草稿纸上多描述多绘画几遍，不断试错，肯定可以得到最后的结果的~
4. 最⻓回⽂串（easy）
解析：
贪心：每次只要遇到偶数个字符或者大于1个的单字符全都加上它的偶数次数
创建一个hash表来记录每个字符出现的次数
string _s;
unordered_map<char,int> hash;
for(auto e : s)
{
if(!hash.count(e)) _s+=e;
hash[e]++;
}代码编写：
class Solution {
public:
int longestPalindrome(string s) {
int ret=0;
int n=s.size();
string _s;
unordered_map<char,int> hash;
for(auto e : s)
{
if(!hash.count(e)) _s+=e;
hash[e]++;
}
int f=0;
if(hash.size()==1) return hash[s[0]];
for(auto e : _s)
{
if(hash[e]%2==1) f=1;
if(hash[e]%2==1&&hash[e]>2) ret+=hash[e]-1;
if(hash[e]%2==0) ret+=hash[e];
}
if(f==1) ret+=1;
return ret;
}
};总结：
题目是简单的贪心策略，只要能想到回文串的定义，字符出现偶数次就能满足条件，就可以解决该问题
5. 增减字符串匹配（easy）
当前字符是'I'就要满足p[i] < p[i+1] 否则就要满足p[i] < p[i+1]
解析：
最开始在想该怎么贪心呢？双指针吗？还是要三指针来记录前后的值？
但是这里就有一个问题，如果我只是盲目的填值，无法确定大小，可能填道最后，会出现数字不够的情况，因为[1,n]数字都只出现一次；
那么就只能来研究测试用例来找规律：
所以有了上面的规律之后，解决问题就好办多了，只需要开头记录字符串的长度，然后就可以开始往ret内进行添加即可；也就是说数字最大，也只能是n，最小也只能是0，所以从两个极端开始选择~
贪⼼策略：
a. 当遇到 'I' 的时候，为了让下⼀个上升的数可选择的「范围更多」，当前选择「最⼩」的那个数；b. 当遇到 'D' 的时候，为了让下⼀个下降的数可选择的「范围更多」，选择当前「最⼤」的那个数。
代码编写：
class Solution {
public:
vector<int> diStringMatch(string s) {
int n=s.size();
vector<int> ret;
int num1=0,num2=0;
for(int i=0;i<n;i++)
{
if(s[i]=='I') num1++;
else num2++;
}
int j=n,k=0;
for(int i=0;i<n;i++)
{
if(s[i]=='I') ret.push_back(k++);
else ret.push_back(j--);
}
if(s[n-1]=='D') ret.push_back(j);
else ret.push_back(k);
return ret;
}
};总结：
找规律题还是很有趣的，如果没发现真的挺难的，还是要多试错~
6. 分发饼⼲（easy）
就是要饼干满足最多孩子的胃口
解析：
贪心：
将两个数组进行排序后，就又满足从胃口小的来吃最小的饼干，当一个孩子能够吃下这个饼干，i指针才往后移动，否则就移动j指针，因为只有饼干变大才有意义，否则孩子胃口变大，饼干大小不变是没有意义的
那么就在一个while内进行判断，直到饼干被遍历完，或者所有孩子得到满足为止
代码编写：
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
// 对胃口值和饼干尺寸排序
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int ret = 0; // 满足的孩子数量
int i = 0, j = 0; // 分别为孩子和饼干的指针
// 遍历两个数组
while (i < g.size() && j < s.size()) {
if (g[i] <= s[j]) { // 如果饼干满足孩子的胃口
ret++;
i++; // 下一个孩子
}
j++; // 无论是否满足，换下一块饼干
}
return ret; // 返回满足孩子的数量
}
};总结：
题目还是很简单的，就只需要排序后来判断当前饼干是否满足孩子胃口，因为当前饼干不满足，那么就更不会满足后面的孩子，所以只能挑更大的饼干来比较
7. 最优除法（medium）
在这个数组内，每个数组都是按顺序相除，但是你可以通过添加括号来改变优先级，得到一个最大的值
解析：
从结果出发，加括号这一操作的结果无非就是把算式中的部分除号变成乘号。 要想得到最大值，只需要让算式里的乘号尽可能多，除了第一个除号没法变之外，把从第二个数开始的所有数括起来就可以让后面的所有除号变成乘号。
这题真的就有点搞笑了，从测试用例出发，只需要把第二个数开始的所有数用括号括起来就行~
代码编写：
class Solution {
public:
string optimalDivision(vector<int>& nums) {
int n=nums.size();
string s;
if(n==1) return to_string(nums[0]);
else if(n==2)
{
s+=to_string(nums[0]);
s+='/';
s+=to_string(nums[1]);
return s;
}
for(int i=0;i<n;i++)
{
s+=to_string(nums[i]);
if(i!=n-1) s+='/';
if(i==0) s+='(';
if(i==n-1) s+=')';
}
return s;
}
};总结：
贪心，贪的就是最后分母上一定要最小只要先算第一个数后面的所有数字，让它们一直除就能除到最小，然后再进行计算
8. 跳跃游戏 Ⅱ（medium）
解析：
贪心策略：每次都贪最大的跳转范围，直到跳转范围能够超过n-1,这样就能保证跳转的次数最少
可以看出num来记录每次跳转的最大范围，然后再每次跳转的最大范围内记录下标+nums[i]的最大值_max, 因为只有当_max最大的时候，下一次的跳转范围才会更大，再更大的跳转范围内，就可以取寻找下下次跳转的最大范围，因为只要再这个范围内，就可以随意跳转，只要我们能到一个下次能跳转范围最大的值，就可以保证跳转的次数最少！
那么num记录每次跳转的极限下标；
_max记录每次跳转的范围内，下次跳转的更大范围
j就用来记录，下次跳转是从哪个下标开始，就是记录最大的_max的下标
代码编写：
class Solution {
public:
int jump(vector<int>& nums) {
int n=nums.size();
int ret=0;
int _max=0+nums[0];
int num=_max;
if(n==1) return 0;
int j=0;
for(int i=0;i<n;i++)
{
if(i<=num&&_max<(nums[i]+i))
{
_max=nums[i]+i;
if(_max>=n-1) ret++;
j=i;
}
if(_max>=n-1)
{
ret++;
break;
}
if(i==num)
{
ret++;i=j;num=_max;
}
}
return ret;
}
};总结：
这一题的贪心简直用到淋漓尽致，我都为我自己开心~每次都贪最大的跳转范围，这样肯定就能保证跳转的次数最少
9. 跳跃游戏（medium）
解析：
当一个数组不存在nums[i]==0的时候，那么这个数组就一定可以到达终点；
举一个不能到达终点的例子：我能跳跃的范围就是当前位置的下标 + nums[i]
如下：前三个数，最大都只能跳跃到nums[3]的位置，而nums[3]==0,所以再nums[i]==0的位置是无法继续往后跳跃的，也就是说，无论前面有多大的数字，只要全都不能越过nums[i]==0这个位置的话，那么就永远都不能到达终点；
那么我就设置一个数组v来专门记录整个数组的0的下标，然后再一个for内判断，当i==每一个0的下标的时候，就判断一下，前面能越过的最大的范围是否能够越过当前0的下标，如果可以就继续，直到跳跃到终点就返回true；否则就返回false！
代码编写：
class Solution {
public:
bool canJump(vector<int>& nums) {
int n=nums.size();
int f=0;
vector<int> v;
for(int i=0;i<n;i++)
{
if(nums[i]==0)
{
f=1;
v.push_back(i);
}
}
if(f==0) return true;
int m=v.size();
int _max=0;
int j=0;
for(int i=0;i<n;i++)
{
_max=max(nums[i]+i,_max);
if(j<m&&v[j]==i)
{
if(_max>=n-1) return true;
else if(_max>i) j++;
else return false;
}
}
return true;
}
};总结：
跟上题大差不差，还是挺简单的，很好想，只要想清楚一个测试用例，就很顺理成章的找到解题思路了~
10. 加油站（medium）
在经过每一个加油站的时候都会加油，然后去往下一个加油站又会消耗油，观察是否会出现一个在环形的路线上上能否正常回到当前加油站
解析：
暴力：
每次只有在加油站获得的油大于等于消耗掉油，到达下一个加油站的时候
其中差值大于0 就能够到达下一个加油站，小于0的就说明不能从当前位置开始出发；
那么我就用数组v将所有能够出发的位置的下标记录下来，然后模拟这个过程，判断是否能够成功
代码编写：
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
vector<int> v;
int n=gas.size();
for(int i=0;i<n;i++)
if(gas[i]>=cost[i]&&gas[i]!=0&&gas[i]!=1) v.push_back(i);
int m=v.size();
for(int i=0;i<m;i++)
{
int j=v[i];
int sum=0;
int f=0;
for(int k=0;k<n;k++)
{
sum+=gas[j];
sum-=cost[j];
if(sum<0)
{
f=1;
break;
}
j=(j+1)%n;
}
if(f==0) return v[i];
}
return -1;
}
};优化：贪心
我们在一个for内进行考虑当前位置是否可以成为起点~不行就continue
最主要就是遍历该位置的时候来判断当前位置走的步数k来记录，来模拟加油和消耗油的这个过程，从0步开始，进行模拟，直到走完一圈为止，如果在中途出现了sum小于0的情况，就说明不能成功到达下一个加油站，这个时候贪心就出来了：
在这个过程中，里面加油的量绝对是正数，如果我们从头开始遍历到当前为止，也是绝对不会成功的；
代码编写：
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int n=gas.size();
for(int i=0;i<n;i++)
{
if(gas[i]-cost[i]<0) continue;
int sum=0;
int f=0;int k=0;
for(;k<n;k++)
{
int index=(i+k)%n;
sum=sum+gas[index]-cost[index];
if(sum<0) break;
}
if(sum>=0) return i;
i+=k;
}
return -1;
}
};总结：
这一题的贪心还是很难想到的，但是暴力好想，只要能在暴力上做优化，应该没什么大问题~