479. 最大回文数乘积
题目描述:
给定一个整数 n,返回 可表示为 两个n位整数 乘积 的 最大回文整数 。
因为答案可能非常大，所以返回它对 1337 取余 。
例子1：
输入：n = 2
输出：987
解释：99 x 91 = 9009, 9009 % 1337 = 987
例子2：
输入： n = 1
输出： 9
题解：
超时:
func largestPalindrome1(n int) int { // eg: n=2 min := int(math.Pow10(n - 1)) // 10 max := int(math.Pow10(n) - 1) // 99 // 存放每个数的最大回文乘积 // eg: // n=2的时候 // [1001 888 1001 868 585 848 969 828 1881 777 2112 1771 // 2112 2002 999 2772 2552 2112 3003 2992 2772 3663 3003 // 2772 4224 4554 4224 3773 4004 4664 5445 4774 6336 5005 // 6336 6336 7227 5775 7007 8118 8448 9009] var AllPalindromeMaxSlice []int for i := min; i <= max; i++ { // 记录当前数的与其他数的乘积 为回文数的 结果 var myPalindrome []int j := i for j <= max { if palindrome(i * j) { myPalindrome = append(myPalindrome, i*j) } j++ } if len(myPalindrome) == 0 { continue } AllPalindromeMaxSlice = append(AllPalindromeMaxSlice, myPalindrome[len(myPalindrome)-1]) } sort.Ints(AllPalindromeMaxSlice) if len(AllPalindromeMaxSlice) == 0 { return 0 } return AllPalindromeMaxSlice[len(AllPalindromeMaxSlice)-1] % 1337 } func palindrome(x int) bool { t := x c := 0 // 数值反转 for t > 0 { // t%10 取个位 c = c*10 + t%10 // 抛弃个位 t = t / 10 } return c == x }
正解：
func largestPalindrome(n int) int { // n = 1 // 1-->9 1~81 // 77 66 55 44 33 22 11 // 可以看到这些都是1个一位数和1个二位数的乘积，不满足题意 if n == 1 { return 9 } // 上下界限 upperBound := int(math.Pow10(n)) - 1 lowerBound := upperBound/10 + 1 // 最大值 maxNumber := upperBound * upperBound // 9801 half := maxNumber / int(math.Pow10(n)) // maxNumber的前半部分 9889 ———> 98 // 是否找到了回文串 found := false // 结果 res := 0 for !found { res = createPalindrome(half) // 从高往低去看 for i := upperBound; i >= lowerBound; i-- { // 意味着在遍历过程中i的值太小了 if i*i<res { break } if res%i==0 { found = true break } } half-- } return res % 1337 } // 根据左半部分生成回文串 func createPalindrome(half int) int { t := half for x := half; x > 0; x /= 10 { t = t*10 + x%10 } return t }
