LeetCode 564. 寻找最近的回文数

2021-11-22 HGNULB 约 11 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 564. 寻找最近的回文数

题意分析

输入是一个用字符串表示的正整数 n，要求找出与它数值上最接近、并且本身是回文的另一个整数，结果同样以字符串返回。「另一个」是硬性要求：即使 n 自己就是回文，也不能把它当答案。

判定标准分两层：先比绝对差，绝对差相同时取数值更小的那个。这条平局规则是本题最容易被忽略的部分，它决定了很多用例的正确答案。

约束里最强的信号是长度上限 18 位。这个规模说明从 n 出发一格一格向两边试探是不可能的，答案必须被直接构造出来；同时 18 位数值超出 32 位范围，中间量必须用 64 位存。

边界集中在三处：n 只有一位时，答案是比它小一的那个数（"1" 对应 "0"）；n 形如 10…0 时答案会退到少一位的全 9；n 形如 9…9 时答案会涨到多一位的 10…01。

解法：前缀构造候选，逐个比较距离

核心思路

最朴素的想法是从 n 向左右同时扩散，每遇到一个数就判断是否回文，先命中的就是答案。正确但不可行：n 与最近回文的距离在最坏情况下能到 $10^{L/2}$ 量级，18 位输入下这是十亿级别的试探。

瓶颈在于「逐个试」。突破口是回文数的结构：一个 $L$ 位回文完全由它的前 $\lceil L/2 \rceil$ 位决定，后半段只是前半段的镜像。于是长度固定为 $L$ 的回文与它的前缀之间是一一对应、并且单调递增的关系——前缀越大，镜像出的回文越大。

既然单调，把 n 的前缀记作 $p$，那么所有 $L$ 位回文中离 n 最近的，只可能出自 $p-1$、$p$、$p+1$ 这三个前缀：更远的前缀镜像出的数一定比这三个更远。剩下的只有换位数的情况，而换位数时离 n 最近的必然是恰好少一位的最大回文 $10^{L-1}-1$ 和恰好多一位的最小回文 $10^{L}+1$。

这就给出了本题的不变量：答案一定落在这五个候选之内。把它们放进集合去重，剔除等于 n 的那个，再按「先比差值、后比大小」挑最优，就是完整算法。

解题步骤

先把字符串解析成 64 位整数 num，记下长度 len。之所以要转成数值，是因为距离比较是算术意义上的，字符串比较无法表达「差多少」。

一位数单独返回 num - 1。因为一位数的最近回文永远是相邻的那个更小数字，直接短路可以避免后面镜像逻辑处理零长度后半段。

把两个长度边界候选 $10^{L-1}-1$ 与 $10^{L}+1$ 先放进集合。它们是换位数时唯一可能的最优解，且在前缀退位（如 $p-1$ 少了一位）时充当兜底，漏掉就会错。

取前缀 $p = num / 10^{\lfloor L/2 \rfloor}$，对 $p-1$、$p$、$p+1$ 各做一次镜像并加入集合。除以 $10^{\lfloor L/2 \rfloor}$ 恰好砍掉后半段，留下决定整个回文的 $\lceil L/2 \rceil$ 位。

镜像时按长度奇偶决定从哪一位开始回抄：长度为奇数时中间位只出现一次，所以起点要再退一格，否则会把中心字符写两遍、长度多出 1。

遍历集合，跳过等于 num 的候选，用「差值更小」或「差值相等且数值更小」的条件更新答案。两个条件必须都写，只写前者会让平局的结果依赖集合的遍历顺序。

以 "1213" 走一遍：num = 1213，len = 4，不是一位数。先放入边界候选 $10^3-1 = 999$ 与 $10^4+1 = 10001$。前缀 $p = 1213 / 100 = 12$，半长 $\lceil 4/2 \rceil = 2$。镜像 $p-1 = 11$：左半 "11"，长度为偶数故从下标 1 开始回抄，得 "1111"；镜像 $p = 12$ 得 "1221"；镜像 $p+1 = 13$ 得 "1331"。集合为 ${999, 1111, 1221, 1331, 10001}$，其中没有等于 1213 的。逐个算差：$ 999-1213 = 214$、$ 1111-1213 = 102$、$ 1221-1213 = 8$、$ 1331-1213 = 118$、$ 10001-1213 = 8788$。最小差是 8，答案为 "1221"。

再看一个平局用例 "1000"：$p = 1000/100 = 10$，镜像 $p-1 = 9$ 时左半补零成 "09"，拼出的 990 已不是回文，但无妨——真正接住这一情况的是边界候选 999。集合为 ${990, 999, 1001, 1111, 10001}$，$ 999-1000 = 1$ 与 $ 1001-1000 = 1$ 打平，按数值更小取 "999"。

代码实现

class Solution {
    // 真正可能成为最近值的候选通常是 left-1、left、left+1 三个前半部分对应回文，再加上长度变化边界。
    public String nearestPalindromic(String n) {
        long num = Long.parseLong(n);
        if (num < 10) {
            return String.valueOf(num - 1);
        }

        int len = n.length();
        long half = num / pow10(len / 2);
        java.util.HashSet<Long> candidates = new java.util.HashSet<>();
        candidates.add(pow10(len - 1) - 1);
        candidates.add(pow10(len) + 1);

        for (long left = half - 1; left <= half + 1; left++) {
            if (left < 0) {
                continue;
            }
            candidates.add(Long.parseLong(mirror(left, len)));
        }

        long best = -1;
        long bestDiff = Long.MAX_VALUE;
        for (long c : candidates) {
            if (c == num) {
                continue;
            }
            long diff = Math.abs(c - num);
            if (best == -1 || diff < bestDiff || (diff == bestDiff && c < best)) {
                best = c;
                bestDiff = diff;
            }
        }
        return String.valueOf(best);
    }

    private String mirror(long leftPart, int len) {
        String left = String.valueOf(leftPart);
        int leftLen = (len + 1) / 2;
        while (left.length() < leftLen) {
            left = "0" + left;
        }
        if (left.length() > leftLen) {
            return String.valueOf(pow10(len) + 1);
        }

        StringBuilder sb = new StringBuilder(left);
        int start = leftLen - 1;
        if ((len & 1) == 1) {
            start--;
        }
        for (int i = start; i >= 0; i--) {
            sb.append(left.charAt(i));
        }
        return sb.toString();
    }

    private long pow10(int p) {
        long v = 1;
        for (int i = 0; i < p; i++) {
            v *= 10;
        }
        return v;
    }
}

func nearestPalindromic(n string) string {
    // 真正可能成为最近值的候选通常是 left-1、left、left+1 三个前半部分对应回文，再加上长度变化边界。
    num := parseInt564(n)
    if num < 10 {
        return intToString(num - 1)
    }

    length := len(n)
    half := num / pow106(length / 2)
    cands := make(map[int64]struct{})
    cands[pow106(length-1)-1] = struct{}{}
    cands[pow106(length)+1] = struct{}{}

    for left := half - 1; left <= half+1; left++ {
        if left >= 0 {
            cands[parseInt564(makePalindrome606(left, length))] = struct{}{}
        }
    }

    best := int64(-1)
    bestDiff := int64(-1)
    for c := range cands {
        if c == num {
            continue
        }
        diff := c - num
        if diff < 0 {
            diff = -diff
        }
        if best == -1 || diff < bestDiff || (diff == bestDiff && c < best) {
            best = c
            bestDiff = diff
        }
    }
    return intToString(best)
}

func makePalindrome606(left int64, length int) string {
    leftLen := (length + 1) / 2
    s := intToString(left)
    for len(s) < leftLen {
        s = "0" + s
    }
    if len(s) > leftLen {
        return intToString(pow106(length) + 1)
    }

    out := []byte(s)
    start := leftLen - 1
    if (length % 2) == 1 {
        start--
    }
    for i := start; i >= 0; i-- {
        out = append(out, s[i])
    }
    return string(out)
}

func parseInt564(s string) int64 {
    var v int64
    for i := 0; i < len(s); i++ {
        v = v*10 + int64(s[i]-'0')
    }
    return v
}

func pow106(p int) int64 {
    v := int64(1)
    for i := 0; i < p; i++ {
        v *= 10
    }
    return v
}

func intToString(v int64) string {
    if v == 0 {
        return "0"
    }
    buf := make([]byte, 0)
    for v > 0 {
        buf = append(buf, byte('0'+v%10))
        v /= 10
    }
    for i, j := 0, len(buf)-1; i < j; i, j = i+1, j-1 {
        buf[i], buf[j] = buf[j], buf[i]
    }
    return string(buf)
}

复杂度分析

时间复杂度：$O(L)$，$L$ 为字符串长度。候选个数是固定的 5 个，与输入规模无关；每个候选的镜像构造与解析都只扫一遍长度为 $L$ 的字符串，所以总量由字符串长度决定，与 n 的数值大小无关。

空间复杂度：$O(L)$，集合里始终只有常数个 64 位整数，真正占空间的是构造镜像时的字符缓冲区，长度为 $L$。

关键点总结

当答案空间巨大但答案本身有强结构时，正确的方向是「构造候选」而不是「搜索」。回文由前半段唯一决定，这一条把 $10^{18}$ 的搜索空间压成 5 个候选。

单调性是把候选集合裁到常数个的依据：同长度回文随前缀单调递增，所以最近的必在前缀 $\pm 1$ 的邻域内，更远的前缀不必看。

结构性问题要单独枚举「维度变化」的边界。位数减一和加一各自只有一个最优代表（全 9 与 $10^L+1$），漏掉它们的解法在 "1000"、"999" 这类用例上必错。

比较准则要显式建模成有序对：先差值后数值。凡是「距离最近，平局取小」的题都该这样写，否则结果会依赖遍历顺序。

面试视角：这题面试官看的不是代码量，而是你能否说清「为什么只有五个候选就够」。开口先给出这个不变量并简单论证单调性，再动手写镜像函数；直接闷头写字符串处理很容易陷进奇偶长度和前导零的细节里出不来。

易错点总结

错误写法：不排除 n 本身。"121" → 候选里 121 差值为 0 直接胜出，返回 "121"，而正确答案是 "111"。

错误写法：位数减一的边界候选写成 $10^{L}-1$ 而不是 $10^{L-1}-1$。"1000" → 少一位的 999 从未进入候选，返回 "1001"，正确答案是 "999"。

错误写法：只镜像前缀 $p$ 自己，不看 $p \pm 1$。"1221" → 唯一的同长度候选就是它自己且必须排除，只能退到边界候选返回 "999" 或 "10001"，正确答案是 "1111"。

错误写法：平局时用 diff <= bestDiff 无条件覆盖，或干脆不写平局分支。"1000" → 999 和 1001 差值都是 1，谁最后被遍历到谁获胜，在哈希集合遍历顺序不确定的语言里结果随机。

错误写法：用 32 位整数存中间量。长度为 18 的输入 → $10^{18}+1$ 这个上边界候选溢出成负数，比较时它会以极小值身份胜出，输出一个负数字符串。

错误写法：取前缀时除以 $10^{\lceil L/2 \rceil}$。"12345" → 本该留下 3 位前缀 123，却只剩 12，镜像出的是 4 位数，长度与原数对不上，同长度候选整体失效。

错误写法：镜像时不区分长度奇偶，一律从左半末位开始回抄。"12345" → 左半 "123" 回抄成 "123321"，比原数多了一位，中心的 3 被写了两遍。

错误写法：前缀减一后位数缩短却按字符串直接拼接，且不保留位数边界候选。"1000" 的前缀 10 减一得 9，补零成 "09" 拼出的 990 并不是回文；若把它当作合法回文参与比较，又恰好没有 999 兜底，就会输出一个非回文数。

错误写法：一位数不做特判又让镜像逻辑处理长度为 1 的输入时算错半长。"1" → 半长与回抄起点的计算会拼出空串或两位数，解析阶段直接抛异常。

相似题目

题目	难度	考察点
9. 回文数	简单	不借助字符串判定一个整数是否回文
1328. 破坏回文串	中等	改动一个字符使其不再回文且字典序最小
214. 最短回文串	困难	求最长回文前缀，用字符串匹配而非枚举