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

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

花费很长时间的是将这样长度的字符串转换为数字,将大数字转换为字符串.因为K = 10 ** 200000 + 2,这一步str_half = str(int(str_half+string[half]) + 1)只需要一秒钟.它在您的计算机上可能会更快,但SPOJ的机器速度很慢,这种情况可能会使您超过时间限制.

所以你必须避免转换,直接在字符串表示(可变数字列表)上工作.