回文构造

lc

lc2384

hash+贪心

trick: 对于回文串，可以先构造做左半部分，然后添加对称的右半部分来降低编码难度。

先统计数字出现次数

把非零大数字的偶数次半数拼左半部分，有非零左半才加零的偶数次半数

再塞一个最大奇数次数字当中间

最后镜像左半拼出最大回文数

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();

if(cnt[0]==n)return "0";
string left;

for(int i=9;i>0;--i){
for(int j=0;j<cnt[i]/2;j++)
left+='0'+i;
}
// 只有左边添加了大于'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;
}
};