564. 寻找最近的回文数
题目描述
输入一个字符串 n，它表示一个正整数，没有前导零。
找一个回文整数，使它与 n 所表示的数之差的绝对值尽可能小。回文整数是指十进制写法正读反读都一样的非负整数，0 也算。答案不能是 n 本身。
如果有两个回文数与 n 的距离相同，返回较小的那个。结果同样以不含前导零的字符串形式返回。
示例 1
输入：n = "123" 输出："121"
解释：离 123 最近的回文数是 121，相差 2。
示例 2
输入：n = "1" 输出："0"
解释：0 和 2 与 1 的距离都是 1，取较小的 0。
数据范围
1 <= n.length <= 18n只由数字组成。n没有前导零。n表示的整数在[1, 10^18 - 1]范围内。
解题思路
回文数由前半部分完全决定，要离 n 近，前半部分就应该和 n 的前半部分 prefix 尽量接近。所以只需把 prefix-1、prefix、prefix+1 三个数分别镜像成回文。若前半加减 1 后位数变了，答案会变成位数不同的回文，这类情况由两个边界候选 99…9（m-1 位）和 10…01（m+1 位）覆盖。最后删掉 n 本身，在至多 5 个候选里按（距离，数值）取最小。
为什么正确
与 n 最近的回文一定在这 5 个候选之中：同位数的回文里，前半部分越接近 prefix 越接近 n；跨位数的最近回文只能是 99…9 或 10…01。
复杂度分析
时间 O(m)，m 为位数；额外空间 O(m)。
易错点
只镜像 prefix 本身是不够的：n 若已是回文必须换别的，且 99、1000 这类数的最近回文位数不同。还要记得删除 n 本身，并在距离相同时取较小值。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def nearestPalindromic(self, n: str) -> str:
m = len(n)
cands = {10 ** m + 1, 10 ** (m - 1) - 1}
prefix = int(n[:(m + 1) // 2])
for p in (prefix - 1, prefix, prefix + 1):
s = str(p)
if len(s) == (m + 1) // 2:
cands.add(int(s + s[::-1][m % 2:]))
x = int(n)
cands.discard(x)
return str(min(cands, key=lambda c: (abs(c - x), c)))class Solution {
public String nearestPalindromic(String n) {
int m = n.length();
long p10 = 1;
for (int i = 0; i < m - 1; i++) p10 *= 10;
TreeSet<Long> cands = new TreeSet<>(List.of(p10 * 10 + 1, p10 - 1));
long prefix = Long.parseLong(n.substring(0, (m + 1) / 2));
for (long p : new long[]{prefix - 1, prefix, prefix + 1}) {
String s = Long.toString(p);
if (s.length() == (m + 1) / 2) {
String r = new StringBuilder(s).reverse().toString();
cands.add(Long.parseLong(s + r.substring(m % 2)));
}
}
long x = Long.parseLong(n);
cands.remove(x);
long best = -1;
for (long c : cands) {
if (best == -1 || Math.abs(c - x) < Math.abs(best - x)) best = c;
}
return Long.toString(best);
}
}class Solution {
public:
string nearestPalindromic(string n) {
int m = n.size();
long long p10 = 1;
for (int i = 0; i < m - 1; i++) p10 *= 10;
set<long long> cands = {p10 * 10 + 1, p10 - 1};
long long prefix = stoll(n.substr(0, (m + 1) / 2));
for (long long p : {prefix - 1, prefix, prefix + 1}) {
string s = to_string(p);
if ((int)s.size() == (m + 1) / 2) {
string r(s.rbegin(), s.rend());
cands.insert(stoll(s + r.substr(m % 2)));
}
}
long long x = stoll(n);
cands.erase(x);
long long best = -1;
for (long long c : cands) {
if (best == -1 || llabs(c - x) < llabs(best - x)) best = c;
}
return to_string(best);
}
};func nearestPalindromic(n string) string {
m := len(n)
p10 := int64(1)
for i := 0; i < m-1; i++ {
p10 *= 10
}
cands := map[int64]bool{p10*10 + 1: true, p10 - 1: true}
prefix, _ := strconv.ParseInt(n[:(m+1)/2], 10, 64)
for _, p := range []int64{prefix - 1, prefix, prefix + 1} {
s := strconv.FormatInt(p, 10)
if len(s) != (m+1)/2 {
continue
}
r := []byte(s)
for i, j := 0, len(r)-1; i < j; i, j = i+1, j-1 {
r[i], r[j] = r[j], r[i]
}
v, _ := strconv.ParseInt(s+string(r[m%2:]), 10, 64)
cands[v] = true
}
x, _ := strconv.ParseInt(n, 10, 64)
delete(cands, x)
abs := func(a int64) int64 {
if a < 0 {
return -a
}
return a
}
best := int64(-1)
for c := range cands {
if best == -1 || abs(c-x) < abs(best-x) || (abs(c-x) == abs(best-x) && c < best) {
best = c
}
}
return strconv.FormatInt(best, 10)
}var nearestPalindromic = function(n) {
const m = n.length;
const cands = new Set([10n ** BigInt(m) + 1n, 10n ** BigInt(m - 1) - 1n]);
const prefix = BigInt(n.slice(0, Math.floor((m + 1) / 2)));
for (const p of [prefix - 1n, prefix, prefix + 1n]) {
const s = p.toString();
if (s.length === Math.floor((m + 1) / 2)) {
cands.add(BigInt(s + [...s].reverse().join('').slice(m % 2)));
}
}
const x = BigInt(n);
cands.delete(x);
const abs = a => a < 0n ? -a : a;
let best = -1n;
for (const c of cands) {
if (best === -1n || abs(c - x) < abs(best - x) || (abs(c - x) === abs(best - x) && c < best)) best = c;
}
return best.toString();
};function nearestPalindromic(n: string): string {
const m = n.length;
const cands = new Set<bigint>([10n ** BigInt(m) + 1n, 10n ** BigInt(m - 1) - 1n]);
const prefix = BigInt(n.slice(0, Math.floor((m + 1) / 2)));
for (const p of [prefix - 1n, prefix, prefix + 1n]) {
const s = p.toString();
if (s.length === Math.floor((m + 1) / 2)) {
cands.add(BigInt(s + [...s].reverse().join('').slice(m % 2)));
}
}
const x = BigInt(n);
cands.delete(x);
const abs = (a: bigint): bigint => a < 0n ? -a : a;
let best = -1n;
for (const c of cands) {
if (best === -1n || abs(c - x) < abs(best - x) || (abs(c - x) === abs(best - x) && c < best)) best = c;
}
return best.toString();
}