LC *264. 丑数 II（动态规划）

题目

思路

暴力法超时，官方题解是DP 三指针

贴个官方题解吧LeetCode题解

代码语言：javascript复制

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> res = {1};
        int s2 = 0, s3 = 0, s5 = 0;
        for (int i = 1; i <= n; i  ) {
            res.push_back(min(min(res[s2] * 2, res[s3] * 3), res[s5] * 5));
            if (res[i] == res[s2] * 2) s2  ;
            if (res[i] == res[s3] * 3) s3  ;
            if (res[i] == res[s5] * 5) s5  ;
        }
        return res[n - 1];
    }
};

dp ode 指针

0 人点赞