Hard

题目描述

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

这里的最近是指两个整数之间的绝对差值最小。

示例 1：

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

示例 2：

输入：n = "1"
输出："0"
解释：0 和 2 都是最近的回文数，但我们返回最小的那个 0。

提示：

  • 1 <= n.length <= 18
  • n 只由数字组成
  • n 不含前导零
  • n 表示范围在 [1, 10^18 - 1] 的整数

思考：

  • 暴力法适用于这个问题吗？想想其他方法。
  • 举一些例子如 1234、999、1000 等，检查它们最近的回文数。有多少种不同的情况？
  • 我们是否需要考虑字符串的左半部分或右半部分，还是两者都要考虑？
  • 尝试找出这些数字的最近回文数：12932、99800、12120。你观察到了什么？

解题思路

这道题的关键是找到所有可能的候选回文数，然后选择距离最近的那个。

主要思路：

  1. 构造候选回文数：基于输入字符串的前半部分，我们可以构造几个可能的回文数候选
  2. 特殊情况处理：需要考虑一些边界情况，如 999...9 和 100...1 这样的数字

具体的候选回文数包括：

  • 镜像回文：将前半部分直接镜像到后半部分
  • 前半部分+1的镜像：将前半部分加1后镜像
  • 前半部分-1的镜像：将前半部分减1后镜像
  • 特殊边界：999...9（位数减1的最大回文）和 100...1（位数加1的最小回文）

算法步骤：

  1. 提取输入字符串的前半部分
  2. 生成上述5种候选回文数
  3. 过滤掉与原数相等的候选
  4. 选择距离最近的候选，如果距离相等则选较小的

时间复杂度主要在于字符串操作和数值比较，整体效率很高。

代码实现

class Solution {
public:
    string nearestPalindromic(string n) {
        int len = n.length();
        long long num = stoll(n);
        
        set<long long> candidates;
        
        // 特殊情况：999...9 -> 100...001
        candidates.insert(pow(10, len) + 1);
        // 特殊情况：100...001 -> 999...9
        candidates.insert(pow(10, len - 1) - 1);
        
        // 获取前半部分
        string prefix = n.substr(0, (len + 1) / 2);
        long long prefixNum = stoll(prefix);
        
        // 生成三个候选：prefix-1, prefix, prefix+1
        for (int i = -1; i <= 1; i++) {
            string p = to_string(prefixNum + i);
            string candidate = p;
            
            // 构造回文
            int start = len % 2 == 0 ? p.length() - 1 : p.length() - 2;
            for (int j = start; j >= 0; j--) {
                candidate += p[j];
            }
            
            candidates.insert(stoll(candidate));
        }
        
        // 移除原数字本身
        candidates.erase(num);
        
        // 找到最近的回文数
        long long result = *candidates.begin();
        long long minDiff = abs(result - num);
        
        for (long long candidate : candidates) {
            long long diff = abs(candidate - num);
            if (diff < minDiff || (diff == minDiff && candidate < result)) {
                result = candidate;
                minDiff = diff;
            }
        }
        
        return to_string(result);
    }
};

class Solution:
    def nearestPalindromic(self, n: str) -> str:
        length = len(n)
        num = int(n)
        
        candidates = set()
        
        # 特殊情况
        candidates.add(10**(length) + 1)  # 999...9 -> 1000...0001
        candidates.add(10**(length-1) - 1)  # 100...0 -> 99...9
        
        # 获取前半部分
        prefix = n[:(length + 1) // 2]
        prefix_num = int(prefix)
        
        # 生成三个候选：prefix-1, prefix, prefix+1
        for i in [-1, 0, 1]:
            p = str(prefix_num + i)
            candidate = p
            
            # 构造回文
            if length % 2 == 0:
                candidate += p[::-1]
            else:
                candidate += p[-2::-1]
            
            candidates.add(int(candidate))
        
        # 移除原数字本身
        candidates.discard(num)
        
        # 找到最近的回文数
        result = min(candidates, key=lambda x: (abs(x - num), x))
        
        return str(result)

public class Solution {
    public string NearestPalindromic(string n) {
        int length = n.Length;
        long num = long.Parse(n);
        
        HashSet<long> candidates = new HashSet<long>();
        
        // 特殊情况
        candidates.Add((long)Math.Pow(10, length) + 1);
        candidates.Add((long)Math.Pow(10, length - 1) - 1);
        
        // 获取前半部分
        string prefix = n.Substring(0, (length + 1) / 2);
        long prefixNum = long.Parse(prefix);
        
        // 生成三个候选：prefix-1, prefix, prefix+1
        for (int i = -1; i <= 1; i++) {
            string p = (prefixNum + i).ToString();
            string candidate = p;
            
            // 构造回文
            int start = length % 2 == 0 ? p.Length - 1 : p.Length - 2;
            for (int j = start; j >= 0; j--) {
                candidate += p[j];
            }
            
            candidates.Add(long.Parse(candidate));
        }
        
        // 移除原数字本身
        candidates.Remove(num);
        
        // 找到最近的回文数
        long result = long.MaxValue;
        long minDiff = long.MaxValue;
        
        foreach (long candidate in candidates) {
            long diff = Math.Abs(candidate - num);
            if (diff < minDiff || (diff == minDiff && candidate < result)) {
                result = candidate;
                minDiff = diff;
            }
        }
        
        return result.ToString();
    }
}

var nearestPalindromic = function(n) {
    const len = n.length;
    const num = BigInt(n);
    const candidates = new Set();
    
    // Edge cases: smallest and largest palindromes with different lengths
    candidates.add(BigInt(10) ** BigInt(len - 1) - BigInt(1)); // 999...9
    candidates.add(BigInt(10) ** BigInt(len) + BigInt(1)); // 100...001
    
    // Get the prefix (first half including middle for odd length)
    const isOdd = len % 2;
    const mid = Math.floor(len / 2);
    const prefix = n.substring(0, mid + isOdd);
    
    // Generate candidates by modifying the prefix
    for (let delta of [-1, 0, 1]) {
        const newPrefix = (BigInt(prefix) + BigInt(delta)).toString();
        let palindrome;
        
        if (isOdd) {
            palindrome = newPrefix + newPrefix.slice(0, -1).split('').reverse().join('');
        } else {
            palindrome = newPrefix + newPrefix.split('').reverse().join('');
        }
        
        candidates.add(BigInt(palindrome));
    }
    
    // Remove the original number
    candidates.delete(num);
    
    // Find the closest palindrome
    let closest = null;
    let minDiff = null;
    
    for (let candidate of candidates) {
        const diff = candidate > num ? candidate - num : num - candidate;
        
        if (minDiff === null || diff < minDiff || (diff === minDiff && candidate < closest)) {
            minDiff = diff;
            closest = candidate;
        }
    }
    
    return closest.toString();
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(L)，其中 L 是字符串长度。主要操作包括字符串处理和数值比较，候选数量是常数
空间复杂度O(L)，用于存储候选回文数和临时字符串

相关题目