贪心算法总结（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 diStringMatch(string s) { //如果是升 就把最小的放进去 如果是降 就把最大的放进去 int left=0,right=s.size(); vector 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(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=n) index=1; ret[index]=\'a\'+i; index+=2; } return ret; }};四、最优除法
553. 最优除法 - 力扣（LeetCode）
class Solution {public: string optimalDivision(vector& 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 %10 int monotoneIncreasingDigits(int n) { //根据贪心策略，首先第一步我们要找到第一个下降的数，然后让他-1 之后再把后面所有的数都变成9 //但是比如12345555123这种情况。就需要进行回退 回退到第一个5的位置然后再进行上面的操作 string s=to_string(n); int m=s.size(),i=0; while(i+1<n&&s[i]=0&&s[i]==s[i-1]) --i; --s[i]; //然后让后面的位置变成9 for(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 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& nums) { // 正难则反 //sum%3==0 //sum%3==1 x1 或者y1y2 //sum%3==2 x1x2或者y1 const 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); }};
