0479：最大回文数乘积（★★）

2016-04-23 约 240 字预计阅读 1 分钟次阅读

力扣第 479 题

题目

给定一个整数 n ，返回可表示为两个 n 位整数乘积的 最大回文整数 。因为答案可能非常大，所以返回它对 1337 取余。

示例 1：

输入：n = 2
输出：987
解释：99 x 91 = 9009, 9009 % 1337 = 987

示例 2：

输入：n = 1
输出：9

提示:

1 <= n <= 8

分析

两个 n 位数相乘，必然是 2n 或 2n-1 位
因此从大到小遍历 n 位回文根，构造回文数，判断即可
- 例如 10 作为回文根，可根据两种镜像方式，构造出 1001、101
- 遍历两种镜像方式，注意大小顺序即可

解答

1
2
3
4
5
6
7
8
9


class Solution:
    def largestPalindrome(self, n: int) -> int:
        for odd in [0,1]:
            for h in range(10**n-1,10**(n-1)-1,-1):
                x = int(str(h)+str(h)[::-1][odd:])
                mi = max(10**(n-1),(x-1)//(10**n-1)+1)
                for y in range(mi,isqrt(x)+1):
                    if x%y==0:
                        return x%1337

1018 ms

目录

0479：最大回文数乘积（★★）

题目

分析

解答