LeetCode每日一题(1)——最大回文数乘积

简介: LeetCode每日一题(1)最大回文数乘积1.题目2.示例3.思路1.生成位数符合要求的递减的回文数2.判断回文数是否符合要求4.代码5.复杂度分析

1.题目


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


2.示例


示例 1:


输入:n = 2 输出:987

解释:99 x 91 = 9009, 9009 % 1337 = 987


示例 2:


输入: n = 1 输出: 9


提示:


1 <= n <= 8


3.思路


要求两个n位整数乘积的最大回文整数,从两个n位乘数入手寻找乘积为回文数又是最大的明显很难实现。

而从回文数入手可以从最大的回文数开始尝试能否由两个符合要求的乘数得到。


1.生成位数符合要求的递减的回文数


(易知n位数乘以n位数积最大为2n位,同时n位乘数最大为10的n次方减一),通过两层循环生成递减的回文数:


  key := int(math.Pow10(n)) - 1
    for num := key; num > 0; num-- {
        t := num 
        for side := t; side > 0; side /= 10 {
            t = t*10 + side%10
        }
        //判断此回文数是否可由2个n位数乘得
     }


2.判断回文数是否符合要求


for test := key; test*test > t ;test--{
            if t/test <= key && t%test == 0{
                return t%1337
            }
        }


满足t/test <= key && t%test == 0 可证明t可被test和另一满足要求的数乘得


4.代码


func largestPalindrome(n int) int {
    if n == 1{
        return 9
    }
    key := int(math.Pow10(n)) - 1
    for num := key; num > 0; num-- {
        t := num 
        for side := t; side > 0; side /= 10 {
            t = t*10 + side%10
        }
        for test := key; test*test > t ;test--{
            if t/test <= key && t%test == 0{
                return t%1337
            }
        }
    }
    return 0
    //for循环里一定会return,但是这里不写return力扣报错,就随便写了个0,但是官方没写的就可以通过,who知道为啥踢我一下
}


5.复杂度分析


时间复杂度:O(10^{2n})

空间复杂度:O(1)

相关文章
|
29天前
DAY-4 | 力扣 - 求自身以外数组的乘积:区间划分,左右累乘,巧求乘积
该文档是关于LeetCode上的一道题目“Product of Array Except Self”的题解。提供了两种解题方法,一是暴力破解,即计算所有数的乘积后再逐个除以当前元素;二是左右累乘法,通过两次遍历数组分别计算左侧和右侧元素的乘积,避免了除法操作。其中,左右累乘法更优,代码实现中展示了这种方法。
24 1
|
9天前
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
|
1月前
leetcode代码记录(回文数
leetcode代码记录(回文数
18 1
|
25天前
题目----力扣--回文链表
题目----力扣--回文链表
20 0
|
26天前
|
索引
【力扣刷题】回文链表、环形链表、合并两个有序链表
【力扣刷题】回文链表、环形链表、合并两个有序链表
20 0
|
1月前
【力扣】238. 除自身以外数组的乘积
【力扣】238. 除自身以外数组的乘积
|
1月前
【力扣】409.最长回文串
【力扣】409.最长回文串
|
1月前
|
C语言 C++ 索引
【力扣】141. 环形链表、160. 相交链表、206.反转链表、234. 回文链表
【力扣】141. 环形链表、160. 相交链表、206.反转链表、234. 回文链表
|
1月前
【力扣】9. 回文数
【力扣】9. 回文数
|
1月前
|
算法 C++ 索引
【力扣经典面试题】238. 除自身以外数组的乘积
【力扣经典面试题】238. 除自身以外数组的乘积