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

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

题目

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

示例

示例 1:

输入:n = 2 输出:987

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

示例 2:

输入: n = 1 输出: 9

思路

由于数据量较大并且从乘数的角度不好考虑策略,可以从回文乘积这一角度考虑该题。

两个n位数相乘,位数位2n-1或者2n,由于题目要求最大值,这里我们都是用位数位2n的回文乘积,我们可以从大到小列出n位数,由这个n位数从大到小整合出回文乘积。

再从n到1判断是否由乘数相乘等于该回文数,如果有直接返回,没有接着往下执行,直到找到最大的回文乘积。

由于该题目类型为输入为一个整数,输出也为一个整数,我们直接写程序时间复杂度比较高,可以采取打表的策略来提高效率(前提是你得写对题解保证你的答案都是正确的)。

代码

一般解:

# 最大回文数乘积
def largestPalindrome(n):
    if n == 1:
        return 9
    res = 0
    max_num = pow(10, n) - 1
    for i in range(max_num, 0, -1):
        for j in range(i, 0, -1):
            use = int(str(j) + str(j)[::-1])
            print(use)
            for k in range(max_num, 0, -1):
                if k ** 2 < use:
                    break
                if use % k == 0:
                    res = use % 1337
                    return res
    return res

打表:

    def largestPalindrome(self, n: int) -> int:
        res = [9,987,123,597,677,1218,877,475]
        return res[n-1]
目录
相关文章
|
3月前
|
Go
【LeetCode 热题100】DP 实战进阶:最长递增子序列、乘积最大子数组、分割等和子集(力扣300 / 152/ 416 )(Go语言版)
本文深入解析三道经典的动态规划问题:**最长递增子序列(LIS)**、**乘积最大子数组** 和 **分割等和子集**。 - **300. LIS** 通过 `dp[i]` 表示以第 `i` 个元素结尾的最长递增子序列长度,支持 O(n²) 动态规划与 O(n log n) 的二分优化。 - **152. 乘积最大子数组** 利用正负数特性,同时维护最大值与最小值的状态转移方程。 - **416. 分割等和子集** 转化为 0-1 背包问题,通过布尔型 DP 实现子集和判断。 总结对比了三题的状态定义与解法技巧,并延伸至相关变种问题,助你掌握动态规划的核心思想与灵活应用!
136 1
|
11月前
|
算法
LeetCode回文数(暴力解,求更好的思路)
这篇博客讨论了如何判断一个整数是否为回文数,提供了暴力解法的代码,并寻求更优的算法建议。
120 1
LeetCode回文数(暴力解,求更好的思路)
LeetCode第9题回文数
该文章介绍了 LeetCode 第 9 题回文数的解法,通过分析回文数的特征,只需反转一半数字进行比较即可,时间复杂度可降至 O(n/2),并总结了该题与整数反转有关,需根据回文数特征来解决。
LeetCode第9题回文数
|
算法 Java 索引
LeetCode初级算法题:寻找数组的中心索引+x的平方根+三个数的最大乘积+Leetcode 149:直线上最多的点数 Java详解
LeetCode初级算法题:寻找数组的中心索引+x的平方根+三个数的最大乘积+Leetcode 149:直线上最多的点数 Java详解
93 0
|
Python
【Leetcode刷题Python】318. 最大单词长度乘积
本文提供了LeetCode题目318的Python编程解决方案,题目要求在一个字符串数组中找出两个不含有公共字母的单词,且这两个单词的长度乘积最大,如果不存在这样的两个单词,则返回0。
81 0
|
Python
【Leetcode刷题Python】234.回文链表
两种判断链表是否为回文的方法:使用栈和拆分为两个链表后反转对比,并给出了相应的Python代码实现。
101 0
DAY-4 | 力扣 - 求自身以外数组的乘积:区间划分,左右累乘,巧求乘积
该文档是关于LeetCode上的一道题目“Product of Array Except Self”的题解。提供了两种解题方法,一是暴力破解,即计算所有数的乘积后再逐个除以当前元素;二是左右累乘法,通过两次遍历数组分别计算左侧和右侧元素的乘积,避免了除法操作。其中,左右累乘法更优,代码实现中展示了这种方法。
116 1
leetcode代码记录(回文数
leetcode代码记录(回文数
124 1
【力扣】238. 除自身以外数组的乘积
【力扣】238. 除自身以外数组的乘积
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积