查找第二大回文
查找第二大回文
提问于 2022-04-03 06:12:48
我为佩林问题编写了一个程序：
如果正整数的十进制表示是相同的从左到右，从右到左，则称为回文。对于给定的不超过1000000位数的正整数K，将大于K的最小回文的值写入输出。…
我的程序似乎不够快(需要在2S-9s之间运行)。我想到的一种方法是去掉基于字符串的数学，但是当我对它进行编码时，它开始在特定的数字上失败。有什么方法可以优化我看不到的代码吗？
代码：
from math import ceil
def next_palindrome(n):
digits = list(str(n))
length = len(digits)
mid = length / 2
rev = int("".join(digits[::-1]))
if all(d == "9" for d in digits):
return n + 2
if length == 1:
return n + 1
left = digits[: int(mid)]
digits[ceil(mid) :] = left[::-1]
palindrome = int("".join(digits))
if palindrome > n:
return palindrome
if length % 2 != 0:
mid = int(mid)
if digits[mid] == "9":
# return int("".join(digits)) + (11 * (10 * (mid - 1)))
return int("".join(digits)) + int(f"11{'0' * (mid - 1)}")
digits[mid] = f"{int(digits[mid])+1}"
return "".join(digits)
left_d, right_d = left[-1], digits[ceil(mid) :][0]
if left_d == "9" and right_d == "9":
mid = int(mid)
# return int("".join(digits)) + (11 * (10 * (mid - 2)))
return int("".join(digits)) + int(f"11{'0' * (mid - 2)}")
left[-1] = f"{int(left_d) + 1}"
return "".join(left + left[::-1])
t = int(input())
for i in range(t):
n = int(input())
print(next_palindrome(n))回答 1
Code Review用户
发布于 2022-04-05 06:04:51
Python字符串实际上已经是字符列表了。不需要将字符串转换为单个字符串的列表。这是：
digits = list(str(n))
rev = int("".join(digits[::-1]))可以简单地写成这样：
digits = str(n)
rev = int(digits[::-1])消除不必要的join。在整个代码中也可以进行类似的改进。
真正的速度来自于实现回文可以很容易的枚举。
第n个偶长回文是str(n) + str(n)[::-1]。
第n个奇数长度回文是str(n) + str(n)[-2::-1]。
n可以从输入数字的前半部分确定。如果生成的回文不够大，则生成n+1-th。
页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codereview.stackexchange.com/questions/275477
复制相关文章
相似问题
腾讯云开发者
