大于给定数字且为回文数的最小数字是多少？

Question

这是一个面试题。给定一个数字，比如900，输出大于该数字的最小回文数，例如909。我提供了一个暴力解法，逐个检查每个数字，但我认为应该有更好的方法来解决这个问题。

- Aks

---

给定一个数字 abcde，找到它的反转数 edcba。如果不是回文数，则将 e 替换为 a，如果还不是回文数，则将 d 替换为 b。 - Grijesh Chauhan

你的算法，使用12225作为abcde，返回了12221，这是不正确的。 - Guntram Blohm

@GuntramBlohm 嗯，我错了。 - Grijesh Chauhan

Answer 1

仅供娱乐，以下是使用Python进行简单实现的代码（基本上使用了Guntram Blohm所描述的相同算法）。

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

- Mark Dickinson

---

做得好。将右侧部分丢弃，通过加一来增加左侧部分（而不是循环遍历每个数字），并在增加后将左侧部分“镜像”到右侧，使算法更短，并处理所有数字都为9的情况 - 至少只要数字足够小以适合整数，这似乎是问题的意思。 - Guntram Blohm

Answer 2

将第一个数字复制到最后一个，第二个数字复制到倒数第二个，以此类推，直到到达中心数字（如果是偶数个数字，则为中心2个数字）。

如果结果数字小于原始数字，则将中心数字/中心2个数字增加1。如果它们是9，则将它们设置为零，并重试其旁边的2个数字，向外移动，直到遇到非9数字为止。

编辑：

如果向外移动的循环永远不会遇到非9数字，则在字符串前面添加1，将除最后一个数字以外的所有数字设置为0，并将最后一个数字设置为1。这相当于将2加到数字上。

- Guntram Blohm

---

回文应该严格大于，而不是大于或等于。在前一种情况下，即使我们用“_smaller or equal_”替换“_smaller_”，建议的算法似乎也无法处理“9”、“99”、“999”等情况。 - AlexD

@AlexD：对于“严格大于”，您可以将其增加1，然后将“大于或等于”算法应用于结果。 - Mark Dickinson

如果提供的数字是99，而结果应该是101 - 一个比原来多1位数的数字，我不确定这个是如何工作的。 - zmbq

你说得对，如果在第一步之后数字只由9组成（997之后的下一个回文数也是1001，第一步将997变为999），我们需要特殊处理。 - Guntram Blohm

Answer 3

虽然以上回答完全正确。只是为了更好地理解 :)

可能需要分别处理三种不同类型的输入。

1）输入数字是回文数且全部都是9。例如“999”。输出应为“1001”

2）输入数字不是回文数。例如“1234”。输出应为“1331”

3）输入数字是回文数，但不全部都是9。例如“1221”。输出应为“1331”。

对于类型1的输入，解决方案很容易。输出包含n + 1个数字，其中角落数字为1，而在两个角落数字之间的所有数字都为0。

现在让我们来谈谈类型2和3的输入。首先定义以下两个术语：

左侧：给定数字的左半部分。 “1 2 3 4 5 6”的左侧是“1 2 3”，“1 2 3 4 5”的左侧是“1 2”。

右侧：给定数字的右半部分。 “1 2 3 4 5 6”的右侧是“4 5 6”，“1 2 3 4 5”的右侧是“4 5”。 为了转换为回文，我们可以将其左侧的镜像或右侧的镜像取出。但是，如果我们取右侧的镜像，则所形成的回文不能保证是下一个更大的回文。

因此，我们必须将左侧的镜像复制到右侧。但是，有些情况必须以不同的方式处理。请参见以下步骤。

我们将从两个索引i和j开始。 i指向两个中间元素（或在n为奇数的情况下指向中间元素周围的两个元素）。我们逐一将i和j从彼此移开。

步骤1。 首先忽略左侧与右侧相应部分相同的部分。例如，如果数字是“8 3 4 2 2 4 6 9”，我们忽略中间的四个元素。现在i指向元素3，j指向元素6。

步骤2。 在第一步之后，会出现以下情况：

情况1： 索引i和j越过边界。 当输入数字为回文数时，就会出现这种情况。在这种情况下，我们只需将中间数字（或偶数情况下的数字）加1，并将进位传递到左侧的MSB数字，同时将左侧的镜像复制到右侧。 例如，如果给定的数字是“1 2 9 2 1”，我们将9增加到10并传递进位。因此，数字变为“1 3 0 3 1”

情况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”的下一个回文是“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”的下一个回文是“9 4 1 8 8 0 8 8 1 4 9” 我们像第一种情况一样处理这个子情况。我们只需将1添加到中间数字（或在n为偶数的情况下添加数字），将进位传播到左侧的MSB数字，并同时将左侧的镜像复制到右侧。

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

- Pranay Agrawal