Leetcode 丑数总结

发表于 更新于 分类于 Waline：

最近leetcode的每日一题开始了丑数的系列，做了几道，来总结一下。

丑数I - Easy

题目链接：https://leetcode-cn.com/problems/ugly-number/

这个题目没什么好说的，大家看下题目应该就知道怎么做了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number} n
 * @return {boolean}
 */
var isUgly = function(n) {
    if (n <= 0) {
        return false;
    }
    const factors = [2, 3, 5];
    for (const factor of factors) {
        while (n % factor === 0) {
            n /= factor;
        }
    }
    return n == 1;
};

丑数II - Medium

题目链接

https://leetcode-cn.com/problems/ugly-number-ii/

这个题目就有点意思了。

最小堆

要得到从小到大的第 n 个丑数，可以使用最小堆实现。

初始时堆为空。首先将最小的丑数 1 加入堆。

每次取出堆顶元素 x，则 x 是堆中最小的丑数，由于 2x, 3x, 5x 也是丑数，因此将 2x, 3x, 5x 加入堆。

上述做法会导致堆中出现重复元素的情况。为了避免重复元素，可以使用哈希集合去重，避免相同元素多次加入堆。

在排除重复元素的情况下，第 n 次从最小堆中取出的元素即为第 n 个丑数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var nthUglyNumber = function(n) {
    const factors = [2, 3, 5];
    const seen = new Set();
    const heap = new MinHeap();
    seen.add(1);
    heap.insert(1);
    let ugly = 0;
    for (let i = 0; i < n; i++) {
        ugly = heap.pop();
        for (const factor of factors) {
            const next = ugly * factor;
            if (!seen.has(next)) {
                seen.add(next);
                heap.insert(next);
            }
        }
        
    }
    return ugly;
};

最小堆的实现大家可以看我另一篇博客：https://sunra.top/posts/9df73d67/

动态规划

方法一使用最小堆，会预先存储较多的丑数，导致空间复杂度较高，维护最小堆的过程也导致时间复杂度较高。可以使用动态规划的方法进行优化。

定义数组dp，其中dp[i] 表示第 i 个丑数，第 n 个丑数即为dp[n]。

由于最小的丑数是 1，因此dp[1]=1。

如何得到其余的丑数呢？定义三个指针 p2,p3,p5 ，表示下一个丑数是当前指针指向的丑数乘以对应的质因数。初始时，三个指针的值都是 1。

当2≤i≤n 时，令 dp[i]=min(dp[p2]×2,dp[p3]×3,dp[p5 ]×5)，然后分别比较dp[p2],dp[p3],dp[p5] 是否相等，如果相等则将对应的指针加 1。

这段话可能有些抽象

换个说法就是，px的值是表示的是px前面位置的数乘以x的结果已经在dp列表中了。

举个例子，

p2 = 3,说明dp[1], dp[2] 分别乘以2的结果已经在dp中了

p3 = 2,说明dp[1] 分别乘以3的结果已经在dp中了

p5 = 1,说明dp[0] 分别乘以5的结果已经在dp中了

在这个情况下，我要去求dp[i]，我就要从dp[p2] * 2, dp[p3] * 3, dp[p5] * 5中去找一个。

为什么不去找dp[p2 - 1] * 2呢？因为整个值已经在dp中了，而且肯定小于等于dp[i - 1]

为什么不去找dp[p2 + 1] * 2呢？因为我们要找最小值，这个值肯定大于dp[p2] * 2;

为什么不去找dp[p3] * 2呢？因为p2和p3之间可能还有其他值乘以2的结果还没在dp中，也就是说可能存在一个p2 < j < p3，dp[j] * 2 还不在dp中，而且 dp[p2] * 2 < dp[j] * 2 < dp[p3] * 2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var nthUglyNumber = function(n) {
    const dp = new Array(n + 1).fill(0);
    dp[1] = 1;
    let p2 = 1, p3 = 1, p5 = 1;
    for (let i = 2; i <= n; i++) {
        const num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
        dp[i] = Math.min(Math.min(num2, num3), num5);
        if (dp[i] === num2) {
            p2++;
        }
        if (dp[i] === num3) {
            p3++;
        }
        if (dp[i] === num5) {
            p5++;
        }
    }
    return dp[n];
};

参考链接：

https://leetcode-cn.com/problems/ugly-number-ii/solution/chou-shu-ii-by-leetcode-solution-uoqd/