贪心算法（三）

目录

一、k次取反后最大化的数组和

二、优势洗牌

三、最长回文串 

四、增减字符串匹配

---

一、k次取反后最大化的数组和

k次取反后最大化的数组和

贪心策略：

解题代码： 

class Solution 
{
public:int largestSumAfterKNegations(vector<int>& nums, int k) {int m = 0;int min_elec = INT_MAX;for(auto& x:nums){if(x < 0)m++;min_elec = min(min_elec, abs(x));}sort(nums.begin(), nums.end());int ret = 0;if(m > k){for(int i = 0; i < nums.size(); i++){if(i < k){ret += -nums[i];continue;}ret += nums[i];}}else{for(auto& x : nums)ret += abs(x);if((k-m) % 2)ret -= 2*min_elec;}return ret;}
};

---

二、优势洗牌

优势洗牌

引例：田忌赛马 

田忌赛马的故事，我相信大家都知道。赛马的要求就是：上等马对上等马，中等马对中等马，下等马对下等马。因为齐王的上中下等马，都依次比田忌的上中下等马好一些，所以无论怎么比，田忌都无法获胜。

而孙膑给田忌出了个注意：田忌的下等马对齐王的上等马，中等马对下等马，上等马对中等马。这样，虽然齐王的上等马对田忌的下等马是场碾压式的胜利，可是另外两场，田忌都可以获胜。总的来说，就是田忌获胜了。

而我们这道题的贪心策略就可以从田忌赛马中获得启发。

贪心策略：

我们根据示例二来模拟一下解题过程。

我们需要先对数组进行排序。贪心策略对于田忌赛马的思想运用，就是对于同一位置来说，如果nums1的值小于nums2的值， 那么我们就拿nums1的值去匹配nums2中没有被匹配元素的最大元素。

解题代码：

class Solution 
{
public:vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {int m = nums1.size();sort(nums1.begin(), nums1.end());vector<int> index(m);for(int i = 0; i < m; i++)index[i] = i;sort(index.begin(), index.end(), [&](int i, int j){return nums2[i] < nums2[j];});vector<int> ret(m);int left = 0, right = m-1;for(auto& x:nums1){if(x <= nums2[index[left]]){ret[index[right]] = x;right--;}else if(x > nums2[index[left]]){ret[index[left]] = x;left++;}}return ret;}
};

---

三、最长回文串 

最长回文串

贪心策略：

1、先统计字符串s中，各个字符的个数。

2、如果某个字符的个数是偶数，那么所有的这个字符都可以去构成回文串。

3、如果有字符的个数是奇数，那么可以选择其中一个字符放在中间，如下：

注：设一个字符个数为x，那么该字符可以构成回文串的个数为 x / 2 * 2。 

解题代码： 

class Solution 
{
public:int longestPalindrome(string s) {int hash[127] = {0};for(auto& e:s)hash[e]++;int len = 0;for(int i = 0; i < 127; i++)len += hash[i] / 2 * 2;return len == s.size() ? len : len+1;}
};

---

四、增减字符串匹配

增减字符串匹配

贪心策略： 

1、当遇到 'I'，选择当前能够选择的最小的数。

2、当遇到 'D'，选择当前能够选择的最大的数。 

解题代码：

class Solution 
{
public:vector<int> diStringMatch(string s) {int n = s.size();vector<int> ret;int left = 0, right = n;for(auto& e : s){if(e == 'I')ret.push_back(left++);elseret.push_back(right--);}ret.push_back(left);return ret;}
};