Skip to main content
 首页 » 编程设计

python之加速 Python 3.4 代码

2025年05月04日8java哥

我有一个问题,我需要在给定数字之后找到下一个最大的回文,但是我遇到了运行时间超过 1 秒的问题。有什么方法可以加快这段代码的速度吗?

inp = input() 
if inp == '9' * len(inp): 
    print('1' + ('0' * (len(inp) - 1)) + '1') #ran into a problem where 999 would give 9109 
else: 
num = list(inp) 
oldnum = int(inp) 
if len(num) % 2 == 0: #for even length numbers 
    for i in range(len(num) // 2): 
        num[len(num) // 2 + i] = num[len(num) // 2 - 1 - i] 
    if int("".join(num)) > oldnum: 
        print("".join(num)) 
    else:                   
#sometimes the palindrome was smaller eg: 1199 --> 1111 
        num[len(num) // 2 - 1] = str(int(num[len(num) // 2 - 1]) + 1) 
        num[len(num) // 2] = str(int(num[len(num) // 2]) + 1) 
        print("".join(num)) 
else: #basically the same but for odd length numbers 
    for i in range(len(num) // 2): 
        num[len(num) // 2 + 1 + i] = num[len(num) // 2 - 1 - i] 
    if int("".join(num)) > oldnum: 
        print("".join(num)) 
    else: 
        num[len(num) // 2] = str(int(num[len(num) // 2]) + 1) 
        print("".join(num)) 

请您参考如下方法:

下面是我将如何分解它,

# simple version, easy to understand and fast enough 
#   up to maybe a thousand digits 
 
def next_palindrome(n): 
    """ 
    Find the first integer p such that p > n and p is palindromic 
    """ 
    # There are two forms of palindrome: 
    #   even number of digits,     abccba 
    #   odd number of digits,      abcba 
    # Find abc 
    s = str(n) 
    abc = s[:(len(s) + 1) // 2] 
 
    # There are six possibilites for p: 
    #     
    #   abcpq  <  abcba    -> p = abcba 
    #   abcpq  >= abcba    -> p = ab(c + 1)ba      (with carries as needed) 
    #   abcpqr == 999999   -> p = 1000001          *(num digits + 1) 
    #   
    #   abcpqr <  abccba   -> p = abccba 
    #   abcpqr >= abccba   -> p = ab(c+1)(c+1)ba   (with carries as needed) 
    #   abcpq  == 99999    -> p = 100001           *(num digits + 1) 
    #   
    #  *Note that the even-number-of-9s case is properly handled by 
    #    odd-digits-with-carry, but odd-number-of-9s needs special handling 
    # 
    # Make basis substrings 
    cba  = abc[::-1] 
    ba   = cba[1:] 
    abc1 = str(int(abc) + 1) 
    cba1 = abc1[::-1] 
    ba1  = cba1[1:] 
    # Assemble candidate values 
    candidates = [ 
        int(abc  + ba),        # abcba 
        int(abc1 + ba1),       # ab(c+1)ba 
        int(abc  + cba),       # abccba 
        int(abc1 + cba1),      # ab(c+1)(c+1)ba 
        int(abc1[:-1] + ba1)   # handles odd-number-of-9s 
    ] 
    # Find the lowest candidate > n 
    return min(c for c in candidates if c > n) 
 
def main(): 
    while True: 
        n = int(input("\nValue for n (or -1 to quit): ")) 
        if n == -1: 
            break 
        else: 
            print("Next palindrome is {}".format(next_palindrome(n))) 
 
if __name__ == "__main__": 
    main() 

运行方式如下

Value for n (or -1 to quit): 12301 
Next palindrome is 12321 
 
Value for n (or -1 to quit): 12340 
Next palindrome is 12421 
 
Value for n (or -1 to quit): 99999 
Next palindrome is 100001 
 
Value for n (or -1 to quit): 123001 
Next palindrome is 123321 
 
Value for n (or -1 to quit): 123400 
Next palindrome is 124421 
 
Value for n (or -1 to quit): 999999 
Next palindrome is 1000001 
 
Value for n (or -1 to quit): -1 

编辑:我以为你说的可能是 100 位数字。一百万个数字值得花更多的时间来最小化字符串操作和类型转换的数量,如下所示:

# Super-efficient version 
#  for playing with million-digit palindromes 
 
def str_lt(x, y): 
    """ 
    Take two integer strings, `x` and `y`, 
      return int(`x`) < int(`y`) 
    """ 
    return len(x) < len(y) or x < y 
 
def str_add_1(n): 
    """ 
    Given an integer string `n`, 
      return str(int(n) + 1) 
    """ 
    # find the first non-9 digit, starting from the right 
    for i in range(len(n) - 1, -1, -1): 
        if n[i] != '9': 
            return n[:i] + str(int(n[i]) + 1) + '0' * (len(n) - i - 1) 
    # string was all 9s - overflow 
    return '1' + '0' * len(n) 
 
def next_palindrome(n): 
    """ 
    For non-negative integer `n` (as int or str) 
      find the first integer p such that p > n and p is palindromic 
    Return str(p) 
 
    Note: `n` must be well-formed, ie no leading 0s or non-digit characters 
    """ 
    # Make sure n is a string 
    if not isinstance(n, str): 
        n = str(n) 
 
    # There are three forms of palindrome: 
    #           single digit,      x    (ab == '') 
    #  even number of digits,   abba    ( x == '') 
    #   odd number of digits,  abxba    ( x is single digit) 
    #     
    if len(n) == 1: 
        # take care of single digit case 
        return '11' if n == '9' else str_add_1(n) 
    else: 
        # There are six possibilites for p: 
        #     
        #  (1)  abqr   <  abba   -> p = abba 
        #  (2)  abqr  >=  abba   -> p = a(b+1)(b+1)a   (with carries as needed) 
        #  (3)  abqr  ==  9999   -> p = 10001          (carry results in overflow) 
        #   
        #  (4)  abxqr  < abxba   -> p = abxba 
        #  (5)  abxqr >= abxba   -> p = ab(x + 1)ba    (with carries as needed) 
        #  (6)  abxqr == 99999   -> p = 100001         (carry results in overflow) 
        # 
        # Find ab, x, qr 
        half = len(n) // 2 
        ab = n[     : half] 
        x  = n[ half:-half]    # a 0- or 1-digit string 
        qr = n[-half:     ] 
 
        ba = ab[::-1] 
        if str_lt(qr, ba): 
            # solve cases (1) and (4) 
            return "".join([ab, x, ba]) 
 
        if x == '9': 
            # do manual carry from x 
            ab1 = str_add_1(ab) 
            ba1 = ab1[::-1] 
            if len(ab1) > len(ab): 
                # carry results in overflow - case (6) 
                return ab1 + ba1 
            else: 
                # carry but no overflow - case (5) 
                return "".join([ab1, '0', ba1]) 
 
        if x: 
            # no carry - case (5) 
            return "".join([ab, str_add_1(x), ba]) 
 
        # x == '' 
        ab1 = str_add_1(ab) 
        ba1 = ab1[::-1] 
        if len(ab1) > len(ab): 
            # carry results in overflow - case (3) 
            return ab1[:-1] + ba1 
        else: 
            # no overflow - case (2) 
            return ab1 + ba1 

在我的机器上,这会在不到 0.002 秒的时间内找到一个百万位的回文(而您的代码大约需要 18.5 秒)。