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

Gg 普通 2023年8月9日下午9:49

class Solution {
    // 定义dp[i]为第i+1个丑数
    // dp[i] = Math.min(dp[a] * 2 , dp[b] * 3, dp[c] * 5)
    // 同时 dp[i] = dp[a] * 2 时，要小于dp[a+1] * 2
    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 条回复

宁永久会员 2023年3月14日下午3:58

下标含义

class Solution {
    public int nthUglyNumber(int n) {
        //丑数和丑数相乘，得到的只能是丑数
        int[] dp = new int[n + 1];
        dp[1] = 1;
        int a = 1, b = 1, c = 1;
        //注意下标的含义
        for(int i = 2; i <= n; i++){
            dp[i] = Math.min(Math.min(2 * dp[a], 3 * dp[b]), 5* dp[c]);
            if(dp[i] == 2 * dp[a]) a++;
            if(dp[i] == 3 * dp[b]) b++;
            if(dp[i] == 5 * dp[c]) c++;
        }
        return dp[n];
    }
}

0 赞同 0 条回复

PatNick 普通 2023年1月20日上午11:48

def nthUglyNumber(n: int) -> int:
    if n == 0:
        return None
    if n == 1:
        return 1
    # 规定dp【i】代表第i个丑数
    dp = [0 for _ in range(n+1)]
    dp[1] = 1
    a = b = c = 1

    for i in range(2,n+1):
        dp[i] = min(dp[a]*2,dp[b]*3,dp[c]*5)
        if dp[i] == dp[a]*2:
            a += 1
        if dp[i] == dp[b]*3:
            b += 1
        if dp[i] == dp[c]*5:
            c += 1
    return dp[-1]

0 赞同 0 条回复

lucca 普通 2023年1月19日下午9:50

真的难，又是能看一下午的一道题目

class Solution {
    public int nthUglyNumber(int n) {
        int[] v = new int[n];
        v[0] = 1;
        int i = 0, j = 0, k = 0;
        for (int idx = 1; idx < n; idx++) {
            v[idx] = Math.min(v[i]*2, Math.min(v[j]*3, v[k]*5));
            if (v[idx] == v[i] * 2) i++;
            if (v[idx] == v[j] * 3) j++;
            if (v[idx] == v[k] * 5) k++;
        }
        return v[n-1];
    }
}

0 赞同 0 条回复

@ 普通 2022年12月23日上午11:20

时间复杂度：O(N)

空间复杂度：O(N)

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

    //以下做法超时了
//    public int nthUglyNumber(int n) {
//
//        int res = 0;
//
//        for (int i = 1, j = 0; j < n ; i++) {
//            if(isUgly(i)){
//                res = i;
//                j++;
//            }
//
//        }
//
//        return res;
//
//    }
//
//    public boolean isUgly(int n) {
//        if(n == 0)
//            return false;
//        while(n != 1)
//        {
//            if(n % 2 == 0)
//                n = n / 2;
//            if(n % 3 ==0)
//                n = n / 3;
//            if(n % 5 ==0)
//                n = n / 5;
//            if(n % 2 != 0 && n % 3 != 0 && n % 5 != 0)
//                break;
//        }
//        if(n == 1)
//            return true;
//        else
//            return false;
//    }


}

0 赞同 0 条回复

mpweixin用户普通 2022年12月8日下午9:26

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 < 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];
}
};
C++
思路：
定义：dp[i]是当n=i的时候的丑数
初始化：dp[0] = 1；
关系：dp[i] = min(dp[a]2, min(dp[b]3, dp[c]*5))
要注意a，b， c的转移

0 赞同 0 条回复

symbol 普通 2022年12月3日上午7:53

func nthUglyNumber(n int) int {
    // 抽数的提取性质：丑数只包含因子2，3，5，
    ///因此有“丑数=某较小丑数 * 某因子” （例如：10 = 5 * 2）
    // dp[a] dp[b] dp[c] 感觉想是三个数组组成一个丑数数组，
    //分别对应小丑数2/3/5的倍数，每次都取最小倍数放到丑数数组
    a, b ,c := 0, 0, 0
    dp := make([]int, n)
    dp[0] = 1
    for i := 1; i < n; i++ {
        n1, n2, n3 := dp[a] * 2, dp[b] * 3, dp[c] * 5
        dp[i] = min(min(n1, n2), n3)
        if dp[i] == n1 {
            a++
        }
        if dp[i] == n2 {
            b++
        }
        if dp[i] == n3 {
            c++
        }
    }
    return dp[n-1]
}
func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

0 赞同 0 条回复

T 普通 2022年12月1日下午4:07

class Solution {
    public int nthUglyNumber(int n) {
        if(n == 0) return 0;
        int[] dp = new int[n];
        dp[0] = 1;
        //标记当前2,3,5分别乘到第几个数
        int a = 0, b = 0, c = 0;
        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(n2 == dp[i]) a++;
            if(n3 == dp[i]) b++;
            if(n5 == dp[i]) c++;
        }
        return dp[n - 1];
    }
}

0 赞同 0 条回复

Tolkien 永久会员 2022年11月29日下午7:56

/**
     * 动态规划
     * 时间复杂度：O(n)，空间复杂度：O(n)
     * 1. dp的定义：第i个丑数为dp[i-1]
     * 2. 关系式：dp[i] = min(dp[a]*2, dp[b]*3, dp[5]*5)
     * 3. 初始化：a=b=c=0, dp[0] = 1
     */
    public static int nthUglyNumber(int n) {
        int[] dp = new int[n];
        dp[0] = 1;
        int a = 0, b = 0, c = 0;

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

            if(dp[i] == timesTwo) { a++; }
            if(dp[i] == timesThree) { b++; }
            if(dp[i] == timesFive) { c++; }
        }

        return dp[n-1];
    }

0 赞同 0 条回复

Mooby 普通 2022年11月27日下午3:58

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

西西弗斯的石头永久会员 2022年11月27日下午2:21

该题时间空间复杂度为O（n）

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        int a = 1,b = 1,c = 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];
    }
}

0 赞同 0 条回复

訁訁訁訁訁普通 2022年11月25日下午9:52

我们知道，丑数的排列肯定是1,2,3,4,5,6,8,10…. 然后有一个特点是，任意一个丑数都是由小于它的某一个丑数2，3或者5得到的，那么如何得到所有丑数呢？现在假设有3个数组，分别是： A：{1 * 2，2 * 2，3 * 2，4 * 2，5 * 2，6 * 2，8 * 2，102……}

B：{1 * 3，2 * 3，3 * 3，4 * 3，5 * 3，6 * 3，8 * 3 ，10*3……}

C：{15，2 * 5，3 * 5，4 * 5，5 * 5，6 * 5，8 * 5，105……}

那么所有丑数的排列，必定就是上面ABC3个数组的合并结果然后去重得到的，那么这不就转换成了三个有序数组的无重复元素合并的问题了吗？而这三个数组就刚好是{1,2,3,4,5,6,8,10….}乘以2,3,5得到的。

合并有序数组的一个比较好的方法，就是每个数组都对应一个指针，然后比较这些指针所指的数中哪个最小，就将这个数放到结果数组中，然后该指针向后挪一位。

回到本题，要求丑数ugly数组中的第n项，而目前只知道ugly[0]=1，所以此时三个有序链表分别就只有一个元素：

A ： {1*2……}

B ： {1*3……}

C ：{1*5……}

假设三个数组的指针分别是i,j,k，此时均是指向第一个元素，然后比较A[i]，B[j]和C[k]，得到的最小的数A[i]，就是ugly[1]，此时ugly就变成{1,2}了，对应的ABC数组就分别变成了：

A ： {1 * 2，2*2……}

B ： {1 * 3, 2 * 3……}

C ：{1 * 5,2*5……}

此时根据合并有序数组的原理，A数组指针i就指向了下一个元素，即’2*2’，而j和k依然分别指向B[0]和C[0]，然后进行下一轮合并，就是A[1]和B[0]和C[0]比较，最小值作为ugly[2]…..如此循环n次，就可以得到ugly[n]了。

此外，注意到ABC三个数组实际上就是ugly[] * 2，ugly[] * 3和ugly[] * 5的结果，所以每次只需要比较A[i]=ugly[i]2，B[j]=ugly[j] * 3和C[k]=ugly[k]5的大小即可。然后谁最小，就把对应的指针往后移动一个，为了去重，如果多个元素都是最小，那么这多个指针都要往后移动一个。

//时间复杂度O(n)空间复杂度O(n)
/**
dp[i]表示第i+1个丑数的值
 */
class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n];
        //填充最大值，避免min判断时将0加入
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0] = 1;
        //三个指针分别控制因子2 3 5
        int x2 = 0,x3 = 0,x5 = 0;
        for(int i = 1;i < n;i++){
            int min = Math.min(dp[x3]*3,Math.min(dp[x2]*2,dp[x5]*5));
            dp[i] = min;
            if(dp[i] == dp[x2] * 2) x2++;
            if(dp[i] == dp[x3] * 3) x3++;
            if(dp[i] == dp[x5] * 5) x5++;
        }
        return dp[n-1];
    }
}

0 赞同 0 条回复

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

共以下 12 个回答

真的难，又是能看一下午的一道题目

# 回答此问题取消回复

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

共以下 12 个回答

真的难，又是能看一下午的一道题目

# 回答此问题 取消回复

# 回答此问题取消回复