LeetCode每日一题（1）——最大回文数乘积

2023-02-14 91

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 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)