python - SPOJ 下一个回文

Question

我正在尝试解决 SPOJ 问题 5:找到给定输入的下一个最大整数“回文”；也就是说，一个以十进制表示法从左到右和从右到左读取相同的整数。

问题请看here

我尝试计算下一个回文，而不是使用强力搜索。但是我的代码仍然返回 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

输入可以很长。问题陈述说“不超过 1000000 位”。所以可能有几个测试用例有几十万个数字。将这样的字符串分成两半，反转一半并附加它们确实需要一点时间。但据我所知，Python 的字符串处理非常好，所以这只是问题的一小部分。

花费长时间的是将如此长的字符串转换为数字，并将巨大的数字转换为字符串。对于 K = 10 ** 200000 + 2，str_half = str(int(str_half+string[half]) + 1) 这一步在这里花费了将近一秒钟。它在您的计算机上可能更快，但 SPOJ 的机器非常慢，这样的情况可能会使您超过那里的时间限制。

因此您必须避免转换，直接处理字符串表示(可变数字列表)。