SPOJ 下一个回文数

Question

我正在尝试解决SPOJ的第5个问题：找到一个给定输入的下一个最大的“回文”整数；也就是说，这个整数在十进制表示中，从左到右和从右到左读都是一样的。

请查看这个问题的详细信息 这里

我不想用暴力搜索的方法，而是想计算下一个回文数。但是我的代码还是返回了TLE（也就是超出时间限制），这让我很沮丧……你能给我一点提示吗？

这是我用python 3.x写的代码

if __name__ == '__main__':
    n = int(input())
    for i in range(n):
        string = input()
        length = len(string)
        ans = ""
        if length %2 == 0 :
            half = length // 2
            str_half = string[0:half]
            ans =  str_half + str_half[::-1]         
            if(ans <= string):
                str_half = str(int(str_half) + 1)
                ans = str_half + (str_half[0:half])[::-1]
            print(ans)
        else:
            half = length // 2
            str_half = string[0:half]
            ans = str_half + string[half] + str_half[::-1]
            if(ans<= string):            
                str_half = str(int(str_half+string[half]) + 1)
                ans = str_half + (str_half[0:half])[::-1]
            print(ans)

Answer 1

根据这个问题，我们来看看当 K 的长度等于 1 时，最长的回文数是什么。这个情况可以忽略，因为没有比 K 更大的回文数。K 的长度等于 2 的情况也是一样。所以，评估这个的伪代码如下：

if K.length <= 2  
     pass  

当 K 的长度等于 3 时，我们关注的是 K[0] 和 K[2]，这两个值决定了边界。比如说 K = 100，我们关注的就是 1 和 0。如果 K[0] 比 K[2] 大，那我们就知道必须把 K[2] 改成 K[0]，这样就完成了。再举个例子，K = 200，首个比它大的回文数是 202，这是第一个相等的质数。如果 K[0] 等于 K[2] 并且 K 小于 999，我们就把 K[1] 加 1，这样也完成了。伪代码如下：

if K[0] > K[2]   
      K[2] = K[0]   
if K[0] == K[2] and K < 999  
      K[1]++  

如果 K 中的所有值都是 9（比如 999、9999 等），那就把 K 加 2，然后结束这个过程。我会把算法的一般形式留给你，除非你真的卡住了。

Answer 2

输入的数据可能会很长。题目中提到“最多不超过1000000位数字”。所以可能会有一些测试用例包含几十万位数字。把这样一个字符串分成两半，反转其中一半再拼接起来，确实需要花一点时间。不过我知道，Python处理字符串的能力还不错，所以这部分耗时其实不算太多。

真正耗时的是把这么长的字符串转换成数字，以及把大数字转换回字符串。比如对于K = 10 ** 200000 + 2，这一行str_half = str(int(str_half+string[half]) + 1)就花了将近一秒钟。你在自己的电脑上可能会快一些，但SPOJ的服务器比较慢，这种情况可能会让你超出时间限制。

所以你需要避免这些转换，直接在字符串表示上操作（用可变的数字列表）。