class Solution {
public:
string largestPalindromic(string num) {
}
};
2384. 最大回文数字
给你一个仅由数字（0 - 9）组成的字符串 num 。
请你找出能够使用 num 中数字形成的 最大回文 整数，并以字符串形式返回。该整数不含 前导零 。
注意：
num 中的所有数字，但你必须使用 至少 一个数字。
示例 1：
输入：num = "444947137" 输出："7449447" 解释： 从 "444947137" 中选用数字 "4449477"，可以形成回文整数 "7449447" 。 可以证明 "7449447" 是能够形成的最大回文整数。
示例 2：
输入：num = "00009" 输出："9" 解释： 可以证明 "9" 能够形成的最大回文整数。 注意返回的整数不应含前导零。
提示：
1 <= num.length <= 105num 由数字（0 - 9）组成原站题解
python3 解法, 执行用时: 68 ms, 内存消耗: 15.8 MB, 提交时间: 2022-11-18 15:01:56
class Solution:
def largestPalindromic(self, num: str) -> str:
digits = '0123456789'
cnt = Counter(num)
if cnt['0'] == len(num): # 特判最特殊的情况：num 全是 0
return "0"
s = ""
for d in digits[:0:-1]:
s += d * (cnt[d] // 2)
if s: # 如果填了数字，则可以填 0
s += '0' * (cnt['0'] // 2)
t = s[::-1]
for d in digits[::-1]:
if cnt[d] % 2: # 还可以填一个变成奇回文串
s += d
break
return s + t # 添加镜像部分
golang 解法, 执行用时: 8 ms, 内存消耗: 6.4 MB, 提交时间: 2022-11-18 15:00:32
func largestPalindromic(num string) string {
cnt := ['9' + 1]int{}
for _, d := range num {
cnt[d]++
}
if cnt['0'] == len(num) { // 特判最特殊的情况：num 全是 0
return "0"
}
s := []byte{}
for i := byte('9'); i > '0' || i == '0' && len(s) > 0; i-- { // 如果填了数字，则可以填 0
s = append(s, strings.Repeat(string(i), cnt[i]/2)...)
}
j := len(s) - 1
for i := byte('9'); i >= '0'; i-- {
if cnt[i]&1 > 0 { // 还可以填一个变成奇回文串
s = append(s, i)
break
}
}
for ; j >= 0; j-- { // 添加镜像部分
s = append(s, s[j])
}
return string(s)
}