贪心算法总结（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 %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]<=s[i+1]) ++i; //找到第一个下降趋势的
       if(i==m-1) return n;//可能直接走到头了
       //如果没有走到头，开始回退
       while(i-1>=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<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或者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);
    }
};