题目
给定一个整数 n ,返回 可表示为两个 n 位整数乘积的 最大回文整数 。因为答案可能非常大,所以返回它对 1337 取余 。
示例
示例 1:
输入:n = 2 输出:987
解释:99 x 91 = 9009, 9009 % 1337 = 987
示例 2:
输入: n = 1 输出: 9
思路
由于数据量较大并且从乘数的角度不好考虑策略,可以从回文乘积这一角度考虑该题。
两个n位数相乘,位数位2n-1或者2n,由于题目要求最大值,这里我们都是用位数位2n的回文乘积,我们可以从大到小列出n位数,由这个n位数从大到小整合出回文乘积。
再从n到1判断是否由乘数相乘等于该回文数,如果有直接返回,没有接着往下执行,直到找到最大的回文乘积。
由于该题目类型为输入为一个整数,输出也为一个整数,我们直接写程序时间复杂度比较高,可以采取打表的策略来提高效率(前提是你得写对题解保证你的答案都是正确的)。
代码
一般解:
# 最大回文数乘积 def largestPalindrome(n): if n == 1: return 9 res = 0 max_num = pow(10, n) - 1 for i in range(max_num, 0, -1): for j in range(i, 0, -1): use = int(str(j) + str(j)[::-1]) print(use) for k in range(max_num, 0, -1): if k ** 2 < use: break if use % k == 0: res = use % 1337 return res return res
打表:
def largestPalindrome(self, n: int) -> int: res = [9,987,123,597,677,1218,877,475] return res[n-1]