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

晓宇普通 2024年12月31日下午9:22

class Solution {
public:
    int nthUglyNumber(int n) {
        // 思路：dp[i] 第i个丑数是多少
        if(n <= 2) return n;
        // 1 2 3 5
        vector<int> dp(n);
        dp[0] = 1;
        int a = 0,b = 0,c = 0;
        for(int i = 1;i < n;i++){
            dp[i] = min(dp[a] * 2,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];



    }
    // o(n) o(n)
};

0 赞同 0 条回复

Kisara 普通 2024年12月31日上午9:00

1

class Solution {
    public int nthUglyNumber(int n) {
        // 定义 dp 数组保存前 n 个丑数
        int[] dp = new int[n];
        dp[0] = 1; // 第一个丑数是 1

        // 定义三个指针分别对应丑数的质因数 2, 3, 5
        int p2 = 0, p3 = 0, p5 = 0;

        for (int i = 1; i < n; i++) {
            // 丑数是前面的丑数分别乘以 2, 3, 5 的最小值
            int next2 = dp[p2] * 2;
            int next3 = dp[p3] * 3;
            int next5 = dp[p5] * 5;

            // 选择最小值作为下一个丑数
            int nextUgly = Math.min(next2, Math.min(next3, next5));
            dp[i] = nextUgly;

            // 更新指针
            if (nextUgly == next2) p2++;
            if (nextUgly == next3) p3++;
            if (nextUgly == next5) p5++;
        }

        return dp[n - 1];
    }
}

0 赞同 0 条回复

陆狗陆狗普通 2024年12月30日下午10:06

解题思路
– 按照顺序去2/3/5的倍数去找
– 初始的2,3,5
– 2：22=4，23=6,25=10
– 3: 32=6,33=9,35=15
– 5：52=10，53=15，55=25
– 存在两个问题，一个是重复，另外一个是可能会跳过一些数字
– 如何解决呢？需要用2,3,5三个独立指针去遍历dp[]。把dp[]作为备选池都可以分别去乘以2,3,5，但是我们需要先把最小的作为新的dp[]追加进去，注意并不是2,3,5依次按顺序去乘以，比如22=4,23=6乘以2次，都比52=10的1次要大。因而2,3，5分别去维护独立的index，然后慢慢去++
【题解1】

class Solution {
    public int nthUglyNumber(int n) {
        // 按照顺序去2/3/5的倍数去找
        // 初始的2,3,5
        // 2：2*2=4，2*3=6,2*5=10
        // 3: 3*2=6,3*3=9,3*5=15
        // 5：5*2=10，5*3=15，5*5=25
        // 存在两个问题，一个是重复，另外一个是可能会跳过一些数字
        // 如何解决呢？把dp[]作为备选池都可以分别去乘以2,3,5，但是我们需要先把最小的作为新的dp[]，注意并不是2,3,5依次按顺序去乘以，比如2*2=4,2*3=6乘以2次，都比5*2=10的1次要大。因而2,3，5分别去维护独立的index，然后慢慢去++
        int[] dp = new int[n];
        dp[0] = 1;
        int n2 = 0;
        int n3 = 0;
        int n5 = 0;
        for (int i = 1; i < n; i++) {
            int nextNumber = Math.min(Math.min(dp[n2] * 2, dp[n3] * 3), dp[n5] * 5);
            dp[i] = nextNumber;
            if (nextNumber == dp[n2] * 2) {
                n2++;
            }
            if (nextNumber == dp[n3] * 3) {
                n3++;
            }
            if (nextNumber == dp[n5] * 5) {
                n5++;
            }
        }
        return dp[n - 1];

    }
}

0 赞同 0 条回复

Pendulumpal 普通 2024年12月25日下午9:16

定义p2,p3,p5,表示dp[px]*x是下一个丑数

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

0 赞同 0 条回复

Aatorx 永久会员 2024年12月24日下午2:34

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

通过乘2，3，5得到全部的丑数
时间复杂度O(N)，空间复杂度O(N)。

0 赞同 0 条回复

月下足迹普通 2024年12月24日上午9:13

//每个丑数可以通过乘2，3，5得到
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年12月23日下午8:10

思路：每个丑数都可以由其他较小的丑数通过乘以 2 或 3 或 5 得到

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

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

共以下 7 个回答

# 回答此问题取消回复

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

共以下 7 个回答

# 回答此问题 取消回复

# 回答此问题取消回复