【LeetCode】丑数（Ugly Number）☹☠☣☢☃

秒速五厘米 2023-01-04 10:30 172阅读 0赞

## LeetCode丑数（Ugly Number） ##

### 文章目录 ###

*   *  LeetCode丑数（Ugly Number）
     *   *  丑数（搜狗百科）
         *  丑数★
         *  丑数Ⅱ★★
         *  超级丑数★★
         *  丑数Ⅲ★★

--------------------

### 丑数（搜狗百科） ###

*  说法一（ugly number）：把只包含质因子2，3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但7、14不是，因为它们包含质因子7。 习惯上我们把1当做是第一个丑数。
 *  对于一给定的素数集合 S = \{p1, p2, …, pK\},考虑一个正整数集合，该集合中任一元素的质因数全部属于S。这个正整数集合包括，p1、p1*p2、p1*p1、p1*p2*p3…(还有其它)。该集合被称为S集合的“丑数集合”。

--------------------

### 丑数★ ###

【**题目**】编写一个程序判断给定的数是否为丑数。丑数就是只包含质因数 `2, 3, 5` 的**正整数**。

[LeetCode263. 丑数][LeetCode263.]

【**题目**】编写一个程序判断给定的数是否为丑数。丑数就是只包含质因数 `2, 3, 5` 的**正整数**。

**说明:**

1.  `1` 是丑数。
2.  输入不会超过 32 位有符号整数的范围: \[−231, 231 − 1\]。

【**示例**】

输入: 6
    输出: true
    解释: 6 = 2 × 3

【**解题思路**】

*  显然，若num为负数或者0，则不是丑数
 *  num除以因子2、3、5，看其最后值是否等于1

class Solution {
        
        public boolean isUgly(int num) {
        
            if(num <= 0) return false;
            int[] fac = {
        2, 3, 5};
            for(int x : fac) {
        
                while(num % x == 0) num /= x;
            }
            return num == 1;
        }
    }

--------------------

### 丑数Ⅱ★★ ###

[LeetCode264. 丑数 II][LeetCode264. _ II]

【**题目**】编写一个程序，找出第 `n` 个丑数。丑数就是质因数只包含 `2, 3, 5` 的**正整数**。

**说明:**

1.  `1` 是丑数。
2.  `n` **不超过**1690。

【**示例**】

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

【**解题思路**】

方法一：优先队列

*  初始化队列为1（第一个丑数）
 *  出队列一个丑数，并且将乘以2、3、5的丑数入队（注意if判断不能重复加入数据）
 *  遍历至第n个丑数

class Solution {
        
        public int nthUglyNumber(int n) {
        
            PriorityQueue<Long> queue = new PriorityQueue<Long>();
            queue.offer(1l);    //此处1l为long型
            long res = 0;
            int[] fac = {
        2, 3, 5};
            for(int i = 0; i < n; i++) {
        
                res = queue.poll();
                for(int j = 0; j < 3; j++) {
        
                    if(!queue.contains(fac[j] * res)) {
        
                        queue.offer(fac[j] * res);
                    }
                }
            }
            return (int)res;
        }
    }

方法二：动态规划

*  初始化第一个丑数dp\[0\]为1
 *  使用三个指针i，j，k标记丑数所需要乘以的因子。
    
    在 2 x dp\[i\]、3 x dp\[j\]、5 x dp\[k\]中选择最小的数添加到数组中，并将因子对应的丑数下标后移一位

class Solution {
        
        public int nthUglyNumber(int n) {
        
            int[] dp = new int[n];
            dp[0] = 1;    //初始化
            int i = 0, j = 0, k = 0;
            int t = 0;
            for(int x = 1; x < n; x++){
        
                t = Math.min(dp[i] * 2, Math.min(dp[j] * 3, dp[k] * 5));
                dp[x] = t;
                if(t == dp[i] * 2) i++;
                if(t == dp[j] * 3) j++;
                if(t == dp[k] * 5) k++;
            }
            return dp[n - 1];
        }
    }

--------------------

### 超级丑数★★ ###

[LeetCode264. 丑数 II][LeetCode264. _ II]

【**题目**】编写一段程序来查找第 `*n*` 个超级丑数。

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

**说明:**

*  1 是任何给定 primes 的超级丑数。
 *  给定 primes 中的数字以升序排列。
 *  0 < k ≤ 100, 0 < n ≤ 106, 0 < primes\[i\] < 1000 。
 *  第 n 个超级丑数确保在 32 位有符整数范围内。

【**示例**】

输入: 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]

【**解题思路**】

同上**丑数Ⅱ**

class Solution {
        
        public int nthSuperUglyNumber(int n, int[] primes) {
        
            int[] dp = new int[n];
            dp[0] = 1;
            int[] t = new int[primes.length];
            for(int i = 1; i < n; i++){
        
                int x = Integer.MAX_VALUE;
                for(int j = 0; j < primes.length; j++){
        
                    x = Math.min(x, dp[t[j]] * primes[j]);
                }
                dp[i] = x;
                for(int j = 0; j < primes.length; j++){
        
                    if(x == dp[t[j]] * primes[j]){
        
                        t[j]++;
                    }
                }
            }
            return dp[n - 1];
        }
    }

--------------------

### 丑数Ⅲ★★ ###

【**题目**】请你帮忙设计一个程序，用来找出第 `n` 个丑数。丑数是可以被 `a` **或** `b` **或** `c` 整除的 **正整数**。

**提示：**

*  `1 <= n, a, b, c <= 10^9`
 *  `1 <= a * b * c <= 10^18`
 *  本题结果在 `[1, 2 * 10^9]` 的范围内

【**示例**】

----输入：n = 3, a = 2, b = 3, c = 5
    输出：4
    解释：丑数序列为 2, 3, 4, 5, 6, 8, 9, 10... 其中第 3 个是 4。
    
    ----输入：n = 1000000000, a = 2, b = 217983653, c = 336916467
    输出：1999999984

【**解题思路**】

`二分查找+集合运算`

若问我意知多少，一切尽在下图中

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]

class Solution {
        
        public int nthUglyNumber(int n, int a, int b, int c) {
        
            if(a == 1 || b == 1 || c == 1) return n;
            //组合最小公倍数
            long comAB  = lcm(a, b);
            long comAC  = lcm(a, c);
            long comBC  = lcm(b, c);
            long comABC = lcm(comAB, c);
            long lo = Math.min(a, Math.min(b, c));
            long hi = Math.min(a, Math.min(b, c)) * n;
            while(lo <= hi){
        
                long mid = lo + (hi - lo) / 2;
                long count = mid / a + mid / b + mid / c 
                           - mid / comAB - mid / comAC - mid / comBC + mid/ comABC;
                if(count == n){
        
                    lo = mid;
                    break;
                }
                if(count > n) hi = mid - 1;
                if(count < n) lo = mid + 1;
            }
            return (int)(lo - Math.min(lo % a, Math.min(lo % b, lo % c)));
        }
        public long lcm(long a, long b){
        
            //最小数公倍数
            return a * b / gcd(a, b);
        }
        public long gcd(long a, long b){
        
            //最大共公约数
            return a == 0 ? b : gcd(b % a, a);
        }
    }

[LeetCode263.]: https://leetcode-cn.com/problems/ugly-number/
[LeetCode264. _ II]: https://leetcode-cn.com/problems/ugly-number-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221119/24336e4597504600af71b252580a5be2.png