算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
今天和大家聊的问题叫做 丑数 II,我们先来看题面:
https://leetcode-cn.com/problems/ugly-number-ii/
An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5. Given an integer n, return the nth ugly number.
给你一个整数 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 通常被视为丑数。
采用动态规划的方法,dp[i]表示第i+1个丑数(i从0开始),要求第n个丑数,就是求dp[n-1]。
首先,最小的丑数是1,即第一个丑数dp[0] = 1。然后第i+1个丑数,dp[i] = min(dp[p2] * 2, dp[p3] * 3, dp[p5] * 5),其中指针p2, p3 , p5表示下一个丑数所乘的质因子是2,3,5。然后判断dp[i]等于其中的哪一项,对应的那一项的指针加1。
最后遍历完,返回dp[n-1]即可。
def nthUglyNumber(n):
dp = [0] * n
#第一个丑数为1
dp[0] = 1
#表示下一个丑数是乘以哪个质因子(2,3,5)得到的。
#p2表示乘以2,p3表示乘以3, p5表示乘以5.
p2 = 0
p3 = 0
p5 = 0
#遍历
for i in range(1, n):
dp[i] = min(dp[p2] * 2, dp[p3] * 3, dp[p5] * 5)
#更新对应的指针
if dp[i] == dp[p2] * 2:
p2 += 1
if dp[i] == dp[p3] * 3:
p3 += 1
if dp[i] == dp[p5] * 5:
p5 += 1
print(dp)
return dp[-1]
好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。