这是一个面试题。给定一个数字,比如900,输出大于该数字的最小回文数,例如909。我提供了一个暴力解法,逐个检查每个数字,但我认为应该有更好的方法来解决这个问题。
这是一个面试题。给定一个数字,比如900,输出大于该数字的最小回文数,例如909。我提供了一个暴力解法,逐个检查每个数字,但我认为应该有更好的方法来解决这个问题。
仅供娱乐,以下是使用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
将第一个数字复制到最后一个,第二个数字复制到倒数第二个,以此类推,直到到达中心数字(如果是偶数个数字,则为中心2个数字)。
如果结果数字小于原始数字,则将中心数字/中心2个数字增加1。如果它们是9,则将它们设置为零,并重试其旁边的2个数字,向外移动,直到遇到非9数字为止。
编辑:
如果向外移动的循环永远不会遇到非9数字,则在字符串前面添加1,将除最后一个数字以外的所有数字设置为0,并将最后一个数字设置为1。这相当于将2加到数字上。
虽然以上回答完全正确。只是为了更好地理解 :)
可能需要分别处理三种不同类型的输入。
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/
abcde
,找到它的反转数edcba
。如果不是回文数,则将e
替换为a
,如果还不是回文数,则将d
替换为b
。 - Grijesh Chauhan