LeetCode 479. Largest Palindrome Product
本博客转载自:http://www.cnblogs.com/grandyang/p/7644725.html
Solution1:我的答案
暴力解法,当n = 4时就超时了。只是记录一下……
class Solution {
public:
int largestPalindrome(int n) {
long long res = 0;
set<long long> res_set;
int min = pow(10, n - 1), max = pow(10, n) - 1;
for (int i = min; i <= max; i++) {
for (int j = min; j <= max; j++) {
res = (long long)i * j;
if (isPalin(res))
res_set.insert(res);
}
}
return *(--res_set.end()) % 1337;
}
bool isPalin(long long n) {
string n_str = to_string(n);
string n_str_copy = n_str;
reverse(n_str_copy.begin(), n_str_copy.end());
if (n_str_copy == n_str)
return true;
else
return false;
}
};
Solution2:
参考网址:http://www.cnblogs.com/grandyang/p/7644725.html
算法关键:
当n>1时,2个n位数乘积的最大回文数一定是2n位的
当
n
>
1
时
,
2
个
n
位
数
乘
积
的
最
大
回
文
数
一
定
是
2
n
位
的
思路:先找出这个回文数,然后判断其是否能由两个n位数的乘积得到!
首先我们还是要确定出n位数的范围,最大值upper,可以取到,最小值lower,不能取到。然后我们遍历这区间的所有数字,对于每个遍历到的数字,我们用当前数字当作回文数的前半段,将其翻转一下拼接到后面,此时组成一个回文数,这里用到了一个规律,当n>1时,两个n位数乘积的最大回文数一定是2n位的。下面我们就要来验证这个回文数能否由两个n位数相乘的来,我们还是遍历区间中的数,从upper开始遍历,但此时结束位置不是lower,而是当前数的平方大于回文数,因为我们遍历的是相乘得到回文数的两个数中的较大数,一旦超过这个范围,就变成较小数了,就重复计算了。比如对于回文数9009,其是由99和91组成的,其较大数的范围是[99,95],所以当遍历到94时,另一个数至少需要是95,而这种情况在之前已经验证过了。当回文数能整除较大数时,说明是成立的,直接对1337取余返回即可,参见代码如下:
class Solution {
public:
int largestPalindrome(int n) {
int upper = pow(10, n) - 1, lower = upper / 10;
for (int i = upper; i > lower; --i) {
string t = to_string(i);
long p = stol(t + string(t.rbegin(), t.rend()));
for (long j = upper; j * j >= p; --j) {
if (p % j == 0) return p % 1337;
}
}
//当n = 1时,两个1位数乘积范围在[1, 81]之间,
//显然{77,66,55,44,33,22,11}这些数不能由两个1位数
//相乘得到,退出上面的循环后,直接返回9
return 9;
}
};