【动态规划专题】剑指 Offer 49. 丑数-跟着帅地玩副业，开拓第二曲线PlayOffer

hi 普通 2023年11月29日下午5:48

归并排序类似思想，S2、S3、S5（分别以2，3，5为质因子的集合）组成最终得答案

class Solution {
public:
    int nthUglyNumber(int n) {
        //存放答案丑数数组q，初始大小为1，值为1
        vector<int> q(1, 1); 

        int i = 0, j = 0, k = 0;
        while(q.size() < n){
            int temp = min(q[i] * 2, min(q[j] * 3, q[k] * 5));
            q.push_back(temp);
            if(temp == q[i] * 2) i++;
            if(temp == q[j] * 3) j++;
            if(temp == q[k] * 5) k++;  
        }

        return q.back(); //返回数组中的最后一个数
    }
};

0 赞同 0 条回复

June 普通 2023年11月6日下午7:49

class Solution {
    public int nthUglyNumber(int n) {
        if(n == 1)
            return 1;
        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;
            int num3 = dp[p3]*3;
            int 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];
    }
}

0 赞同 0 条回复

Marshan 普通 2023年9月2日下午10:48

没碰到过还真不会

class Solution {
public:
    int nthUglyNumber(int n) {
        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 条回复

北辰普通 2023年8月25日上午10:56

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] == 2*dp[a]) a++;
                if(dp[i] == 3*dp[b]) b++;
                if(dp[i] == 5*dp[c]) c++;
            }
            return dp[n];
    }

时间复杂度：O（n）
空间发杂度：O（n）

0 赞同 0 条回复

Mby 普通 2023年8月21日下午4:10

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 条回复

人生何处不青山普通 2023年8月20日下午10:59

背

function nthUglyNumber(n: number): number {
    let dp: number[] = new Array(n + 1).fill(0);
    dp[1] = 1;
    let x = 1, y = 1, z = 1;
    for (let i = 2; i <= n; i++) {
        let t1 = dp[x] * 2;
        let t2 = dp[y] * 3;
        let t3 = dp[z] * 5;
        dp[i] = Math.min(t1, t2, t3);
        if (t1 === dp[i]) x++;
        if (t2 === dp[i]) y++;
        if (t3 === dp[i]) z++;
    }
    return dp[n];
};

0 赞同 0 条回复

NullPointerException 普通 2023年8月14日下午7:26

class Solution {
public int nthUglyNumber(int n) {
//dp[i] 肯定等于之前的某一个数2/3/5
// 记录 a索引2 b索引3 c索引是5
//当做3个有序数组合并
int dp[] =new int[n];
dp[0]=1;
int a=0;
int b =0;
int c = 0;
for(int i=1;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-1];
}

}

0 赞同 0 条回复

阿尚普通 2023年8月9日下午8:35

//如果一个数是丑数，那么他的2倍、3倍、五倍也是丑数
//类似于合并链表
class Solution {
    public int nthUglyNumber(int n) {
        int p2 = 1, p3 = 1, p5 = 1;
        int v2 = 1, v3 = 1, v5 = 1;
        int[] dp = new int[n + 1];
        int index = 1;

        while(index <= n){
            int minNum = Math.min(Math.min(v2, v3), v5);
            dp[index] = minNum;
            index++;
            if(minNum == v2){
                v2 = 2 * dp[p2];
                p2++;
            }
            if(minNum == v3){
                v3 = 3 * dp[p3];
                p3++;
            }
            if(minNum == v5){
                v5 = 5 * dp[p5];
                p5++;
            }
        }

        return dp[n];
    }
}

0 赞同 0 条回复

AD钙奶普通 2023年8月9日下午2:48

class Solution {
    public int nthUglyNumber(int n) {
        if(n == 1) return 1;
        // dp[i] : 第i个只包含质因子2、3、5的数
        int[] dp = new int[n + 1];
        dp[1] = 1;
        int a = 1,b = 1,c = 1;
        for(int i = 2; i <= n; i ++) {
            int n2 = dp[a]*2, n3= dp[b]*3, n5=dp[c]*5;
            dp[i] = Math.min(Math.min(n2,n3),n5);
            if(dp[i] == n2) a ++;
            if(dp[i] == n3) b ++;
            if(dp[i] == n5) c ++;
        }
        return dp[n];
    }
}

0 赞同 0 条回复

长河呼叫黄江普通 2023年8月9日上午8:40

8.8 周二
Day29：下面是代码

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

0 赞同 0 条回复

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

共以下 10 个回答

# 回答此问题取消回复

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

共以下 10 个回答

# 回答此问题 取消回复

# 回答此问题取消回复