[回文串][贪心]leetcode6166：最大回文数字(medium)

题目：

---

思路：

思路：贪心

• 对于回文串最常规的做法是只用考虑单独一半，另一半做镜像还原这样来降低编码复杂度。
• 所以我们先构造回文串的左半部分，优先将大数字放在前面。若前面添加了大于 0 的大数字，然后再中间添加一半 0 即可，由于需要将回文串的数字最大，因此可以在最中间添加一个最大数字，最终将右半部分补齐。

---

代码如下：

class Solution {
public:
    // 对于回文串，先构造做左半部分，然后添加对称的右半部分来降低编码难度。
    string largestPalindromic(string s) {
        int cnt[10];memset(cnt,0,sizeof cnt);
        for(char c:s)cnt[c-'0']++;
        int n=s.size();
        // 特判全 0 的情况
        if(cnt[0]==n)return "0";
        string left;
        // 先将大数字添加到最左边，只用考虑添加偶数个一半的数字"i"
        for(int i=9;i>0;--i){
            for(int j=0;j<cnt[i]/2;j++)
                left+='0'+i;
        }
        // 主要是处理"00009"这种情况的。只有左边添加了大于'0'的数字才能在中间添加偶数个'0'
        if(left.size()){
            for(int j=0;j<cnt[0]/2;++j)
                left+='0';
        }
        // 记录前面对称部分的最后一个下标
        int j=left.size()-1;
        // 将数量为奇数的最大一个数字，添加在最中间
        for(int i=9;i>=0;i--)
            if(cnt[i]&1){
                left+='0'+i;
                break;
            }
        // 将右半部分补齐
        for(;j>=0;j--){
            left+=left[j];
        }
        return left;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35