LeetCode 479. 最大回文数乘积
2023-3-23
| 2023-3-23
0  |  阅读时长 0 分钟
Created time
Apr 20, 2022 12:16 PM
date
status
category
Origin
summary
tags
type
URL
icon
password
slug

最大回文数乘机积

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

Largest Palindrome Product

Given an integer n, return the largest palindromic integer that can be represented as the product of two n-digits integers. Since the answer can be very large, return it modulo 1337.
  • 1 <= n <= 8
这题是一个比较玄学的问题,它其实是一个暴力枚举 。 但是它的这个时间复杂度虽然看似很高,但是这道题目本身就是一个暴力,虽然最坏时间复杂度很高,但是我们通过实际操作却发现答案很快就可以算出来,是这样的一种题。我们先看这道题是什么意思:给我们一个n, 让我们找一下所有由两个n位数组成乘积的数里面最大的一个回文数是多少?
这个n位数是什么呢?比如当三位数n=3的时候就是100~999里面所有两个三位数的乘积里面最大的一个回文数是多少;当两位数n=2的时候就是10~99里面所有两个两位数的乘积里面最大的一个回文数是多少,样例给出了是99 x 91 = 9009,最后返回的这个最大的回文数根据题目的要求模上1337就是答案987。
这种题的输入范围是很小的所以可以直接打表,在力扣的评测机里面直接输入1~9就可以评测出答案{9,987,123,597,677,1218,877,475},最后根据要求直接返回即可。注意考试的时候打表没有问题,但是在面试的时候如果遇到面试官不允许的话就无法打表了。
那这题该怎么做呢?这题可能有同学会想有没有能够优化的做法,答案是没有的,我们直接暴力去做就可以了。因为大家试过一遍就可以发现答案其实很快就可以找到(虽然他的时间复杂度很大,但是巧在他的答案都分布在遍历刚开始没多久的区域,所以我们很快就可以得到答案,所以说这题很玄学,但是这题根据网上的信息在面试中很少遇到,所以大家图一乐就好)。
首先枚举的时候我们得想一下怎么暴力,你不能写那种一看就会超时的暴力(比如从小往大枚举,也不剪去绝对不正确的情况一直枚举到最大,相信很多科班的同学第一次优化暴力枚举是在谭浩强的c语言程序设计上面求质数的那道题吧,与这道题有异曲同工之妙),又或者是枚举两个数然后去判断它的回文串的话这种就比较慢了,可能会超时。那么这题我们这么枚举呢,也就是这题出题的精髓和本质,就是从大到小去枚举回文数,从大到小枚举回文数的话其实只需要枚举一半就可以了。为什么只需要枚举一半就可以了呢,因为回文数左右两边其实是一样的,枚举左边右边就有了,所以我们这题其实是枚举回文数,从大到小枚举回文数其实就是从大到小枚举答案。比如说等于3的时候,就是从999999开始枚举,判断一下这个数能不能整除一下999并且整除之后的这个数也是n位数,如果是的话就成功了,反之就失败了继续枚举下一个数998899能不能分成两个n位数相乘,我们同样从999开始,这里需要注意的是我们必须保证999的平方必须大于等于998899才可以,因为如果小于998899的话那么就意味着我们另外一个数必然不是三位数,所以我们从最大数开始枚举的时候我们要求999的平方必须要大于等于998899才行。这样的话其实就是相当于我们每次枚举较大的那个数,因为两个数相乘,n如果可以分成两个n位数相乘的话(假设为a和b且a大于等于b),那么a和b其实是没有顺序的是吧,但是我们每次枚举的是枚举较大的那个数也就是枚举a,此时有a^2>=a*b=n也就是a的平方要大于等于n。
所以我们再去做的时候要求:
  • 最大数开始枚举
  • n位数最大数的平方一定要大于等于我们枚举的这个数
然后这里面的边界问题,就是说两个n位数相乘的话它得到的数不一定是2n位也有可能是2n-1位,比如说100✖️100=10000是五位数,但是999✖️999=998001这个就是是一个六位数,经过实验可以发现在2~8的范围内,最大数字必定是2n位,所以在2n位数里面一定是有答案的。如果n=1的话口算一下只有3的平方等于9,所以特判一下n=1的情况就可以了,所以这题就暴力去做。还是那句经典的话,虽然看似这道题目的暴力的情况下跟慢,但是其实很快就可以找到答案。然后是代码实现:
时间复杂度:。枚举left 和 x 的时间复杂度均为 。实际上我们只需要枚举远小于 个的left 就能找到答案,实际的时间复杂度远低于
空间复杂度:O(1),我们只需要常数的空间保存若干变量。
最后提供文中提到过的有趣的打表的方法的程序实现:
LeetCode 442. 数组中重复的数据LeetCode 386. 字典序排数
Loading...