最大回文数乘积Java
文章发布较早,内容可能过时,阅读注意甄别。
# 题目
给定一个整数 n ,返回 可表示为两个 n 位整数乘积的 最大回文整数 。
因为答案可能非常大,所以返回它对 1337 取余 。
示例 1:
输入:n = 2
输出:987
解释:99 x 91 = 9009, 9009 % 1337 = 987
示例 2:
输入: n = 1
输出: 9
提示:
- 1 <= n <= 8
# 思路
//提供一个简单的思路,首先通过最大上界max(n位数)得到一个最大乘积结果max × max(2n位数),
然后取前n位数作为初始值half。通过half去构造回文数,检查能否由处于上界和下界之间的两个数得到,如果不可以,则half--,重新构造回文数,再次判断
# 解法
class Solution {
public int largestPalindrome(int n) {
//提供一个简单的思路,首先通过最大上界max(n位数)得到一个最大乘积结果max × max(2n位数),然后取前n位数作为初始值half。通过half去构造回文数,检查能否由处于上界和下界之间的两个数得到,如果不可以,则half--,重新构造回文数,再次判断
if(n == 1){
return 9;
}
long max = (long)Math.pow(10,n)-1;
long min = (long)Math.pow(10,n-1);
long half = max*max/(min*10);
long val;
long temp;
while(true){
val = getVal(half);
for(long i = max ; i >= Math.sqrt(val) ; i--){
if(val % i == 0){
temp = val / i;
if(temp >= min && temp <= max){
return (int)(val % 1337);
}
}
}
half--;
}
}
public long getVal(long half){
StringBuilder sb = new StringBuilder();
return Long.parseLong(half+sb.append(half).reverse().toString());
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# 总结
- 分析出几种情况,然后分别对各个情况实现