LeetCode264. 丑数 II(相关话题：多重指针动态规划)-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode264. 丑数 II(相关话题：多重指针动态规划)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述

给你一个整数 n ，请你找出并返回第 n 个丑数。丑数就是质因子只包含 2、3 和 5 的正整数。

示例 1：

输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。

示例 2：

输入：n = 1
输出：1
解释：1 通常被视为丑数。

提示：

1 <= n <= 1690

解题思路

动态规划数组：dp 数组用于存储从第 1 个到第 n 个丑数。dp[0] 初始化为 1，因为第一个丑数定义为 1。
三个指针：p2、p3、p5 分别表示下一个丑数是当前指向的丑数乘以 2、3 或 5。开始时，这三个指针都指向第一个丑数。
生成新的丑数：在每一步中，计算 dp[p2] * 2、dp[p3] * 3 和 dp[p5] * 5，并取这三个值中的最小值作为新的丑数。这保证了丑数序列的有序性。
更新指针：如果当前丑数是由某个指针生成的（即等于该指针对应的乘积），则将该指针后移一位。这样做是为了确保每个指针都能继续参与生成更大的丑数。
结果：循环结束后，dp[n-1] 存储的是第 n 个丑数。

a队列1,2,3,4,5,6,8

b队列1,2,3,4,5

c 队列1,2,3

生成新丑数的过程：在每一步中，代码通过比较 dp[a] * 2、dp[b] * 3 和 dp[c] * 5 来决定下一个丑数是哪个。这相当于从三个队列中选出最小的数：文章来源地址https://www.toymoban.com/news/detail-808814.html

一个队列是当前丑数乘以 2 的结果。
另一个队列是当前丑数乘以 3 的结果。
第三个队列是当前丑数乘以 5 的结果。

代码实现

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        dp = [0] * n  # 初始化DP数组，用于存储丑数
        dp[0] = 1     # 第一个丑数是1

        # 初始化三个指针，分别对应乘以2、3和5的情况
        a, b, c = 0, 0, 0

        for i in range(1, n):
            # 选出当前可以生成的最小丑数
            dp[i] = min(dp[a] * 2, dp[b] * 3, dp[c] * 5)

            # 更新指针，如果当前丑数由某个指针生成，则该指针后移
            if dp[i] == dp[a] * 2: a += 1
            if dp[i] == dp[b] * 3: b += 1
            if dp[i] == dp[c] * 5: c += 1

        return dp[n-1]  # 返回第n个丑数

到了这里，关于LeetCode264. 丑数 II(相关话题：多重指针动态规划)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！