最大的數字大於給定的數字，這是一個迴文

Question

這是在採訪中被問到的。給定一個數字，比如900，輸出最小的迴文數大於數字909。我給蠻力解決方案，檢查每一個號碼，但我假設有一個更好的辦法，直到你到達中心數字去這

Answer 1

複製的第一個數字到最後，第二位到倒數第二等（或者如果有偶數位數則居中2位）。

如果結果數字小於原始數字，請將中心數字/中心2位數字加1。如果它們是9，則將它們設置爲零，然後再次使用它們旁邊的兩個數字，向外移動，直到您碰到非9。

編輯：

如果向外移動從來沒有迴路達到非9，在前面加上一個1到字符串，將所有數字，除了最後一個0，最後一個爲1。這是相同於將數字加2。

Answer 2

只是爲了好玩，這裏是Python中的簡單的實現（使用基本相同的算法由貢特拉姆博隆描述）。

def next_palindrome(n): 
    """ 
    Given a non-negative integer n, return the first integer strictly 
    greater than n whose decimal representation is palindromic. 

    """ 
    s = str(n + 1) 
    l = len(s) 
    if s[:l//2][::-1] < s[(l+1)//2:]: 
     head = str(int(s[:(l+1)//2])+1) 
    else: 
     head = s[:(l+1)//2] 
    return int(head + head[:l//2][::-1]) 

一些樣本輸出：

>>> next_palindrome(123) 
131 
>>> next_palindrome(4321) 
4334 
>>> next_palindrome(999) 
1001 

Answer 3

雖然上面已經回答是絕對正確的。只是爲了增加理解:)

可以有三種不同類型的輸入，需要分開處理。

1）輸入的數字是迴文，全部爲9。例如「9 9 9」。輸出應爲「1 0 0 1」

2）輸入號碼不是迴文。例如「1 2 3 4」。輸出 應爲「1 3 3 1「

3）輸入號碼是迴文結構和不具有所有787-9。例如 「1 2 2 1」。輸出應該是「1 3 3 1」。

輸入類型1的解決方案 很容易。輸出包含N + 1個數字，其中的角落數字是1，和角位之間的所有數字都爲0

現在讓我們先來談談輸入型2和3。讓我們首先定義下列兩個術語：

Left Side:給定數字的左半部分。 「1 2 3 4 5 6」的左側爲「1 2 3」，「1 2 3 4 5」的左側爲「1 2」

Right Side:給定數字的右半部分。 「1 2 3 4 5 6」的右側是「4 5 6」，「1 2 3 4 5」的右側是「4 5」 要轉換爲迴文，我們可以將其左側的鏡像或把它的右側鏡子。然而，如果我們把右側的鏡子拿過來，那麼所形成的迴文不能保證成爲下一個更大的迴文。

所以，我們必須把左邊的鏡子複製到右邊。但有些情況必須以不同的方式處理。請參閱以下步驟。

我們將從兩個指數i和j開始。我指向兩個中間元素（或者在n爲奇數的情況下指向中間元素周圍的兩個元素）。我們一個接一個地讓我和j彼此遠離。

Step 1.最初，忽略與右側相應部分相同的左側部分。例如，如果數字是「8 3 4 2 2 4 6 9」，我們忽略中間的四個元素。我現在指向元件3和現在J個點到元件6

Step 2.步驟1之後，下列情況下出現：

Case 1:指數i &Ĵ過境。 當輸入號碼是迴文時發生此情況。在這種情況下，我們只需向中間數字加1（或n爲偶數的數字），將進位傳給左側的MSB數字，同時將左側的鏡像複製到右側。例如，如果給定的數字是「1 2 9 2 1」，我們增加9到10並傳播進位。所以數字變成「1 3 0 3 1」

Case 2:左側和右側之間還有數字不一樣。所以，我們只是鏡像左側&儘量減少形成的數量，以保證下一個最小的迴文。 在這種情況下，可以有兩個子情況。

2.1)將左側複製到右側就足夠了，我們不需要增加任何數字，結果只是左側的鏡像。以下是這個子情況的一些例子。 「7 8 3 3 2 2」的下一個迴文是「7 8 3 3 8 7」 「1 2 5 3 2 2」的下一個迴文是「1 2 5 5 2 1」 「1 4 5 8 7 6 7 8 3 2 2「is」1 4 5 8 7 6 7 8 5 4 1「 我們如何檢查這個子情況？我們需要檢查的是在步驟1中被忽略的部分之後的數字。這個數字在上面的例子中突出顯示。如果該數字大於右側數字中的相應數字，則將左側複製到右側就足夠了，我們不需要做其他任何事情。

2.2)將左側複製到右側是不夠的。當上面定義的左側數字較小時會發生這種情況。以下是這種情況的一些例子。 「7 1 3 3 2 2」的下一個迴文是「7 1 4 4 1 7」 「1 2 3 4 6 2 8」的下一個迴文是「1 2 3 5 3 2 1」 「9 4 1 8 7 9 7 8 3 2 2「is」9 4 1 8 8 0 8 8 1 4 9「 我們像案例1一樣處理這個子案例。我們只給中間數字加1（或者數字是偶數）向左側的MSB數字傳播進位，同時將左側的鏡像複製到右側。

來源：http://www.geeksforgeeks.org/given-a-number-find-next-smallest-palindrome-larger-than-this-number/