479. 最大回文数乘积 - 每日一题

479. 最大回文数乘积 - 力扣（LeetCode） (leetcode-cn.com)

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

示例 1:

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

输入： n = 1
输出： 9

提示:

• 1 <= n <= 8

要点：

• 要知道什么事回文数。leetcode有很多关于回文数或者回文字符串的题，做一个就知道了
• 回文数就是从前往后 和 从后往前看，结果都是一样的

构造回文数

给你个 n ，返回 两个 n 位整数所有的回文数

      long a = (long) (Math.pow(10, n) - 1);
     // 从大到小构造回文数
      for (long i = a; i >= 0 ; i--) {
            long num = i;
            for (long j = i; j > 0 ; j /= 10) {
                num = num * 10 + j % 10;
            }
            System.out.println(num);
        }

最终答案

public int largestPalindrome(int n) {
        if (n == 1) {
            return 9;
        }
        long a = (long) (Math.pow(10, n) - 1);
        for (long i = a; i >= 0; i--) {
            //从大到小构造回文串
            long number = i;
            for (long j = i; j > 0; j /= 10) {
                number = number * 10 + j % 10;
            }
            //判断number是否为满足条件的最大回文串
            //每次循环都从最大n位开始判断，循环判断条件为 k*k >= number
            //为什么k*k小于number就不用判断了，因为如果k*k小于number依旧存在number%k == 0，说明绝对出现了一个
            //（大于k的数）*（一个小于k的）等于该number,而在（大于k的数）*（大于k的数）> number时就满足条件(number%(大于k的数）== 0  return掉了),所以k*k小于number了就一定不存在number % k ==0;
            for (long k = a; k * k >= number; k--) {
                if (number % k == 0) {
                    return (int) (number % 1337);
                }
            }
        }
        return -1;
    }

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/largest-palindrome-product
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。