LeetCode 564. 寻找最近的回文数

2021-11-22 HGNULB 约 8 分钟

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

分类

LeetCode CodeTop 困难未解决 2-5 字节

题目描述

✅ 564. 寻找最近的回文数

题意分析

找到与输入整数绝对差最小的另一个回文数，差值相同取数值较小者。输入自身必须排除。整数最多有 $18$ 位，可以用 long 或 int64 保存输入和候选，并通过回文的前半部分直接生成少量候选。

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

核心思路

[!blue]

设输入数值为 $N$，长度为 $L$，取前 $\lceil L/2\rceil$ 位作为前缀 $p$。相同长度的回文由这个前缀唯一决定：偶数长度镜像整个前缀，奇数长度镜像时跳过最后一位，因为它是中间位，只能出现一次。

同长度回文随前缀严格递增。若存在前缀小于 $p$ 的同长度回文，它们都小于 $N$，其中最大者由 $p-1$ 生成；若存在前缀大于 $p$ 的同长度回文，它们都大于 $N$，其中最小者由 $p+1$ 生成。更远的前缀只会让距离更大，所以同长度只需比较 $p-1$、$p$、$p+1$ 的镜像。镜像 $p$ 可能落在 $N$ 两侧，也可能等于 $N$，都先纳入候选再判断。

位数不同的候选只需保留两端：所有较短回文中，最大的为 $10^{L-1}-1$，即少一位的全九；所有较长回文中，最小的为 $10^L+1$，即首尾为一、其余为零。其他位数不同的回文离 $N$ 更远。

前缀减一后若位数变短，直接使用少一位的全九；加一后若位数变长，直接使用多一位的首尾一，避免按原长度镜像出错误位数。将至多五个候选去重并排除 $N$，依次比较绝对差，差相同时选更小值，即可得到答案。

解题步骤

用 $64$ 位整数解析输入。一位正整数直接返回减一：前一个数就是回文，距离已达到最小的 $1$，且同距时数值更小；输入为 $1$ 时返回 $0$。

加入 $10^{L-1}-1$ 和 $10^L+1$ 两个位数边界候选。

分别镜像三个相邻前缀，按奇偶长度处理中心位，并在前缀进退位时改用对应边界。

跳过与输入相同的候选，按“绝对差更小，或同差且数值更小”更新答案，最后转回字符串。

最大边界候选为 $10^{18}+1$，仍在有符号 $64$ 位整数范围内，候选之间的差值也不会溢出。

代码实现

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;

        // 前缀退位直接取少一位全九，避免前导零变成非回文数
        if (left.length() < leftLen) {
            return String.valueOf(pow10(len - 1) - 1);
        }

        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)
    // 前缀退位直接取少一位全九，避免前导零变成非回文数
    if len(s) < leftLen {
        return intToString(pow106(length-1) - 1)
    }
    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 为位数，固定数量的镜像构造与解析。

空间复杂度：$O(L)$，镜像字符缓冲，候选整数集合大小固定。

关键点总结

[!green]

同长度邻居与跨位数边界要一起比较。

哈希集合遍历顺序不影响明确的平局规则。

易错点总结

[!yellow]

不排除自身，会错误返回零距离的原数。

奇数长度把中位重复镜像，会多出一位。

缺少位数边界候选，会漏掉最接近的较短或较长回文。

相似题目

题目	难度	关联与区别
9. 回文数	简单	回文数的对称数位结构是基础，本题还需从原数前缀附近构造候选并处理位数边界。
866. 回文质数	中等	同样可以通过前半段镜像生成回文候选，原题再检查素性，本题按距离和较小值规则选择。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2021/leetcode-564

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！