跳转至

丑数 II⚓︎

Leetcode题目链接

描述⚓︎

详见中文题目链接。

解答⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> dp(n + 1);
        dp[1] = 1;

        int times2 = 1, times3 = 1, times5 = 1;
        for (int index = 2; index <= n; index++) {
            int a = dp[times2] * 2, b = dp[times3] * 3, c = dp[times5] * 5;
            int current = min({a, b, c});
            if (current == a) times2++;
            if (current == b) times3++;
            if (current == c) times5++;
            dp[index] = current;
        }

        return dp[n];
    }
};