題目如下

看完題目后沒(méi)有想到取巧的辦法所以嘗試使用枚舉法。
使用枚舉法之前先回答兩個(gè)問(wèn)題：
1. 如何構(gòu)造回文串？
2. 如何判斷是否存在兩個(gè)n位整數(shù)相乘可以得到這個(gè)回文串？
顯然n位數(shù)與n位數(shù)相乘必然是2n位數(shù)也就是說(shuō)最大回文整數(shù)長(zhǎng)度必然是2n，
所以我們只需要從pow(10，n+1)開(kāi)始遍歷直到pow(10，n) (實(shí)際上不用那么多因?yàn)檫@樣的回文串很近)然后翻轉(zhuǎn)構(gòu)造回文串就行。
至于第二個(gè)問(wèn)題也很容易判斷一個(gè)數(shù)是否有除了1的因子只需要判斷從這個(gè)數(shù)到開(kāi)根號(hào)范圍內(nèi)是否存在可以整除的數(shù)就行。
所以綜合兩點(diǎn)可以寫(xiě)出枚舉代碼。

通過(guò)代碼

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位數(shù)與n位數(shù)相乘的最大值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; 
}
};

當(dāng)然我們可以看到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;
}
};