004. 最大回文数乘积(largest palindrome product)

回文数即从正反两边读都是一样的数,两个二位数的乘积中最大的回文数为\(9009=91*99\),寻找两个三位数乘积中最大的回文数。

分析:题目说要找到两个三位数相乘得到的最大回文数,所以这个数最小只能是\(100^2\),最大只能是\(999^2\)了,也就是说处于区间\([10000,998001]\)之间,这个区间中绝大部分是六位数,而且题目也要求最大的回文数,所以我们先假设所求数是一个六位数,看能不能找到一个符合要求的数。假设这个六位数是\(abccba\)的形式,则有:

$$ \begin{aligned} 'abccba'&=10^5a+10^4b+10^3c+10^2c+10b+a\\ &=100001a+10010b+1100c\\ &=11(9091a+910b+100c) \end{aligned} $$

可以很明显的看出满足要求的六位数必然是11的倍数,因此在检测六位数是否是回文数之前,我们可以先检测它是否是11的倍数,这样可以加快验证的速度。我们可以使用列表推导式从大到小生成两个三位数的乘积,再检测这个乘积是否是11的倍数以及是否是一个回文数,最后对这个列表求最大值即为所求。需要注意,这里用Lambda表达式定义了一个判断特定数字是否是回文数的函数,方法就是把数字转化为字符串,再判断这个字符串是否与其翻转字符串相等。

def main():
    r = range(999,99,-1)
    is_palindrome = lambda x : str(x) == str(x)[::-1]
    ans = max([i*j for i in r for j in r if (i*j)%11==0 and is_palindrome(i*j)])
    return ans