【动态规划专题】剑指 Offer 49. 丑数

本问题对应课程链接：剑指offer刷题第六期

要求：

1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

shuaidi

更新于 3 年前 94 10

共以下 10 个回答

Thaddeus 永久会员 2024年5月6日下午3:18

打卡

class Solution {
    public int nthUglyNumber(int n) {
        =int a = 0, b = 0, c = 0;
        int[] res = new int[n];
        res[0] = 1;
        for(int i = 1; i < n; i++) {
            int n2 = res[a] * 2, n3 = res[b] * 3, n5 = res[c] * 5;
            res[i] = Math.min(Math.min(n2, n3), n5);
            if(res[i] == n2) a++;
            if(res[i] == n3) b++;
            if(res[i] == n5) c++;
        }
        return res[n - 1];
    }
}

0 赞同 0 条回复

=.= 普通 2024年4月15日下午9:50
class Solution {
public int nthUglyNumber(int n) {
int a = 1, b = 1, c = 1;
int[] dp = new int[n+1];
dp[1] = 1;
for(int i=2; i<=n; i++){
dp[i] = Math.min(dp[a]2, Math.min(dp[b]3, dp[c]5));
if(dp[i] dp[a]2) a++;
if(dp[i] dp[b]3) b++;
if(dp[i] dp[c]5) c++;
}
```
    return dp[n];
}
```
}

时间：O(n)；
空间：O(n)
0 赞同 0 条回复

登录以回复
云无深雁影普通 2024年4月10日下午11:46
class Solution {
public int nthUglyNumber(int n) {
int[] dp = new int[n];
int i = 0, j = 0, k = 0;
dp[0] = 1;
int current = 1;
while(current < n){
int min = Math.min(dp[i] * 2,Math.min(dp[j] * 3,dp[k] * 5));
dp[current++] = min;
if(min dp[i] * 2) i++;
if(min dp[j] * 3) j++;
if(min dp[k] * 5) k++;
}
return dp[n-1];
```
}
```
}
//时间复杂度On 空间复杂度On
0 赞同 0 条回复

登录以回复

方铎码农普通 2024年4月8日下午3:22

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n+1];
        dp[1] = 1;
        int p2 = 1, p3 = 1, p5 = 1;
        for(int i = 2; i <= n; i++){
            int num2 = dp[p2]*2, num3 = dp[p3]*3, num5 = dp[p5]*5;
            dp[i] = Math.min(Math.min(num2,num3),num5);
            if(dp[i] == num2){
                p2++;
            } 
            if(dp[i] == num3){
                p3++;
            }
            if(dp[i] == num5){
                p5++;
            }

        }
        return dp[n];
    }
}

时间复杂度$O(n)$，空间复杂度$O(n)$

0 赞同 0 条回复

王位詮釋普通 2024年4月6日下午9:35

class Solution {
    public int nthUglyNumber(int n) {
        int a = 1;
        int b = 1;
        int c = 1;
        int[] dp = new int[n+1];//dp[i]表示第i个丑数 
        dp[1] = 1;
        for(int i=2;i<=n;i++){
            dp[i] = Math.min(Math.min(dp[a]*2,dp[b]*3),dp[c]*5);
            if(dp[i]==dp[a]*2){
                a++;
            }
            if(dp[i]==dp[b]*3){
                b++;
            }
            if(dp[i]==dp[c]*5){
                c++;
            }
        }
        return dp[n];
    }
}
之前对于动归的思路有点太狭隘了，一直以为是i和i-1之间的关系，这个题状态转移方程是这样的，挺好。
时间复杂度：O(n)
空间复杂度：O(n)

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年4月5日下午8:51

class Solution {
    public int nthUglyNumber(int n) {
        int a=1,b=1,c=1;
        int[] dp = new int[n+1]; //注意大小
        dp[1]=1;

        for(int i=2;i<=n;i++){
            dp[i]=Math.min(Math.min(dp[a]*2,dp[b]*3),dp[c]*5);
            if(dp[i] == dp[a] * 2) a++;
            if(dp[i] == dp[b] * 3) b++;
            if(dp[i] == dp[c] * 5) c++;
        }

        return dp[n];
    }
}

时间复杂度：O(n)
空间复杂度：O(n)

0 赞同 0 条回复

Raphtalia. 普通 2024年4月4日上午11:37

class Solution {
public:
int nthUglyNumber(int n) {
vector dp(n + 1, 1);
int p2 = 1, p3 = 1, p5 = 1;
for(int i = 2; i <= n; i ++) {
int n2 = dp[p2] * 2, n3 = dp[p3] * 3, n5 = dp[p5] * 5;
dp[i] = min(min(n2, n3), n5);
if(dp[i] n2) p2 ++;
if(dp[i] n3) p3 ++;
if(dp[i] n5) p5 ++;
}
return dp[n];
}
};
时空均为n

0 赞同 0 条回复

登录以回复

Jimmy 普通 2024年4月4日上午11:07

时间复杂度O(n)，空间复杂度O(1)

class Solution {
public:
    int nthUglyNumber(int n) {
        int a=0,b=0,c=0;
        vector<int> dp(n,1);
        for(int i=1;i<n;i++)
        {
            dp[i] = min(min(dp[a]*2,dp[b]*3),dp[c]*5);
            if(dp[i]%2 == 0) a += 1;
            if(dp[i]%3 == 0) b += 1;
            if(dp[i]%5 == 0) c += 1; 
        }
        return dp[n-1];
    }
};

0 赞同 0 条回复

紫芝普通 2024年4月2日下午10:03

思路：从 1 开始，每个数都需要乘以 2，3，5；则使用三个变量来分别标记该数是否乘以对应数字，比如 a 表示 dp[a] 之前的 dp[0] … dp[a-1] 都乘以2了，b 表示 dp[b] 之前的 dp[0]…dp[b-1] 都乘以3了，c 表示 dp[0]…dp[c-1]都乘以5了，因此，当前的最小丑值应该在 dp[a]2, dp[b]3, dp[c]*5 中得出。

“`c++
class Solution {
public:
int nthUglyNumber(int n) {
vector dp(n);
dp[0] = 1;
int a = 0, b = 0, c = 0;
for (int i=1; i

0 赞同 0 条回复

登录以回复

heathhou 普通 2024年4月2日下午8:23

class Solution {
public:
    int nthUglyNumber(int n) {
        // dp[i]: 第i个丑数
        vector<int> dp(n+1, 0);
        dp[1] = 1;
        int a = 1, b = 1, c = 1;

        for(int i = 2; i <=n; i++){
            dp[i] = min(min(dp[a]*2, dp[b]*3), dp[c]*5);
            if(dp[i] == dp[a] * 2) ++a;
            if(dp[i] == dp[b] * 3) ++b;
            if(dp[i] == dp[c] * 5) ++c;
        }

        return dp[n];
    }
};

0 赞同 0 条回复

# 回答此问题取消回复

后才能回答

【动态规划专题】剑指 Offer 49. 丑数

共以下 10 个回答

# 回答此问题 取消回复

# 回答此问题取消回复