题目描述
这是 LeetCode 上的 564. 寻找最近的回文数 ，难度为 困难。
Tag : 「贪心」、「脑筋急转弯」
给定一个表示整数的字符串 nn ，返回与它最近的回文整数（不包括自身）。如果不止一个，返回较小的那个。
“最近的”定义为两个整数差的绝对值最小。
示例 1:
输入: n = "123" 输出: "121" 复制代码
示例 2:
输入: n = "1" 输出: "0" 解释: 0 和 2是最近的回文，但我们返回最小的，也就是 0。 复制代码
提示:
- 1 <= n.length <= 181<=n.length<=18
- nn 只由数字组成
- nn 不含前导 00
- nn 代表在 [1, 10^{18} - 1][1,1018−1] 范围内的整数
上下界分析 + 边界处理
对于任意字符串数值 ss 而言（令其长度为 nn），先考虑如何找到「第一个比其大」和「第一个比其小」的回文串数值（上下界）。
由于是找「最近」的数值，因此一个自然的想法是优先修改低位数字，但由于回文串本身的对称性质，每个「低位」的修改带来的副作用是需要同时修改对应的「高位」，因此一个真正可以修改的位置是（相对）中间的位置。
举个 🌰，对于长度为奇数回文串数值 abcdeabcde，其中 dede 的修改会导致 abab 同步修改，因此最近一个可以修改的低位是 cc；对于长度为偶数的回文串数值 abcdabcd 而言，其中 dd 的修改会导致 aa 同步修改，因此最近一个可以修改的位置是 bcbc。
当对目标位置进行修改后，其余位置的数值可由回文串性质唯一确定，因此只需要找到可修改位置相邻数值即可。
例如对于 abcdeabcde 来说，最近的回文数值的前三位可能是 abcabc、abc+1abc+1 和 abc-1abc−1 三者之一，其他位置的数值随着前三位的确定而唯一确定。
上述分析对于一般情况成立，而边界情况是指 abc + 1abc+1 和 abc - 1abc−1 导致整体长度发生变化，即 abc=999abc=999 和 abc=100abc=100 的情况，此时直接套用上述方法得到的值分别为 10000011000001 和 999999，但真实最近的值为 100001100001 和 99999999。
展开来说就是：对于 abc = 999abc=999（对应原串为 999xx999xx 的情况）而言，按照上述逻辑得到的是 10001000，进行回文补充后得到 10000011000001（事实上应该是 100001100001 更优）；对于 abc = 100abc=100（对应原串为 100xx100xx 的情况）而言，按照上述逻辑得到是 9999，进行回文补充后得到 999999（事实上应该是 99999999 更优）。
因此对于长度为 nn 的数值，值考虑枚举前一半数的三种情况（前一半数不变，前一半数加一或减一）可能会过错最优解，我们需要将与长度相关的边界值也纳入考虑，即将「长度为 n - 1n−1 的回文串最大值（99...9999...99）」和「长度为 n + 1n+1 的回文串最小值（10...0110...01）」也纳入考虑，也就是对应的 10^{n - 1} - 110n−1−1 和 10^n + 110n+1 也纳入考虑。然后从上述 55 个值中选绝对差值最小的作为答案。
一些细节：在枚举完前一半数后，我们需要根据原串长度的奇偶性来决定，如何生成后一半数，从而确保构建的回文串长度仍和原串长度相等。
即对于原串长度 nn 为奇数的 abcdeabcde 而言，在处理完 abcabc 之后，生成后一半数时，只需要根据前两位 abab 生成对应的 baba，而无须处理中间字符 cc；而对于原串长度 nn 为偶数的 abcdabcd 而言，在处理完 abab 之后，生成另外一般数值需要根据整一个 abab 来生成 baba，没有中间字符需要被跳过。
代码：
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 = -1; if (n % 2 == 0) temp = getNum(i, true); else temp = getNum(i, false); 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 idx = isEven ? sb.length() - 1 : sb.length() - 2; while (idx >= 0) sb.append(sb.charAt(idx--)); return Long.parseLong(sb.toString()); } } 复制代码
- 时间复杂度：O(\log{n})O(logn)
- 空间复杂度：O(1)O(1)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.564 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
