479. 最大回文数乘积

题目描述

给定一个整数 n ，返回可表示为两个 n 位整数乘积的 最大回文整数 。因为答案可能非常大，所以返回它对 1337 取余。

示例 1：

输入：n = 2
输出：987
解释：99 x 91 = 9009, 9009 % 1337 = 987

示例 2：

输入：n = 1
输出：9

提示:

1 <= n <= 8

解法

方法一

思考

求两个 \(n\) 位整数乘积中最大的回文，再模 \(1337\)。\(n\le 8\)，枚举所有乘积再判回文过大。

从大到小枚举回文的前半 \(a\)，镜像得到回文 \(x\)，再检查是否存在 \(n\) 位因子 \(t\)（从 \(10^n-1\) 向下，\(t^2\ge x\)）。第一个成功的 \(x\) 即为最大。

先构造回文再试因子，比枚举乘积更早遇到最大值。\(n=1\) 的哨兵返回 \(9\)。

Python3JavaC++Go

class Solution:
    def largestPalindrome(self, n: int) -> int:
        mx = 10**n - 1
        for a in range(mx, mx // 10, -1):
            b = x = a
            while b:
                x = x * 10 + b % 10
                b //= 10
            t = mx
            while t * t >= x:
                if x % t == 0:
                    return x % 1337
                t -= 1
        return 9

class Solution {
    public int largestPalindrome(int n) {
        int mx = (int) Math.pow(10, n) - 1;
        for (int a = mx; a > mx / 10; --a) {
            int b = a;
            long x = a;
            while (b != 0) {
                x = x * 10 + b % 10;
                b /= 10;
            }
            for (long t = mx; t * t >= x; --t) {
                if (x % t == 0) {
                    return (int) (x % 1337);
                }
            }
        }
        return 9;
    }
}

class Solution {
public:
    int largestPalindrome(int n) {
        int mx = pow(10, n) - 1;
        for (int a = mx; a > mx / 10; --a) {
            int b = a;
            long x = a;
            while (b) {
                x = x * 10 + b % 10;
                b /= 10;
            }
            for (long t = mx; t * t >= x; --t)
                if (x % t == 0)
                    return x % 1337;
        }
        return 9;
    }
};

func largestPalindrome(n int) int {
    mx := int(math.Pow10(n)) - 1
    for a := mx; a > mx/10; a-- {
        x := a
        for b := a; b != 0; b /= 10 {
            x = x*10 + b%10
        }
        for t := mx; t*t >= x; t-- {
            if x%t == 0 {
                return x % 1337
            }
        }
    }
    return 9
}

479. 最大回文数乘积

题目描述

解法

方法一

评论