首页 🍒LeetCode,🐶算法

题目

JtRUur8VE4.png

思路

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

贴个官方题解吧LeetCode题解

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];
    }
};



文章评论