leetcode 479. 最大回文数乘积

题目如下

看完题目后没有想到取巧的办法所以尝试使用枚举法。
使用枚举法之前先回答两个问题：
1. 如何构造回文串？
2. 如何判断是否存在两个n位整数相乘可以得到这个回文串？
显然n位数与n位数相乘必然是2n位数也就是说最大回文整数长度必然是2n，
所以我们只需要从pow(10，n+1)开始遍历直到pow(10，n) (实际上不用那么多因为这样的回文串很近)然后翻转构造回文串就行。
至于第二个问题也很容易判断一个数是否有除了1的因子只需要判断从这个数到开根号范围内是否存在可以整除的数就行。
所以综合两点可以写出枚举代码。

通过代码

class Solution {
public:int largestPalindrome(int n) {if(n == 1)return 9;  long long s = 9;long long ans;long long t;  for(int i = 1;i < n;i++) {s *= 10;s += 9;}s *= s;//s是n位数与n位数相乘的最大值for(int i = pow(10,n) - 1;i >= pow(10,n - 1);i--) {t = i;ans = i;for(int j = 0;j < n;j++) {ans *= 10;ans += (t % 10);t /= 10;}if(ans <= s) {for(int k = pow(10,n) - 1;k >= sqrt(ans);k--) {if(ans % k == 0)return  ans % 1337;}}} return ans % 1337; 
}
};

当然我们可以看到n是从1到8所以我们还可以使用打表的手法。

class Solution {
public:int largestPalindrome(int n) {if(n == 1)return 9;if(n == 2)return 987;if(n == 3)return 123;if(n == 4)return 597;if(n == 5)return 677;if(n == 6)return 1218;if(n == 7)return 877;if(n == 8)return 475;return 0;
}
};