> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/math/564.-find-the-closest-palindrome.md).

# 564. Find the Closest Palindrome

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

找与给定数值n最相近的回文数。分为三种情况:

1. 比n多一位: 99->101
2. 比n少一位: 101->99
3. 和n位数一样。为了和n尽量靠近，前半边不能动，否则数会差很大，让后半边和前半边一致。此时如果n本身就是回文的话，要把中间数调高1或降低1。

把这三种情况以及子情况全检查一遍，找出差值最小且数是最小的。

答案参考了[这](https://link.zhihu.com/?target=https%3A//blog.csdn.net/magicbean2/article/details/78889530)。

```cpp
/*
 * @lc app=leetcode id=564 lang=cpp
 *
 * [564] Find the Closest Palindrome
 */

// @lc code=start
class Solution {
public:
    string nearestPalindromic(string n) {
        const int L = n.size();
        unordered_set<long> candidates;
        // 多一位数字，10...01
        candidates.insert(pow(10, L) + 1); 
        // 少一位数字，99...99或0
        candidates.insert(pow(10, L - 1) - 1);
        // prefix + Mid + reverse(prefix)
        // Mid = {mid -1, mid, mid + 1}
        long prefix = stol(n.substr(0, (L + 1) / 2));
        for (long i = -1; i <= 1; ++i) {
            string p = to_string(prefix + i);
            string pp = p + string(p.rbegin() + (L & 1), p.rend());
            candidates.insert(stol(pp));
        }
        long num = stol(n), min_diff = LONG_MAX, res = 0;
        candidates.erase(num);
        for (auto c : candidates) {
            long diff = abs(c - num);
            if (diff < min_diff) {
                res = c;
                min_diff = diff;
            } else if (diff == min_diff) {
                res = min(res, c);
            }
        }
        return to_string(res);
    }
};
// @lc code=end


```