564. 寻找最近的回文数 564. Find the Closest Palindrome

[Shellbye]

题目

给定一个整数 n ，你需要找到与它最近的回文数（不包括自身）。 “最近的”定义为两个整数差的绝对值最小。

示例 1:

输入: "123" 输出: "121"

注意:

n 是由字符串表示的正整数，其长度不超过18。 如果有多个结果，返回最小的那个。

初步分析

如果这个题目教会了我什么，那一定是“认真审题”。其中有三个点是我一开始没有注意到，以至于我走了很多弯路，浪费了不少精力，现在我把它们罗列出来，避免大家也走弯路：

1. 不包括自身
2. “最近的”定义为两个整数差的绝对值最小
3. 如果有多个结果，返回最小的那个

现在回顾这三个限定条件，才发现这才是题目的真正的要求。为什么呢？因为其实找到一个数（12345）附近的回文数是比较容易的，最简单的办法就是把高位部分折叠到低位部分（12321），或者反过来（54345）。你甚至可以随便写一个回文数（11111），这也算是一个答案，因为“附近”的定义是模糊的，我们可以狡辩11111也在12345附近嘛。所以题目加了以上三个限定条件，把“最近的”进行了精确的定义，那就是差值绝对值最小，并且明确了不能是自己（差值为0）。这样一来，对于每一个输入，这个题目就是有唯一正确输出的了。

反转高位 or 反转低位？

经过上面的初步分析，我们在明确了题意的情况下，也有了一定的思路。首先要找回文数肯定需要把一半的数反转到另一半，然后比较大小，最后输出最近且最小的。那么关于反转这块，是反转高位还是反转低位呢？这个可能是这个题目里最容易的一部分了。对于任意数字abcxy（a不等于y，b不等于x），反转低位xy之后的数yxcxy与原数的距离是肯定大于等于高位ab之后的数字abcba与原数的距离（绝对值）的，因为有公式如下

abcba - abcxy = | ba - xy | < 100 < 11000 < | yx000 - ab000 | = yxcxy - abcxy

所以我们需要分析的情形就少了一半，开心（😄）。

反转的具体位数

确定反转高位之后，还有一个需要注意的点，就是要反转几位，这个也不是很复杂，就是需要区分一下输入的数字的长度是奇数还是偶数即可。之所以要做这个区分，是因为奇数长度和偶数长度他们的结果形式是不一样的，分别是abcba和abccba，从结果形式我们可以看出其中参与反转的高位数目也是不一样，奇数长度不包含中间数（c），而偶数长度则是刚好一半。

寻找绝对值最小

从这里开始，题目就进入深水区了。通过我们上面的反转，找到了一个回文数，可是就一个候选值啊，哪里来的绝对值最小？说明还有其他的回文数隐藏在各个角落：

比如1999，按上面的策略，找到的应该是1991，但是其实有一个距离更近的数2002，才是答案； 比如9900，按上面的策略，找到的应该是9999，但是其实有一个距离更近的数9889，才是答案；

通过观察上面两种情况（其实也是通过递交答案没通过才发现的😫），我们发现一个特点，它们都是在拿到高位之后，分别对高位进行了+1、-1操作之后才反转的。于是又得到了新的回文数候选值。把上面的直接反转高位认为是高位进行了+0操作的话，刚好可以构建一个-1到+1的循环！

初步代码

有了上面的一些分析为基础，我们可以初步写出如下代码了

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Solution {
    public String nearestPalindromic(String n) {
        int half = n.length() / 2 + n.length() % 2; // 统一奇偶
        long highVal0 = Long.parseLong(n.substring(0, half)); // 获取高位的值，用来加减1
        Set<Long> candidates = new HashSet<>();// 存储所有候选值，目前最多三个
        for (int i = -1; i <= 1; i++) { // 高位的值分别加 `-1`，`0`，`1`
            String pre = String.valueOf(highVal0 + i);
            String post = ""; // 反转之后的值，也就是新的后半部分
            if (n.length() % 2 == 0) { // 偶数，前半部分整体反转
                post = new StringBuffer(pre).reverse().toString();
            } else { // 奇数，需要注意中间值不参与反转，减少一位即可
                post = new StringBuffer(pre.substring(0, pre.length() - 1)).reverse().toString();
            }
            Long candidate = Long.parseLong(String.format("%s%s", pre, post));
            candidates.add(candidate);
        }
        // 打印所有候选值看看
        System.out.println(Arrays.toString(candidates.toArray()));
        return "";
    }

    public static void main(String[] args) {
        new Solution().nearestPalindromic("123");
        new Solution().nearestPalindromic("1999");
        new Solution().nearestPalindromic("90100");
        new Solution().nearestPalindromic("9900");
        new Solution().nearestPalindromic("9938");
    }
}

其输出如下：

[131, 121, 111]
[2002, 1991, 1881]
[100001, 9889, 9999]
[100001, 9889, 9999]

寻找“正确”答案

从上面的输出中，我们已经看到了一个个的正确答案（和一些离奇的错误答案），现在我们需要做的，就是把当前候选值中的距离原始值最近的值找出来就行，需要再上面的基础上添加如下代码：

        // 打印所有候选值看看
        System.out.println(Arrays.toString(candidates.toArray()));

        long value = Long.parseLong(n);// 输入本身
        candidates.remove(value);// 结果不能是本身
        long result = value;
        long minDif = Long.MAX_VALUE;
        for (Long a : candidates) {
            if (Math.abs(a - value) < minDif) {
                minDif = Math.abs(a - value);
                result = a;
            } else if (Math.abs(a - value) == minDif) {
                result = Math.min(result, a);
            }
        }
        System.out.println(result);
        return String.valueOf(result);

深水区里的坑

本来到上面为止，我们以为我们的代码已经差不多了，我自己想到的很多用例也都顺利通过了，但是你在递交之后，才会发现这其中还是有坑，比如100这个输入，我们给出的答案是101，但是其实答案应该是99，为什么会这样呢？关键就在于我们在for循环中+1、-1操作之后，高位的位数发生了变化，从n位变成了n-1位，即10变成了9，而反转时我们发现原始输入长度是奇数位的，于是反转时少了一位，9就变成了``（空字符串），所以低位就是空，这就导致本来应该是99，却变成了9，因此错失正确答案宝座。

最终正确答案

解决上面的坑才是本题之所以难的地方，也是我个人本题的核心所在。我在这个地方卡了比较久，最后也是在网上找到了一些参考资料才最终解决。其核心思想就是先通过输入数字的长度，分别计算出比它小一位的最大回文数（99...99）和比它大一位的最小回文数（10...01），并加入候选值，这样就解决了上面提到的深水区里的坑，所以最终答案就是如下代码了，

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Solution {
    public String nearestPalindromic(String n) {
        int half = n.length() / 2 + n.length() % 2; // 统一奇偶
        long highVal0 = Long.parseLong(n.substring(0, half)); // 获取高位的值，用来加减1
        Set<Long> candidates = new HashSet<>();// 存储所有候选值，目前最多三个
        candidates.add((long) Math.pow(10, n.length() - 1) - 1);
        candidates.add((long) Math.pow(10, n.length()) + 1);
        for (int i = -1; i <= 1; i++) { // 高位的值分别加 `-1`，`0`，`1`
            String pre = String.valueOf(highVal0 + i);
            String post = ""; // 反转之后的值，也就是新的后半部分
            if (n.length() % 2 == 0) { // 偶数，前半部分整体反转
                post = new StringBuffer(pre).reverse().toString();
            } else { // 奇数，需要注意中间值不参与反转，减少一位即可
                post = new StringBuffer(pre.substring(0, pre.length() - 1)).reverse().toString();
            }
            Long candidate = Long.parseLong(String.format("%s%s", pre, post));
            candidates.add(candidate);
        }
        // 打印所有候选值看看
//        System.out.println(Arrays.toString(candidates.toArray()));

        long value = Long.parseLong(n);// 输入本身
        candidates.remove(value);// 结果不能是本身
        long result = value;
        long minDif = Long.MAX_VALUE;
        for (Long a : candidates) {
            if (Math.abs(a - value) < minDif) {
                minDif = Math.abs(a - value);
                result = a;
            } else if (Math.abs(a - value) == minDif) {
                result = Math.min(result, a);
            }
        }
//        System.out.println(result);
        return String.valueOf(result);
    }

    public static void main(String[] args) {
        new Solution().nearestPalindromic("123");
        new Solution().nearestPalindromic("1999");
        new Solution().nearestPalindromic("90100");
        new Solution().nearestPalindromic("9900");
        new Solution().nearestPalindromic("9938");
        new Solution().nearestPalindromic("100");

    }
}

其他解法

关于深水区里的坑,除了上面的最大最小回文数，还有一种思路，感兴趣的可以研究一下。也有一些通过判断是否发生位数变化填充0和9的，也是一种思路。