LeetCode 264. 丑数 II
题目描述
思路分析
三指针
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func nthUglyNumber(n int) int {
dp := make([]int, n)
dp[0] = 1 // 第一个丑数是 1
p2, p3, p5 := 0, 0, 0 // 三个指针初始都指向第一个丑数
for i := 1; i < n; i++ {
// 计算下一个丑数，取三者中最小值
next := min(dp[p2]*2, min(dp[p3]*3, dp[p5]*5))
dp[i] = next
// 更新指针
if next == dp[p2]*2 {
p2++
}
if next == dp[p3]*3 {
p3++
}
if next == dp[p5]*5 {
p5++
}
}
return dp[n-1]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
1
write your code here
相似题目
| 题目 | 难度 | 题解 |
|---|---|---|
| 合并 K 个升序链表 | Hard | |
| 计数质数 | Medium | |
| 丑数 | Easy | |
| 完全平方数 | Medium | |
| 超级丑数 | Medium |
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！