贪心算法（2）
目录
K次取反后最大化的数组和
题解：
代码：
按身高排序（田忌赛马的预备）
题解：
代码：
方法一：
方法二：
优势洗牌（田忌赛马）
题解：
代码：
最长回文串
题解：
代码：
增减字符串匹配
题解：
代码：
分发饼干（田忌赛马）
题解：
代码：
最优除法
题解：
代码：
K次取反后最大化的数组和
1005. K 次取反后最大化的数组和 - 力扣（LeetCode）
https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/
题解：
为了最大化数组和，就要对数组中最小的 k 个数取反，我们统计出数组中负数的个数 m，
如果 m >= k，那么我们只需要对这 k 个负数取反，就可以得到最大的数组和；
如果 m < k，我们结合具体例子讨论，如下图所示，m = 4，
将所有的负数取反后，操作数剩下 k - m 次， 为了得到最大的数组和，我们只需要考虑如何操作取反后数组的最小值：
- 如果 k - m 为偶数，那么我们无需操作取反后数组的最小值，因为负负得正，数组和不变；
- 如果 k - m 为奇数，那么取反后数组的最小值取负值即可。
代码：
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
int minNum=INT_MAX,ret=0,n=nums.size(),m=0;
for(auto x:nums)
{
if(x<0) m++;
minNum=min(minNum,abs(x));//找出绝对值最小的数
}
if(m>k)//负数的个数大于k，反转前k小负数
{
sort(nums.begin(),nums.end());
for(int i=0;i<k;i++)
ret+= -nums[i];
for(int i=k;i<n;i++)
ret+=nums[i];
}
else//负数的个数小于等于k，有的数字被多次反转
{
for(auto x:nums)
ret+=abs(x);//反转所有负数
if((k-m)%2)//有的数被反转奇数次
{
ret-=minNum*2;
}
}
return ret;
}
};按身高排序（田忌赛马的预备）
2418. 按身高排序 - 力扣（LeetCode）https://leetcode.cn/problems/sort-the-people/description/
题解：
这道题有两种方法：
方法一：
用 pair 或者 struct 创建一个二元组，二元组的内容为姓名和对应的身高，将所有的二元组放入数组中，再对数组根据身高排序，排序后按照顺序把名字提取出来即可。
或者用哈希表，定义 map< int, string > hash，把身高和姓名放进哈希表中，再根据身高排序即可。
方法二：
因为姓名、身高和下标是一一对应的关系，如果只是对身高排序，身高和下标原本的对应关系就被打乱了，就无法根据身高的下标找到对应的姓名了。
如图所示，原本 165 、John 对应 1 号下标，只对身高排序后，下标为 1 的身高变为 170，John 再次根据下标 1 去找自己的身高时，身高变成 170 了。
为了保留身高、姓名和下标的对应关系， 我们可以重开一个数组 tmp，tmp 存的是身高数组的下标，新建一个排序规则，根据身高对下标排序，但不改变身高数组。
如下图，由于下标为 1 的身高165 小于 下标为 2 的身高 170，所以交换 tmp 中元素 1 和 2 的位置，tmp 排序后的最终顺序为 [ 0, 2, 1 ]，然后遍历 tmp 数组，height[ tmp[0] ] 就是 Mary，height[ tmp[1] ] 就是 Emma，height[ tmp[2] ] 就是 John。
代码：
方法一：
class Solution {
public:
struct person
{
string name;
int height;
}p[1010];
vector<string> sortPeople(vector<string>& names, vector<int>& heights)
{
int n=names.size();
for(int i=0;i<n;i++)
{
p[i].name=names[i];
p[i].height=heights[i];
}
sort(p,p+n,[](const struct person a,const struct person b)
{ return a.height>b.height; });
for(int i=0;i<n;i++)
{
names[i]=p[i].name;
}
return names;
}
};方法二：
class Solution {
public:
vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
int n=names.size();
vector<int> tmp(n);
for(int i=0;i<n;i++)
{
tmp[i]=i;//初始化
}
sort(tmp.begin(),tmp.end(),[&](int a,int b)
{ return heights[a]>heights[b]; });
vector<string> ret;
for(int i=0;i<n;i++)
{
ret.push_back(names[tmp[i]]);
}
return ret;
}
};优势洗牌（田忌赛马）
870. 优势洗牌 - 力扣（LeetCode）https://leetcode.cn/problems/advantage-shuffle/description/
题解：
我们对 nums1 和 nums2 排升序，以示例二为例，排序后 nums1 = [ 8, 12, 24, 32 ] ，nums2 = [ 11, 13, 25, 32 ]，我们 用 i 遍历 nums1 ，用 left 指向 nums2 的较小数，right 指向 nums2 的较大数：
- 如果 nums1[ i ] > nums2[ left ] ，说明 nums1[ i ] 有优势，i++，left++，去匹配下一对优势数；
- 如果 nums1[ i ] <= nums2[ left ]，说明该数没有优势，没有优势的数应该去拖累 nums2 的较大数，即 nums1[ i ] 和 nums2[ right ] 匹配，然后 i++，right -- . 因为 nums2[ left ] 后面的数更大，nums1[ i ] 更没有优势了，继续匹配还不如去拖累较大数。
为了不打乱nums2 的下标和数字的相对位置，在排序 nums2 时，用了 按身高排序的 排序方法，即只排序下标。
代码：
class Solution {
public:
vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
int n=nums1.size();
vector<int> index(n);
for(int i=0;i<n;i++)
index[i]=i;
sort(nums1.begin(),nums1.end());//排升序
sort(index.begin(),index.end(),[&](const int a,const int b)
{
return nums2[a]<nums2[b];
});
vector<int> ret(n);
int left=0,right=n-1;
for(auto x:nums1)
{
if(x>nums2[index[left]])
ret[index[left++]]=x;
else
ret[index[right--]]=x;
}
return ret;
}
};最长回文串
409. 最长回文串 - 力扣（LeetCode）https://leetcode.cn/problems/longest-palindrome/description/
题解：
为了得到回文串，就需要让字符串对称轴左右两侧的字母一一对应。
从下图可以看出，
- 如果回文串的长度为偶数，则每个字母的个数为偶数；
- 如果回文串的长度为奇数，则除了对称轴上的字母的个数为奇数之外，其余字母的个数为偶数。
统计提供的字符串 s 的每个字母出现的次数，
- 如果某字母出现的次数为偶数，说明这个字母可以直接加入回文串；
- 如果某字母出现的次数为奇数，为了得到最长的回文串， 只放入偶数个该字母，且这个偶数要尽可能大。
上述过程得到的回文串的长度为偶数，我们可以考虑一下对称轴上是否可以放一个字母，这里有一个小巧思，
- 如果得到的回文串的长度 == s 的长度，说明 s 中每个字母出现的次数都是偶数，已经没有多余的字母可以让我们放在对称轴上了；
- 如果得到的回文串的长度 < s 的长度，说明 s 中至少存在一个字母出现的次数为奇数，我们只需要让个数为奇数个的这个字母放在对称轴上，放一个就可以了，最后让回文串的长度 +1。
代码：
class Solution {
public:
int longestPalindrome(string s) {
int ret=0;
vector<int> count(256);
for(auto x:s)
count[x]++;
for(auto x:count)
{
ret+=(x/2*2);
}
return ret<s.size()?ret+1:ret;
}
};增减字符串匹配
942. 增减字符串匹配 - 力扣（LeetCode）https://leetcode.cn/problems/di-string-match/description/
题解：
定义两个指针 left 和 right，left 初始化为 0，right 初始化为 1，用 i 遍历字符串 s，将结果存在数组 ret 中：
- 如果 s[ i ] == ' I '，说明 ret[ i+1 ] > ret[ i ] ，即上升趋势，如果 ret[ i ] 的数字选得很大，上升的趋势很快，若后面出现连续的上升趋势，剩下的数字可能没办法满足上升的需求了，所以需要选择比较小的数字，减缓上升的趋势，而 left 指向的就是比较小的数，故 ret[ i ] = left，left++，指向下一个数；
- 如果 s[ i ] == ' D '，说明 ret[ i+1 ] < ret[ i ] ，即下降趋势，如果 ret[ i ] 的数字选得很小，下降的趋势很快，若后面出现连续的下降趋势，剩下的数字可能没办法满足下降的需求了，所以需要选择比较大的数字，减缓下降的趋势，而 right 指向的就是比较小的数，故 ret[ i ] = right，right --，指向下一个数；
- 因为 s 的长度为 n，而我们需要排 n+1 个数，最后 left 和 right 一定会相遇，指向同一个数，把这个数放在数组最后即可。
代码：
class Solution {
public:
vector<int> diStringMatch(string s) {
int n=s.size();
vector<int> ret;
int left=0,right=n;
for(int i=0;i<n;i++)
{
if(s[i]=='I')
{
ret.push_back(left); left++;
}
else
{
ret.push_back(right); right--;
}
}
ret.push_back(left);
return ret;
}
};分发饼干（田忌赛马）
455. 分发饼干 - 力扣（LeetCode）https://leetcode.cn/problems/assign-cookies/description/
题解：
和田忌赛马的思路大同小异，对胃口 g 和饼干 s 排序，用 i 遍历 g，用 j 遍历 s，
- 如果 g[ i ] > s[ j ] ，说明当前饼干不符合该小孩的胃口，后面的小孩的胃口就更不符合了，直接舍弃该饼干，即 j++；
- 如果 g[ i ] <= s[ j ]，说明当前饼干符合该小孩的胃口，该饼干直接给该小孩即可，即 i++，j++.
代码：
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
int ret=0; int n1=g.size(),n2=s.size();
sort(g.begin(),g.end());//排升序
sort(s.begin(),s.end());//排升序
int i=0,j=0;
while(i<n1 && j<n2)
{
if(g[i]>s[j]) j++;
else
{
i++; j++; ret++;
}
}
return ret;
}
};最优除法
553. 最优除法 - 力扣（LeetCode）https://leetcode.cn/problems/optimal-division/description/
题解：
加括号就是为了尽可能地把除数转为被除数，把放在分母的数放到分子上。
代码：
class Solution {
public:
string optimalDivision(vector<int>& nums) {
string ret;
ret+=to_string(nums[0]);
int n=nums.size();
if(n==2)
ret+="/"+to_string(nums[1]);
else if(n>2)
{
ret+="/("+to_string(nums[1]);
for(int i=2;i<n;i++)
{
ret+="/"+to_string(nums[i]);
}
ret+=")";
}
return ret;
}
};