贪心算法总结（3）

一、最长回文串

409. 最长回文串 - 力扣（LeetCode）

class Solution {
public:int longestPalindrome(string s) {int hash[127]={0};for(char&ch:s) ++hash[ch];int ret=0;for(int&x:hash)  ret+=x/2*2; //技巧1 利用向下取整return ret<s.size()?ret+1:ret;}
};

二、增减字符串匹配

942. 增减字符串匹配 - 力扣（LeetCode）

class Solution {
public:vector<int> diStringMatch(string s) {//如果是升 就把最小的放进去  如果是降 就把最大的放进去int left=0,right=s.size();vector<int> ret;ret.reserve(s.size()+1);for(auto&ch:s) if(ch=='I') ret.emplace_back(left++);else ret.emplace_back(right--);ret.emplace_back(left);return ret;}
};

三、重构字符串

767. 重构字符串 - 力扣（LeetCode）

class Solution {
public:string reorganizeString(string s) {int hash[26]={0};int n=s.size(),maxcount=0,maxchar=' ';for(auto&ch:s)if(maxcount<++hash[ch-'a']) maxcount=hash[ch-'a'],maxchar=ch;//先处理最多的那个if(maxcount>(n+1)/2) return "";string ret(n,' ');int index=0;for(int i=0;i<maxcount;++i){ret[index]=maxchar;index+=2;}hash[maxchar-'a']=0;for(int i=0;i<26;++i)for(int j=0;j<hash[i];++j){if(index>=n) index=1;ret[index]='a'+i;index+=2;}return ret;}
};

四、最优除法

553. 最优除法 - 力扣（LeetCode）

class Solution {
public:string optimalDivision(vector<int>& nums) {int n=nums.size();if(n==1) return to_string(nums[0]);if(n==2) return to_string(nums[0])+"/"+to_string(nums[1]);string ret=to_string(nums[0])+"/("+to_string(nums[1]);for(int i=2;i<n;++i) ret+="/"+to_string(nums[i]);ret+=")";return ret;}
};

 五、单调递增的数字

738. 单调递增的数字 - 力扣（LeetCode）

class Solution {
public:
//要获取一个数的数位关系的时候 一般有两个技巧，第一个是变成字符串 第二个就是/10 %10int monotoneIncreasingDigits(int n) {//根据贪心策略，首先第一步我们要找到第一个下降的数，然后让他-1 之后再把后面所有的数都变成9//但是比如12345555123这种情况。就需要进行回退 回退到第一个5的位置然后再进行上面的操作string s=to_string(n);int m=s.size(),i=0;while(i+1<n&&s[i]<=s[i+1]) ++i; //找到第一个下降趋势的if(i==m-1) return n;//可能直接走到头了//如果没有走到头，开始回退while(i-1>=0&&s[i]==s[i-1]) --i;--s[i];//然后让后面的位置变成9for(int j=i+1;j<m;++j) s[j]='9';return stoi(s);}
};

六、坏了的计算机

991. 坏了的计算器 - 力扣（LeetCode）

class Solution {
public:int brokenCalc(int startValue, int target) {int ret=0;while(target>startValue) {if(target%2) ++target;else target/=2;++ret;} return ret+startValue-target;}
};

七、整数替换

397. 整数替换 - 力扣（LeetCode）

 解法1：递归+记忆化搜索

class Solution {
public:unordered_map<int,int> hash;int integerReplacement(int n) {return dfs(n);}int dfs(long n) //细节问题 容易溢出{//模拟 递归 记忆化搜索 if(hash.count(n)) return hash[n];if(n==1) return hash[1]=0;else if(n%2)  return hash[n]=1+min(dfs(n-1),dfs(n+1));else  return hash[n]=dfs(n/2)+1;}
};

解法2：贪心

class Solution {
public:int integerReplacement(int n) {int ret=0;while(n>1){if(n%2==0) n/=2,++ret;else{if(n==3) n=1;else if(n%4==1)  n/=2;else n=n/2+1;ret+=2;}}return ret;}
};

八、可被三数整除的最大和

1262. 可被三整除的最大和 - 力扣（LeetCode）

class Solution {
public:int maxSumDivThree(vector<int>& nums) {// 正难则反//sum%3==0  //sum%3==1     x1  或者y1y2//sum%3==2     x1x2或者y1const int INF=0x3f3f3f3f;int sum=0,x1=INF,x2=INF,y1=INF,y2=INF;for(auto&e:nums){sum+=e;if(e%3==1) {if(e<x1) x2=x1,x1=e;else if(e<x2) x2=e;}else if(e%3==2){if(e<y1) y2=y1,y1=e;else if(e<y2) y2=e;}}if(sum%3==0) return sum;else if(sum%3==1) return max(sum-x1,sum-y1-y2);else return max(sum-x1-x2,sum-y1);}
};