LeetCode479 Largest Palindrome Product

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

Find the largest palindrome made from the product of two n-digit numbers.

Since the result could be very large, you should return the largest palindrome mod 1337.

Note:

The range of n is [1,8].

样例

1
2
3
4
5
6
Input: 
2
Output:
987
Explanation:
99 x 91 = 9009, 9009 % 1337 = 987

思路

找出两个$n$位数乘积中最大的回文数。

首先,乘积的范围为$[10^{n-1} \cdot 10^{n-1}, (10^{n} - 1) \cdot (10^{n} - 1)]$,暴力的方法是遍历每一个数,检查是否为回文的,然后记录其中最大值。复杂度:$\mathcal{O}(10^{2n})$

一个可以优化的地方是,不再枚举所有的数,而是枚举所有的回文数,然后再判断这个回文数能否被分解为两个$n$位数的乘积。基于一个事实,两个$n$位数$(2 \le n \le 8)$乘积中最大的回文数的位数为$2n$位(本弱不会证明…)。所以只需枚举回文数的左半部分,然后再构造出回文数判断。复杂度:$\mathcal{O}(10^{1.5n})$

虽然理论复杂度比较高,但是因为是从大到小枚举,很快便能得到答案,实测只跑了300+ms。

当然,这题还可以本地打表交上去。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
long long palindrome(int x) {
long long ret = x;
while (x) {
ret = ret * 10 + x % 10;
x /= 10;
}
return ret;
}
int largestPalindrome(int n) {
if (n == 1) return 9;
long long l = pow(10, n - 1), r = pow(10, n) - 1;
for (int i = r; i >= l; --i) { // 枚举回文数左半部分
long long p = palindrome(i); // 构造回文数
for (long long j = r; j * j >= p; --j) {
// 判断p能否分解为两个n位数的乘积
// j为其中较大者,故只需枚举到j * j >= p
if (p % j == 0) return p % 1337;
}
}
}
};
分享到 评论