LeetCode 479题是关于寻找最大的回文数乘积的问题。题目要求我们找到两个n位数相乘得到的最大的回文数。下面我将详细解释题目的要求、解题思路以及具体的代码实现。

题目描述

给定一个整数n，返回两个n位数的乘积中的最大回文数。如果没有找到，则返回0。

解题思路

1. 定义回文数：回文数是指从左到右和从右到左读都相同的数，例如121、12321等。
2. 生成n位数：首先需要生成所有可能的n位数。
3. 寻找最大回文数乘积：通过双重循环遍历所有可能的n位数对，计算它们的乘积，并检查是否为回文数。记录最大的回文数乘积。

具体步骤

1. 生成n位数：可以通过计算10^(n-1)到10^n-1之间的所有数来生成n位数。
2. 检查回文数：编写一个函数来判断一个数是否为回文数。
3. 遍历并记录最大回文数乘积：使用双重循环遍历所有n位数对，计算乘积并检查是否为回文数，记录最大的回文数乘积。

代码实现

以下是Python代码实现：

class Solution: def largestPalindrome(self, n: int) -> int: if n == 1: return 9

    # 生成n位数的范围
    start = 10**(n-1)
    end = 10**n - 1

    # 检查是否为回文数的函数
    def is_palindrome(num):
        return str(num) == str(num)[::-1]

    max_palindrome = 0

    # 遍历所有可能的n位数对
    for i in range(end, start - 1, -1):
        for j in range(i, start - 1, -1):
            product = i * j
            if is_palindrome(product):
                max_palindrome = max(max_palindrome, product)

    return max_palindrome

sol = Solution() print(sol.largestPalindrome(2)) # 输出: 9009 (91 * 99)

优化思路

上述代码虽然能够解决问题，但时间复杂度较高，为O(n^2 * 10^(2n))。可以通过以下方法进行优化：

1. 数学性质：利用回文数的数学性质，例如回文数可以表示为a * 10^n + b，其中b是a的逆序数。
2. 减少遍历范围：由于乘积是对称的，可以减少遍历的范围。

优化后的代码

class Solution: def largestPalindrome(self, n: int) -> int: if n == 1: return 9

    upper_limit = 10**n - 1
    lower_limit = 10**(n-1)

    for i in range(upper_limit, lower_limit - 1, -1):
        # 构造回文数
        palindrome = int(str(i) + str(i)[::-1])
        # 从大到小尝试除以n位数
        for j in range(upper_limit, lower_limit - 1, -1):
            if palindrome // j > upper_limit:
                break
            if palindrome % j == 0:
                return palindrome

    return 0

sol = Solution() print(sol.largestPalindrome(2)) # 输出: 9009 (91 * 99)

总结

通过上述方法，我们可以有效地找到两个n位数相乘得到的最大回文数。优化后的代码利用了回文数的数学性质，减少了遍历的范围，提高了效率。希望这个详细的解答对你有所帮助！如果有更多问题，欢迎继续提问。