264. Ugly NumberII & 313. Super Ugly Number

Lionad-Morotar 发布于2019-08-14 14:06 / 3205人阅读

摘要：题目解答这个问题最主要的就是如果按顺序找出那么我们如果能想到把以为因子的这些分成三个然后在每次输出时取里最小的那个数输出就可以解决了。

264 Ugly NumberII
题目：
Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number.

解答：
这个问题最主要的就是如果按顺序找出ugly number, 那么我们如果能想到把以2, 3, 5为因子的这些ugly number分成三个list, 然后在每次输出时取list里最小的那个数输出就可以解决了。代码如下：

public class Solution {
    // (1) 1*2, 2*2, 3*2, 4*2,...
    // (2) 1*3, 2*3, 3*3, 4*3,...
    // (3) 1*5, 2*5, 3*5, 4*5,...
    class Num {
        int index, factor;
        public Num(int index, int factor) {
            this.index = index;
            this.factor = factor;
        }
    }

    public int nthUglyNumber(int n) {
        int[] ugly = new int[n];
        ugly[0] = 1;
        Num l2 = new Num(1, 2);
        Num l3 = new Num(1, 3);
        Num l5 = new Num(1, 5);
        for (int i = 1; i < n; i++) {
            int min = Math.min(l2.factor, Math.min(l3.factor, l5.factor));
            ugly[i] = min;
            if (l2.factor == min) {
                l2.factor = ugly[l2.index++] * 2;
            }
            if (l3.factor == min) {
                l3.factor = ugly[l3.index++] * 3;
            }
            if (l5.factor == min) {
                l5.factor = ugly[l5.index++] * 5;
            }
        }
        return ugly[n - 1];
    }
}

其实这道题还有一个更in general的解法，跟super ugly number可以用一样的解法：

public int nthUglyNumber(int n) {
    int[] primes = {2, 3, 5};
    int[] ugly = new int[n];
    int[] index = new int[primes.length];
    
    ugly[0] = 1;
    for (int i = 1; i < n; i++) {
        ugly[i] = Integer.MAX_VALUE;
        for (int j = 0; j < primes.length; j++) {
            //从每个prime现在乘到的数开始继续往下乘
            ugly[i] = Math.min(ugly[i], primes[j] * ugly[index[j]]);
        }
        
        for (int j = 0; j < primes.length; j++) {
            while (primes[j] * ugly[index[j]] == ugly[i]) {
                index[j]++;
            }
        }
    }
    return ugly[n - 1];
}

313 Super Ugly Number
题目：
Write a program to find the nth super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.

Note:
(1) 1 is a super ugly number for any given primes.
(2) The given numbers in primes are in ascending order.
(3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.

解答：

public int nthSuperUglyNumber(int n, int[] primes) {
    int[] ugly = new int[n];
    int[] index = new int[primes.length];
    
    ugly[0] = 1;
    for (int i = 1; i < n; i++) {
        ugly[i] = Integer.MAX_VALUE;
        //找到最小的值
        for (int j = 0; j < primes.length; j++) {
            ugly[i] = Math.min(ugly[i], primes[j] * ugly[index[j]]);
        }
        //去重
        for (int j = 0; j < primes.length; j++) {
            while (ugly[i] == primes[j] * ugly[index[j]]) {
                index[j]++;
            }
        }
    }
    return ugly[n - 1];
}

GPU服务器服务器托管 Ugly NumberII V313 super

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64811.html

264. Ugly Number II &amp; 313. Super Ugly Number

摘要：每次出一个数，就把这个数的结果都放进去。，指针从个变成个。的做法参考还是复杂度的问题，回头再看看 264. Ugly Number II 题目链接：https://leetcode.com/problems... dp的方法参考discussion：https://discuss.leetcode.com/... dp的subproblem是：dp[i]: i-th ugly numb...

hiyang 2019-08-16 10:29 评论0 收藏0
leetcode263,264,313 ugly numbers

摘要：这题可以使用暴力遍历法，从开始，对每一个数都进行判断，直到找到第个丑数为止。优先队列可以很好的满足该情况。因此每个素数持有的信息包括当前对应的丑数的下标。前言这一篇博客把ugly numbers系列的题目做一个整理。这三道题正好是一个思路的循序渐进，所以放在一篇博客当中。 Ugly Number Write a program to check whether a given nu...

everfly 2019-08-16 11:02 评论0 收藏0
Leetcode[313] Super Ugly Number

摘要：滚动求最大值复杂度考虑一个，的值是下一个可能的替补值。思路数组中保存的是之前保留到的值，因为下一个可能的值是和之前的值的倍数关系。 Leetcode[313] Super Ugly Number Write a program to find the nth super ugly number. Super ugly numbers are positive numbers whos...

Aklman 2019-08-16 10:27 评论0 收藏0
leetcode-313-Super Ugly Number

摘要：题意找出以某些数为公因数的递增排序的第个数条件维护了的元素的相乘因素的。由于是最小值，所以每次保留最小的。问题转化，多次迭代，变成，处理对象变了。不重复的思想找出重复计算的地方，找出不重复计算的方法，用极值约束，加以记录。题意：找出以某些数为公因数的递增排序的第n个数条件：indexes 维护了 primes的元素的相乘因素（uglies）的index。思路：每次从 prim...

张春雷 2019-07-30 17:35 评论0 收藏0
[LintCode/LeetCode] Super Ugly Number

摘要：建两个新数组，一个存数，一个存。数组中所有元素初值都是。实现的过程是，一个循环里包含两个子循环。两个子循环的作用分别是，遍历数组与相乘找到最小乘积存入再遍历一次数组与的乘积，结果与相同的，就将加，即跳过这个结果相同结果只存一次。 Problem Write a program to find the nth super ugly number. Super ugly numbers a...

wuyumin 2019-08-14 15:20 评论0 收藏0