LeetCode 题解工作台
最大回文数字
给你一个仅由数字（ 0 - 9 ）组成的字符串 num 。 请你找出能够使用 num 中数字形成的 最大回文 整数，并以字符串形式返回。该整数不含 前导零 。 注意： 你 无需 使用 num 中的所有数字，但你必须使用 至少 一个数字。 数字可以重新排序。 示例 1： 输入： num = "4449…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
用 数组记录每个数字出现的次数。 回文数字需要满足回文串中最多有一个数字出现了奇数次，因此我们先找最大的、出现了奇数次的数字 （也可能不存在），作为回文数字的中间数字，对应的 减 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个仅由数字（0 - 9）组成的字符串 num 。
请你找出能够使用 num 中数字形成的 最大回文 整数，并以字符串形式返回。该整数不含 前导零 。
注意：
- 你 无需 使用
num中的所有数字，但你必须使用 至少 一个数字。 - 数字可以重新排序。
示例 1：
输入：num = "444947137" 输出："7449447" 解释： 从 "444947137" 中选用数字 "4449477"，可以形成回文整数 "7449447" 。 可以证明 "7449447" 是能够形成的最大回文整数。
示例 2：
输入：num = "00009" 输出："9" 解释： 可以证明 "9" 能够形成的最大回文整数。 注意返回的整数不应含前导零。
提示：
1 <= num.length <= 105num由数字（0 - 9）组成
解题思路
方法一：统计 + 贪心
用 数组记录每个数字出现的次数。
回文数字需要满足回文串中最多有一个数字出现了奇数次，因此我们先找最大的、出现了奇数次的数字 （也可能不存在），作为回文数字的中间数字，对应的 减 。
接下来我们从回文数字中间，按数字从小到大的顺序，往左右两边扩散（也可以枚举回文串的右半部分，然后将右半部分反转，得到左半部分）。这样我们可以得到一个“可能”含有前导零的回文串。
我们去除回文串的前导零，若回文串为空，则返回“0”。否则返回该回文串。
时间复杂度 ，其中 为 的长度。
class Solution:
def largestPalindromic(self, num: str) -> str:
cnt = Counter(num)
ans = ''
for i in range(9, -1, -1):
v = str(i)
if cnt[v] % 2:
ans = v
cnt[v] -= 1
break
for i in range(10):
v = str(i)
if cnt[v]:
cnt[v] //= 2
s = cnt[v] * v
ans = s + ans + s
return ans.strip('0') or '0'
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can the candidate efficiently count the digits and form the largest possible palindrome?
- question_mark
Is the candidate aware of edge cases like leading zeroes or the structure of palindromes?
- question_mark
Does the candidate demonstrate an understanding of how to optimize the palindrome construction process?
常见陷阱
外企场景- error
Not handling the case where digits are not paired properly, leading to an invalid palindrome.
- error
Overlooking the possibility of leading zeroes in the final result.
- error
Failing to maximize the palindrome size by not greedily selecting the largest available digits.
进阶变体
外企场景- arrow_right_alt
Form a palindrome from a string of digits with constraints on the number of allowed digits.
- arrow_right_alt
Allow the use of a subset of digits for palindrome formation.
- arrow_right_alt
Form a palindrome where the middle digit must be the smallest possible digit.