当前位置：首页 > article >正文

【LeetCode】剑指 Offer（25）

article 2025/2/28 23:40:37

题目：剑指 Offer 49. 丑数 - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过啦！！！

写在最后：

题目：剑指 Offer 49. 丑数 - 力扣（Leetcode）

题目的接口：

class Solution {
public:
    int nthUglyNumber(int n) {

    }
};

解题思路：

丑数这道题用到一点动态规划的思想，

具体思路如下：

根据题意：

如果说第一个丑数是一，包含质因子 2、3 和 5 的数称作丑数，

那么我们发现，之后的丑数：

1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

都是前面的丑数乘2、乘3或者乘5 得来的，

那我们的思路就能变成：

从第一个数1开始，让他乘2、乘3、乘5，

第二个数也这样操作，

然后取他们的最小值作为下一个丑数，

以此类推，

三个指针，分别用来乘2、乘3、乘5，

取得最小值的那个指针指向下一个数，

如果出现两个数相等的情况，

例：

2 * 5 == 5 * 2

那就两个指针都指向下一个数，

防止重复，

最后返回第n个丑数即可。

例：

根据规则：从第一个数1开始，让他乘2、乘3、乘5

一乘二，指针往后走一个：

一乘三，指针往后走一个：

这个时候，二乘二比一乘五更小，

所以这里走的是二乘二：

然后是一乘五：

以此类推，就能计算出之后的丑数了。

下面是代码：

代码：

class Solution {
public:
    int nthUglyNumber(int n) {
        //创建n + 1大小的数组
        vector<int> dp(n + 1);

        //初始化三指针   
        int a = 0, b = 0, c = 0;

        //数组从1开始
        dp[0] = 1;

        //循环
        for(int i = 1; i < n; i++)
        {
            //让三指针*2 *3 *5 并选出最小值，就是下一个丑数
            int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;

            //取最小值
            dp[i] = min(min(n2, n3), n5);

            //如果该下标对应的数是下一个丑数，就让指针指向下一个
            //如果有两个数结果相同，就让那两个指针都指向下一个
            //防止重复
            if(n2 == dp[i])
            {
                a++;
            }
            if(n3 == dp[i])
            {
                b++;
            }
            if(n5 == dp[i])
            {
                c++;
            }
        }
        //最后返回第n个丑数
        return dp[n - 1];
    }
};