目录

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;elseret[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;}
};