leetcode 264. 丑数 II 及 313. 超级丑数

264. 丑数 II

题目描述

编写一个程序，找出第 n 个丑数。

丑数就是只包含质因数 2, 3, 5 的正整数。

示例:

输入: n = 10

输出: 12

解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明:  

 1. 1 是丑数。

 2. n 不超过1690。

想法

三指针法。一部分是丑数数组，另一部分是权重2，3，5。下一个丑数，定义为丑数数组中的数乘以权重，所得的最小值。

那么，2该乘以谁？3该乘以谁？5该乘以谁？

其一，使用三个指针idx[3]，告诉它们。比如，2应该乘以ugly[idx[0]]，即数组中的第idx[0]个值。（权重2，3，5分别对应指针，idx[0],idx[1],idx[2]）

其二，当命中下一个丑数时，说明该指针指向的丑数 乘以对应权重所得积最小。此时，指针应该指向下一个丑数。（idx[]中保存的是丑数数组下标）

其三，要使用三个并列的if让指针指向一个更大的数，不能用if-else。因为有这种情况：

丑数6，可能由于丑数2乘以权重3产生；也可能由于丑数3乘以权重2产生。

丑数10，... 等等。

其四，因为第一个丑数一定是1，因此循环从1开始而不是从0开始。

代码

class Solution {

public:

    int nthUglyNumber(int n) {

        vector<int> uglynum(n,1),ind(3,0);

        for(int i = 1; i < n; i++)

        {

            int a = uglynum[ind[0]]*2,b=uglynum[ind[1]]*3,c=uglynum[ind[2]]*5;

            int temp = min(min(a,b),c);

            if(a == temp)

                ++ind[0];

            if(b == temp)

                ++ind[1];

            if(c == temp)

                ++ind[2];

            uglynum[i]=temp;

        }

        return uglynum[n-1];

    }

};

313. 超级丑数

题目描述

编写一段程序来查找第 n 个超级丑数。

超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。

示例:

输入: n = 12, primes = [2,7,13,19]

输出: 32

解释: 给定长度为 4 的质数列表 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。

说明:

   1. 1 是任何给定 primes 的超级丑数。

   2. 给定 primes 中的数字以升序排列。

   3. 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000 。

第 n 个超级丑数确保在 32 位有符整数范围内。

想法

同上面的想法，使用多指针，其中代码中的2147483647是int数据类型的最大值

代码

class Solution {

public:

    int nthSuperUglyNumber(int n, vector<int>& primes) {

        int k = primes.size(),i,j;

        vector<int> uglynum(n,1),idx(k,0),a(k,0);

        for(i = 1; i < n; i++)

        {

            int minnum = 2147483647;

            for(j = 0; j < k; j++)

            {

                a[j] = uglynum[idx[j]]*primes[j];

                if(a[j] < minnum)

                    minnum = a[j];

            }

            for(j = 0; j < k; j++)

            {

                if(a[j] == minnum)

                    ++idx[j];

            }

            uglynum[i] = minnum;

        }

        return uglynum[n-1];

    }

};

巴特西

leetcode 264. 丑数 II 及 313. 超级丑数

264. 丑数 II

题目描述

想法

代码

313. 超级丑数

题目描述

想法

代码

最新文章

热门文章