字节跳动面到这道题，有的读者一脸懵逼，有的读者笑嘻嘻

我不是女神ヾ 2022-12-04 01:24 67阅读 0赞

大家好，我是程序员吴师兄。

今天在逛 LeetCode 评论区的时候，发现了一道题目**近期**频繁出现在字节跳动的面试中，不得不感慨一句：面试官真喜欢考察 **动态规划** 呀！

![format_png][]

今天就来详解这道题目，希望能帮助你在面试的时候笑嘻嘻：）

题目描述是这样子的。

### 题目描述 ###

编写一个程序，找出第 n 个丑数。

丑数就是质因数只包含 2, 3, 5 的**正整数**。

**示例:**

输入: n = 10
    输出: 12
    解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

**说明:**

*  1 是丑数。
 *  n 不超过1690。

题目来源：https://leetcode-cn.com/problems/ugly-number-ii/

### 题目解析 ###

题目让你找出第 n 个丑数。对于丑数，题目也给出了定义，丑数是正整数，并且它的质数因子仅包含 `2, 3, 5`。另外，整数 1 算是一个最小的丑数。

一开始看到这道题，感觉就是一道简单的**数学乘法题**，一个循环不就搞定了？

但其实**并不是**，如果仅仅使用简单的乘法循环，你**并不知道下一个数所在的序列位置**。

另外，暴力的深度优先搜索遍历在这道题上也不适用，因为你并不确定搜索的结束条件，到底找到哪个数才停止递归呢？

但如果进一步思考，你会发现 **后面的数可以由前面的数推出来**。

用通俗一点的话讲就是，问题的解可以由子问题的解推出来。这句话是不是很熟悉？是的，**动态规划的特点**！

但这里比较难想到的地方是，子问题之间的联系是什么？

比如我们定义动态规划状态，`dp[i]` 表示第 i 个丑数，那么这个状态怎么由前面的状态推导得出？

这里的重点是，**前面的每一个数（状态）都可以乘上 `2, 3, 5` 来形成一个新的状态**，新的状态是肯定符合丑数的定义。

但是我们的关注点是下一个状态是什么，比如第一个状态是 1，它可以乘以上面 3 个数的其中一个，结果为 2、3、5，取最小的 `1 × 2 = 2` 为第二个状态。

到这时，我们需要考虑第三个状态是什么。

从第一个状态 1 出发，我们得到了 2，但是从第一个状态 1 出发，我们还可以得到 3，5。另外，从第二个状态 2 出发我们可以得到 4 。

你可能会说，从第二个状态 2 出发我们还可以得到 6、10。没错，但是乘上 3、5 在 1 的时候考虑比在 2 处考虑得出的状态更小。

也就是说，第三个状态的值在 1 × 3、1 × 5、 2 × 2 三者里面进行选择。

通过上面的描述，你可能 **找到规律** 了：每个状态都可以乘上 `2, 3, 5`。

但是状态乘上这些质数因子的时候，必须保证前面的状态已经乘过了对应的质数因子，因为前面会得到更小的值，我们需要的是 **按序查找** 。

由此，我们可以创建 3 个指针 p2、p3、p5，分别表示这 3 个质数因子此时应该乘上第几个状态。

补充：这里来具体解释一下 p2、p3、p5 的含义（来源于 LeetCode 题解区 zzxn）。

实际上 pi 的含义是**有资格同 i 相乘的最小丑数的位置**。

这里资格指的是：如果一个丑数 dp\[pi\] 通过乘以 i 可以得到下一个丑数，那么这个丑数 dp\[pi\] 就永远失去了同 i 相乘的资格（没有必要再乘了），我们把 pi++ 让 dp\[pi\] 指向下一个丑数即可。

不懂的话举例说明：

一开始，丑数只有\{1\}，1可以同 2 、3 、5 相乘，取最小的 1 × 2 = 2 添加到丑数序列中。

现在丑数中有 \{1，2\} ，在上一步中，1 已经同 2 相乘过了，所以今后没必要再比较 1 × 2 了，我们说 1 失去了同 2 相乘的资格。

现在 1 有与 3、5 相乘的资格，2 有与 2、3、5 相乘的资格，但是 2 × 3 和 2 × 5 是没必要比较的，因为有比它更小的 1 可以同 3、5 相乘，所以我们只需要比较 1 × 3 、1 × 5 、 2 × 2 。

依此类推，**每次我们都分别比较有资格同 2、3、5 相乘的最小丑数，选择最小的那个作为下一个丑数**，假设选择到的这个丑数是同 i（ i = 2、3、5）相乘得到的，所以它失去了同 i 相乘的资格，把对应的 pi++ ，让 pi 指向下一个丑数即可。

这样的思路可以在 `O(n)` 的时间完成这道题目。

### 参考代码 ###

class Solution {
        public int nthUglyNumber(int n) {
            if( n < 1) return 0;
    
            int p2 = 0;
            int p3 = 0;
            int p5 = 0;
    
            int[] dp = new int[n];
    
            dp[0] = 1;
    
            for (int i = 1; i < n; i ++) {
                // 比较此时可能的状态，取最小的那个
                dp[i] = Math.min(dp[p2] * 2, Math.min(dp[p3] * 3, dp[p5] * 5));
    
                 // 更新指向
                 // 注意这里不能只更新一个指针
                    // 比如 6，可以由 2 * 2 * 2 形成，也可以由 2 * 3 组成
    
                if( dp[i] == dp[p2] * 2) p2++;
    
                if( dp[i] == dp[p3] * 3) p3++;
    
                if( dp[i] == dp[p5] * 5) p5++;
    
            }
            return dp[n - 1];
    
        }
    }

\---

由 五分钟学算法 原班人马打造的公众号：图解面试算法，现已正式上线！
    接下来我们将会在该公众号上，为大家分享优质的算法解题思路，坚持每天一篇原创文章的输出，视频动画制作不易，感兴趣的小伙伴可以关注点赞一下哈！

[format_png]: /images/20221123/b070ef666d7d45419329353112b817e5.png