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;
}
};