大家好,我是程序员吴师兄。
今天在逛 LeetCode 评论区的时候,发现了一道题目近期频繁出现在字节跳动的面试中,不得不感慨一句:面试官真喜欢考察 动态规划 呀!
今天就来详解这道题目,希望能帮助你在面试的时候笑嘻嘻:)
题目描述是这样子的。
题目描述
编写一个程序,找出第 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];}
}
---
由 五分钟学算法 原班人马打造的公众号:图解面试算法,现已正式上线!
接下来我们将会在该公众号上,为大家分享优质的算法解题思路,坚持每天一篇原创文章的输出,视频动画制作不易,感兴趣的小伙伴可以关注点赞一下哈!