题源

• 479. 最大回文数乘积

知识点

• 枚举 + 数学
• 暴力

思路

• 虽然这道题目是暴力，但是暴力有两种：
  • 第一种：先2个n位数乘积，然后判断是否为回文整数。
  • 第二种：枚举从大到小的回文整数，再去判断是否可以被整除。
• 我选的是第二种，第一种我也不知道能不能过。

代码

python

class Solution:
    def largestPalindrome(self, n: int) -> int:
        if n == 1:
            return 9
        start, end = 10 ** (n - 1), 10 ** n - 1
        for num1 in range(end, start, -1):
            max_palindrome = int(str(num1) + str(num1)[::-1]) # 构造回文数
            for num2 in range(end, start, -1):
                if num2 * end <= max_palindrome:
                    break
                if(max_palindrome % num2 == 0):
                    return max_palindrome % 1337

执行用时：5348 ms, 在所有 Python3 提交中击败了5.37%的用户
内存消耗：14.9 MB, 在所有 Python3 提交中击败了36.40%的用户

javascript

• 除法会产生小数，不会像C一样直接得到整型；
• js超过16位，计算时数字就会损失精度，需要用BigInt数据类型。

/**
 * @param {number} n
 * @return {number}
 */
var largestPalindrome = function(n) {
    if(n === 1) return 9
    const [max, min] = [10 ** n - 1, 10 ** (n - 1)]   // 比如说n === 3 即 [max, min] = [999, 100]
    for(let num1 = max; num1 >= min; num1--){
        let palindromeNumber = BigInt(num1 + String(num1).split('').reverse().join(''))
        for(let num2 = BigInt(max); num2 * num2 >= palindromeNumber; num2--){
            if(palindromeNumber % num2 === BigInt(0)) return palindromeNumber % BigInt(1337)
        }
    }
};

执行用时：8276 ms, 在所有 JavaScript 提交中击败了14.29%的用户
内存消耗：46.8 MB, 在所有 JavaScript 提交中击败了57.14%的用户

java

class Solution {
    public int largestPalindrome(int n) {
        if(n == 1) return 9;
        long start = this.pow(n - 1), end = this.pow(n) - 1;
        for(long num1 = end; num1 > start; num1--){
            long  palindrome = this.toPalindrome(num1);
            for(long num2 = end; num2 * num2 > palindrome; num2--){
                if(palindrome % num2 == 0) return (int)(palindrome % 1337);
            }
        }
        return 9;
    }
    public long toPalindrome(long num){
        long result = num;
        while(num > 0){
            result *= 10;
            result += num % 10;
            num /= 10;
        }
        return result;
    }

    public long pow(int n){
        long result = 1;
        for(int i = 0; i < n; i++) result *= 10;
        return result;
    }
}

执行用时：88 ms, 在所有 Java 提交中击败了73.81%的用户
内存消耗：38.3 MB, 在所有 Java 提交中击败了50.89%的用户

C

long myPow(int n){
    long sum = 1;
    for(int i = 0;i < n; i++){
        sum *= 10;
    }
    return sum;
}

long toPalindrome(long num){
    long result = num;
    while(num){
        result *= 10;
        result += num % 10;
        num /= 10;
    }
    return result;
}

int largestPalindrome(int n){
    if(n == 1) return 9;
    long start = myPow(n - 1), end = myPow(n) - 1;
    for(long num1 = end; num1 > start; num1 --){
        long palindrome = toPalindrome(num1);
        for(long num2 = end; num2 * num2 >= palindrome; num2--){
            if(palindrome % num2 == 0) return palindrome % 1337;
        }
    }
    return 9;
}

执行用时：88 ms, 在所有 C 提交中击败了53.33%的用户
内存消耗：5.4 MB, 在所有 C 提交中击败了80.00%的用户