LC 564. 寻找最近的回文数

题目描述

这是 LeetCode 上的 564. 寻找最近的回文数 ，难度为 困难。

给定一个表示整数的字符串 $n$ ，返回与它最近的回文整数（不包括自身）。如果不止一个，返回较小的那个。

“最近的”定义为两个整数差的绝对值最小。

示例 1:

1
2
3
输入: n = "123"

输出: "121"

示例 2:
1
2
3
4
5
输入: n = "1"

输出: "0"

解释: 0 和 2是最近的回文，但我们返回最小的，也就是 0。

提示:

  • $1 <= n.length <= 18$
  • $n$ 只由数字组成
  • $n$ 不含前导 $0$
  • $n$ 代表在 $[1, 10^{18} - 1]$ 范围内的整数

上下界分析 + 边界处理

对于任意字符串数值 $s$ 而言（令其长度为 $n$），先考虑如何找到「第一个比其大」和「第一个比其小」的回文串数值（上下界）。

由于是找「最近」的数值，因此一个自然的想法是优先修改低位数字，但由于回文串本身的对称性质，每个「低位」的修改带来的副作用是需要同时修改对应的「高位」，因此一个真正可以修改的位置是（相对）中间的位置。

举个 🌰，对于长度为奇数回文串数值 $abcde$，其中 $de$ 的修改会导致 $ab$ 同步修改，因此最近一个可以修改的低位是 $c$；对于长度为偶数的回文串数值 $abcd$ 而言，其中 $d$ 的修改会导致 $a$ 同步修改，因此最近一个可以修改的位置是 $bc$。

当对目标位置进行修改后，其余位置的数值可由回文串性质唯一确定，因此只需要找到可修改位置相邻数值即可。

例如对于 $abcde$ 来说，最近的回文数值的前三位可能是 $abc$、$abc+1$ 和 $abc-1$ 三者之一，其他位置的数值随着前三位的确定而唯一确定。

上述分析对于一般情况成立，而边界情况是指 $abc + 1$ 和 $abc - 1$ 导致整体长度发生变化，即 $abc=999$ 和 $abc=100$ 的情况，此时直接套用上述方法得到的值分别为 $1000001$ 和 $999$，但真实最近的值为 $100001$ 和 $9999$。

展开来说就是：对于 $abc = 999$（对应原串为 $999xx$ 的情况）而言，按照上述逻辑得到的是 $1000$，进行回文补充后得到 $1000001$（事实上应该是 $100001$ 更优）；对于 $abc = 100$（对应原串为 $100xx$ 的情况）而言，按照上述逻辑得到是 $99$，进行回文补充后得到 $999$（事实上应该是 $9999$ 更优）。

因此对于长度为 $n$ 的数值，值考虑枚举前一半数的三种情况（前一半数不变，前一半数加一或减一）可能会错过最优解，我们需要将与长度相关的边界值也纳入考虑，即将「长度为 $n - 1$ 的回文串最大值（$99…99$）」和「长度为 $n + 1$ 的回文串最小值（$10…01$）」也纳入考虑，也就是对应的 $10^{n - 1} - 1$ 和 $10^n + 1$ 也纳入考虑，最后从上述 $5$ 个值中选绝对差值最小的作为答案。

一些细节：在枚举完前一半数后，我们需要根据原串长度的奇偶性来决定，如何生成后一半数，从而确保构建的回文串长度仍和原串长度相等。
即对于原串长度 $n$ 为奇数的 $abcde$ 而言，在处理完 $abc$ 之后，生成后一半数时，只需要根据前两位 $ab$ 生成对应的 $ba$，而无须处理中间字符 $c$；而对于原串长度 $n$ 为偶数的 $abcd$ 而言，在处理完 $ab$ 之后，生成另外一般数值需要根据整一个 $ab$ 来生成 $ba$，没有中间字符需要被跳过。

另外由于数据范围为 $[1, 10^{18} - 1]$，而 $999999999999999999$ 也属于合法输入（$2022/03/03$ 目前样例里还没有这个数据），因此我们需要考虑 getNum 爆 long 的问题，一个比直接特判更好做法是：利用答案长度必然不会超过 $19$ 来做处理，对于长度超过 $19$ 的直接当成 $-1$ 来处理，由于个位数均为回文，$-1$ 注定不会成为答案。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public String nearestPalindromic(String s) {
        int n = s.length();
        long cur = Long.parseLong(s);
        Set<Long> set = new HashSet<>();
        set.add((long) Math.pow(10, (n - 1)) - 1);
        set.add((long) Math.pow(10, n) + 1);
        long t = Long.parseLong(s.substring(0, (n + 1) / 2));
        for (long i = t - 1; i <= t + 1; i++) {
            long temp = getNum(i, n % 2 == 0);
            if (temp != cur) set.add(temp);
        }
        long ans = -1;
        for (long i : set) {
            if (ans == -1) ans = i;
            else if (Math.abs(i - cur) < Math.abs(ans - cur)) ans = i;
            else if (Math.abs(i - cur) == Math.abs(ans - cur) && i < ans) ans = i;
        }
        return String.valueOf(ans);
    }
    long getNum(long k, boolean isEven) {
        StringBuilder sb = new StringBuilder();
        sb.append(k);
        int n = sb.length(), idx = isEven ? n - 1 : n - 2;
        while (idx >= 0) sb.append(sb.charAt(idx--));
        String str = sb.toString();
        return str.length() > 19 ? -1 : Long.parseLong(str);
    }
}

  • 时间复杂度：令 $N$ 为字符串 s 所代指的数值，$n$ 为字符串 s 的长度，复杂度为 $O(\log{N})$ 或者说是 $O(n)$
  • 空间复杂度：$O(1)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.564 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。