[刷题防痴呆] 0564 - 寻找最近的回文数 (Find th

题目地址

https://leetcode.com/problems/find-the-closest-palindrome/

题目描述

564. Find the Closest Palindrome

Given a string n representing an integer, return the closest integer (not including itself), which is a palindrome. If there is a tie, return the smaller one.

The closest is defined as the absolute difference minimized between two integers.

 

Example 1:

Input: n = "123"
Output: "121"
Example 2:

Input: n = "1"
Output: "0"
Explanation: 0 and 2 are the closest palindromes but we return the smallest which is 0.

思路

• 5个candidate, 然后求最近的.

关键点

• 举例: 12345
• 5个对应的candidate为: 12321, 12421, 12221, 9999, 10001.

代码

• 语言支持：Java

class Solution {
    public String nearestPalindromic(String n) {
        int len = n.length();
        boolean isEven = len % 2 == 0;
        int index = 0;
        if (isEven) {
            index = len / 2 - 1;
        } else {
            index = len / 2;
        }
        long left = Long.parseLong(n.substring(0, index + 1));
        List<Long> candidates = new ArrayList<>();
        candidates.add(getPalindrom(left, isEven));
        candidates.add(getPalindrom(left + 1, isEven));
        candidates.add(getPalindrom(left - 1, isEven));
        candidates.add((long)Math.pow(10, len - 1) - 1);
        candidates.add((long)Math.pow(10, len) + 1);

        long diff = Long.MAX_VALUE;
        long res = 0;
        long num = Long.parseLong(n);
        for (long candidate: candidates) {
            if (candidate == num) {
                continue;
            }
            long temp = Math.abs(candidate - num);
            if (temp < diff) {
                res = candidate;
                diff = temp;
            } else if (temp == diff) {
                res = Math.min(res, candidate);
            }
        }

        return res + "";
    }

    private long getPalindrom(long left, boolean isEven) {
        long res = left;
        if (!isEven) {
            left /= 10;
        }
        while (left > 0) {
            res = res * 10 + left % 10;
            left /= 10;
        }

        return res;
    }
}