题目
给你一个整数
n，请你找出并返回第n个 丑数 。丑数 就是质因子只包含
2、3和5的正整数。
解题
def nthUglyNumber(n: int) -> int:# 初始化 dp 数组dp = [0] * ndp[0] = 1# 初始化三个指针p2 = p3 = p5 = 0for i in range(1, n):# 计算当前三个候选丑数next_ugly = min(dp[p2] * 2, dp[p3] * 3, dp[p5] * 5)# 更新 dp 数组dp[i] = next_ugly# 移动指针if next_ugly == dp[p2] * 2:p2 += 1if next_ugly == dp[p3] * 3:p3 += 1if next_ugly == dp[p5] * 5:p5 += 1return dp[n - 1]# 测试代码
n = 10
print(f"The {n}th ugly number is: {nthUglyNumber(n)}")
The 10th ugly number is: 12