跳到主要内容

564.寻找最近的回文数

· 阅读需 3 分钟

1、题干​

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

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

 

示例 1:

输入: n = "123"
输出: "121"

示例 2:

输入: n = "1"
输出: "0"
解释: 0 和 2是最近的回文，但我们返回最小的，也就是 0。

 

提示:

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

2、解题思路​

  • 找到中轴并提取中轴前的数字作为前半段，计算前半段数字加1、减1、不变3种情况的结果
  • 根据3种计算结果推导3个回文数，对进位导致位数增加、借位导致位数减少、前导0等情况分别进行处理
    • 若进位导致位数增加，求得 10...01 形式的回文数
    • 若借位导致位数减少或出现前导0的情况，求得 99...99 形式的回文数
    • 否则将前半段翻转作为后半段（原数字长度为奇数的需要剔除中轴），求得前后两段拼接而成的回文数
  • 在3个回文数中找到与 n 的差值的绝对值最小的数，若存在多个则取较小那个数，最后返回该数

3、代码​

var nearestPalindromic = function (n) {
    const len = n.length, m = Math.floor((len - 1) / 2);
    const s1 = n.slice(0, m + 1);

    const reverse = (s) => [].reduce.call(s, (a, c) => c + a, '');
    const nums = [`${+s1 + 1}`, s1, `${+s1 - 1}`].map((a) => {
        if (a.length > m + 1) return `1${'0'.repeat(len - 1)}1`;
        if (a.length <= m || (a === '0' && len === 2)) return '9'.repeat(len - 1);
        return a + (len % 2 ? reverse(a).slice(1) : reverse(a));
    });
    const diffs = nums.map((d) => BigInt(d) - BigInt(n)).map((d) => (d > 0 ? d : -d));
    const minDiff = diffs.reduce((a, c, i) => (c && c <= a[0] ? [c, i] : a), [Infinity, -1]);
    return nums[minDiff[1]];
};

4、执行结果​

image.png