丑数
题目
给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。1 通常被视为丑数。
题解
根据丑数的定义，00 和负整数一定不是丑数。
当 n>0n>0 时，若 nn 是丑数，则 nn 可以写成 n = 2^a \times 3^b \times 5^cn=2
a
×3
b
×5
c
的形式，其中 a,b,ca,b,c 都是非负整数。特别地，当 a,b,ca,b,c 都是 00 时，n=1n=1。
为判断 nn 是否满足上述形式，可以对 nn 反复除以 2,3,52,3,5，直到 nn 不再包含质因数 2,3,52,3,5。若剩下的数等于 11，则说明 nn 不包含其他质因数，是丑数；否则，说明 nn 包含其他质因数，不是丑数。
class Solution {
public boolean isUgly(int n) {
if(n<=0)
return false;
while(n%2==0)
n=n/2;
while(n%3==0)
n=n/3;
while(n%5==0)
n=n/5;
return n==1;
}
}
丑数2
题目
264. 丑数 II
给你一个整数 n ，请你找出并返回第 n 个 丑数 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。
解法一 最小堆和set去重
要得到从小到大的第 nn 个丑数，可以使用最小堆实现。
初始时堆为空。首先将最小的丑数 11 加入堆。
每次取出堆顶元素 xx，则 xx 是堆中最小的丑数，由于 2x, 3x, 5x2x,3x,5x 也是丑数，因此将 2x, 3x, 5x2x,3x,5x 加入堆。
上述做法会导致堆中出现重复元素的情况。为了避免重复元素，可以使用哈希集合去重，避免相同元素多次加入堆。
在排除重复元素的情况下，第 nn 次从最小堆中取出的元素即为第 nn 个丑数。
使用最小堆，会预先存储较多的丑数，导致空间复杂度较高，维护最小堆的过程也导致时间复杂度较高。
import java.util.HashSet;
import java.util.PriorityQueue;
class Solution {
public int nthUglyNumber(int n) {
HashSet<Long> visited= new HashSet<Long>();
PriorityQueue<Long> q=new PriorityQueue<Long>();
q.add(1l);
long res=0;
while(n-->0)
{
res=q.poll();
long a=res*2,b=res*3,c=res*5;
if(!visited.contains(a))
{
q.add(a);
visited.add(a);
}
if(!visited.contains(b))
{
q.add(b);
visited.add(b);
}
if(!visited.contains(c))
{
q.add(c);
visited.add(c);
}
}
return (int)res;
}
}
解法二 动态规划,三指针
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的避免了重复的情况，算过了，指针加加，就不用再算了
if (dp[i] == num2) {
p2++;
}
if (dp[i] == num3) {
p3++;
}
if (dp[i] == num5) {
p5++;
}
}
return dp[n];
}
}
超级丑数
超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。
给你一个整数 n 和一个整数数组 primes ，返回第 n 个 超级丑数 。
题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。
示例 1：
输入：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] 。
解法
解法与丑数2一致，两种方法都行。