求相同位数两数乘积的最大回文数：最快算法与代码优化

首先，咱们先聊聊原代码的问题：

• 双重循环完全遍历所有可能的乘积，重复计算了xy和yx（比如99999998和99989999是同一个数），平白浪费了一半的计算量；
• 每次判断回文都把数字转成字符串再反转，字符串操作的效率不如纯数学运算；
• 没有提前终止条件，明明当前乘积已经比找到的最大回文数小了，还继续循环，做无用功。

针对这些问题，咱们可以通过以下几个优化点来大幅提升效率，确保maxInt=9999时能在30秒内出结果：

核心优化策略 #

• 避免重复计算：内层循环从x开始向下遍历（而不是从maxInt），这样每个乘积只计算一次；
• 提前终止内层循环：维护当前找到的最大回文数，当x*y的结果已经小于这个最大值时，直接break内层循环（因为y继续减小，乘积只会更小）；
• 用数学方法判断回文：通过数字反转运算来判断，比字符串操作更快；
• 优先检查大乘积：从最大的数开始遍历，一旦找到符合条件的回文数，后续更小的乘积没必要再深入计算。

优化后的Python代码 #

def is_palindrome(num):
    # 数学方法判断回文数，比字符串操作更高效
    original = num
    reversed_num = 0
    while num > 0:
        reversed_num = reversed_num * 10 + num % 10
        num = num // 10
    return original == reversed_num

def largest_palindrome(maxInt):
    max_pal = 0
    # 外层循环从maxInt往下遍历
    for x in range(maxInt, 0, -1):
        # 内层循环从x开始，避免重复计算x*y和y*x
        for y in range(x, 0, -1):
            product = x * y
            # 如果当前乘积已经小于已知最大回文，直接break内层循环
            if product <= max_pal:
                break
            if is_palindrome(product):
                # 更新最大回文数
                max_pal = product
    return max_pal

效果验证 #

• 当maxInt=9时，返回9；
• 当maxInt=99时，返回9009；
• 当maxInt=999时，返回906609；
• 当maxInt=9999时，这个优化后的代码能快速返回99000099，完全在30秒以内。

另外，如果想要进一步提升速度，还可以加入位数预判：比如对于4位数的乘积，最大的回文数一定是8位数，形式为99xx0099，我们可以从大到小构造这类回文数，然后判断它是否能分解成两个4位数的乘积，这样能减少更多计算量，但上面的代码已经足够满足30秒内出结果的需求了。

内容的提问来源于stack exchange，提问作者YEp d