479.最大回文数乘积
479.最大回文数乘积
题解
题目：给一个n，表示两个n位数相乘，求两个n位数相乘得到的最大回文数，并对回文数取模
思路：
- 从大到小枚举回文数
- 例：n=2，从9999开始枚举
- 既然是回文数，直接枚举左半，构造右半即可，9999 9889 9779…
- 判断这个回文数能否被两个n位数的数相乘得到
- 两位数最小1001，10 * 10 < 1001，所以x*x >= p，x一定满足是n位数
- 如果p%x==0，说明x是p的因子，返回p即可
代码
func largestPalindrome(n int) int { //特判 if n == 1 { return 9 } //最大n位数 2->99 3->999 upper := int(math.Pow10(n) - 1) //枚举回文数左半部分 for left := upper; left > 0; left-- { //构造回文数p p := left for x := left; x > 0; x = x / 10 { p = p*10 + x%10 //翻转左半部分到其自身末尾 } //枚举两个数相乘 for x := upper; x*x >= p; x-- { if p%x == 0 { // x 是 p 的因子 return p % 1337 } } } return 0 }
