Leetcode Link: 6166. 最大回文数字 - 力扣（LeetCode）
题目
解法一
个人思路：
假设我们知道所有成对出现的数字，valid = [[数字1, 数字1出现的对数], [数字2, 数字2出现的对数]] 和最大的单独出现的数字 one。那么在一般情况下我们拼接的方法就是先放 one，然后在 one 的两边放最小的成对数字，放完后再放次小的… 显然，如果没有 one，则可以直接放最小的成对数字在中间。
一个关键是怎么找到 valid 和 one。
找 valid: 接对输入的 num 进行计数，统计每个数字出现的次数，对出现次数大于 1 的数字出现次数对 2 整除即可。
找到成对的数字后，我们需要把余数再更新回去，譬如”3339911”，取走两个 3 后剩下的那个 3 就是 one。
找one: 继valid之后，我们找到出现次数为1的最大数字即可，需要提前初始化为一个取不到的值。
后面就是对 valid 排序，根据 one 是否存在初始化一个 res，然后不断拼接 valid 里的数字即可。
错误分析
当 one 为空，
valid = [(0, n)]时 (如num="0000")，我们需要返回的是"0"，而不是""。 所以当 valid 里只有一个成对的数字，且这个数字为 0 的时候，需要进行分类讨论
- one 存在，则返回
str (one)- one 不存在，返回
"0"
题解：
class Solution:
def largestPalindromic(self, num: str) -> str:
counter = Counter(num)
## 找成对出现的数字
valid = [] # [(数字, 该数字有多少对)]
for k in counter.keys():
v = int(counter[k])
if v > 1 and (v % 2 == 0 or v % 2 == 1):
valid.append([int(k), v//2])
counter[k] = v % 2
## 找单独出现或者剩下的数字
one = -float('inf')
for k in counter.keys():
v = int(counter[k])
if v == 1:
one = max(one, int(k))
## 重新排列所有有效的成对数字
valid = sorted(valid, key = lambda x: x[0])
## 有单独出现的数字就添加，没有就是空字符串
res = str(one) if one != -float('inf') else ""
# XXXX 错误出在这里 XXXX
# 开始直接返回了res, 遇到"00"会输出""，实际应该是"0"
if len(valid) == 1 and valid[-1][0] == 0:
return "0" if res == "" else res
# 由里向外成对拼接
for pairs in valid:
for _ in range(pairs[1]):
res = str(pairs[0]) + res + str(pairs[0])
return res解法二
思路：思路一我们是直接正面入手的，这里我们也可以从 0 到 9 在 num 中一个一个找。
相对解法1代码量小一些，之后后面的思路是一样的。
题解：
class Solution:
def largestPalindromic(self, num: str) -> str:
counter = Counter(num)
valid = []
one = -float('inf')
# 一个一个找
for i in range(10):
if str(i) in counter.keys():
if counter[str(i)] // 2 > 0: valid.append([i, counter[str(i)] // 2])
if counter[str(i)] % 2 > 0: one = i
res = "" if one == -float('inf') else str(one)
# 注意这里小心返回错误
if len(valid) == 1 and valid[0][0] == 0:
return '0' if res == '' else res
# 从里向外填写
for pair in valid:
for _ in range(pair[1]):
res = str(pair[0]) + res + str(pair[0])
return res