Given an integer n, find the closest integer (not including itself), which is a palindrome.
The 'closest' is defined as absolute difference minimized between two integers.
Example 1:
Note:
The input n is a positive integer represented by string, whose length will not exceed 18.
If there is a tie, return the smaller one as answer.
這道題給了我們一個數字，讓我們找到其最近的回文數，而且說明了這個最近的回文數不能是其本身。比如如果給你個131，那麼就需要傳回121。而且傳回的回文數可能位數還不同，比如當n為100的時候，我們就應該傳回99，或者給了我們99時，需要傳回101。那麼實際上最近回文數是有範圍的，比如說n為三位數，那麼其最近回文數的範圍在[99, 1001]之間，這樣我們就可以根據給定數字的位數來确定出兩個邊界值，要和其他生成的回文數進行比較，取絕對差最小的。
下面我們來看如何求一般情況下的最近回文數，我們知道回文數就是左半邊和右半邊互為翻轉，奇數情況下中間還有個單獨的值。那麼如何将一個不是回文數的數變成回文數呢，我們有兩種選擇，要麼改變左半邊，要麼改變右半邊。由于我們希望和原數絕對差最小，肯定是改變低位上的數比較好，是以我們改變右半邊，那麼改變的情況又分為兩種，一種是原數本來就是回文數，這種情況下，我們需要改變中間的那個數字，要麼增加1，要麼減小1，比如121，可以變成111和131。另一種情況是原數不是回文數，我們隻需要改變右半邊就行了，比如123，變成121。那麼其實這三種情況可以總結起來，分别相當于對中間的2進行了-1, +1, +0操作，那麼我們就可以用一個-1到1的for循環一起處理了，先取出包括中間數的左半邊，比如123就取出12，1234也取出12，然後就要根據左半邊生成右半邊，為了同時處理奇數和偶數的情況，我們使用一個小tricky，在反轉複制左半邊的時候，我們給rbegin()加上len&1，當奇數時，len&1為1，這樣就不會複制中間數了；為偶數時，len&1為0，這就整個翻轉複制了左半邊。我們把每次生成的回文串轉為轉為數字後加入到一個集合set中，把之前的兩個邊界值也同樣加進去，最後我們在五個candidates中找出和原數絕對差最小的那個傳回，記得别忘了在集合中删除原數，因為如果原數時回文的話, i=0時就把自己也加入集合了，參見代碼如下：
<a>class Solution {</a>
參考資料：
<a href="https://discuss.leetcode.com/topic/88897/java-solution-with-detailed-proof" target="_blank">https://discuss.leetcode.com/topic/88897/java-solution-with-detailed-proof</a>
<a href="https://discuss.leetcode.com/topic/87271/c-short-solution-only-need-to-compare-5-numbers" target="_blank">https://discuss.leetcode.com/topic/87271/c-short-solution-only-need-to-compare-5-numbers</a>
，如需轉載請自行聯系原部落客。