丑数问题
263. 丑数
编写一个程序判断给定的数是否为丑数。
丑数就是只包含质因数 2, 3, 5 的正整数。
示例 1:
1
2
3
| 输入: 6
输出: true
解释: 6 = 2 × 3
|
示例 2:
1
2
3
| 输入: 8
输出: true
解释: 8 = 2 × 2 × 2
|
示例 3:
1
2
3
| 输入: 14
输出: false
解释: 14 不是丑数，因为它包含了另外一个质因数 7。
|
说明：
1 是丑数。- 输入不会超过 32 位有符号整数的范围: [−231, 231 − 1]/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| bool judge(int i){
while(i%2 == 0){
while(i != 0) i /= 2;
}
while(i%3 == 0){
while(i != 0) i /= 3;
}
while(i%5 == 0){
while(i != 0) i /= 5;
}
if(i == 1) return true;
else return false;
}
int divisors[] = [2,3,5];
for (auto divisor: divisors){
while(x%divisior == 0) x /= divisor;
}
return x == 1;
|
264. 丑数II
我们把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例:
1
2
3
| 输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
|
说明:
1 是丑数。n 不超过1690。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| int finduglynum(int n){
int dp[1695];
dp[0] = 0;
dp[1] = 1;
int a = 1, b = 1, c = 1;
for (int i = 2; i <= n; ++i){
int n2 = dp[a]*2, n3 = dp[b]*3, n5 = dp[c]*5;
dp[i] = min(n2, min(n3,n5));
if(dp[i] == n2) a++;
if(dp[i] == n3) b++;
if(dp[i] == n5) c++;
}
return dp[n];
}
|
313. 超级丑数
编写一段程序来查找第 *n* 个超级丑数。
超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。
示例:
1
2
3
| 输入: 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 是任何给定 primes 的超级丑数。- 给定
primes 中的数字以升序排列。
- 0 <
k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000 。
- 第
n 个超级丑数确保在 32 位有符整数范围内。
1201. 丑数 III
请你帮忙设计一个程序，用来找出第 n 个丑数。
丑数是可以被 a 或 b 或 c 整除的 正整数。
示例 1：
1
2
3
| 输入：n = 3, a = 2, b = 3, c = 5
输出：4
解释：丑数序列为 2, 3, 4, 5, 6, 8, 9, 10... 其中第 3 个是 4。
|
示例 2：
1
2
3
| 输入：n = 4, a = 2, b = 3, c = 4
输出：6
解释：丑数序列为 2, 3, 4, 6, 8, 9, 12... 其中第 4 个是 6。
|
示例 3：
1
2
3
| 输入：n = 5, a = 2, b = 11, c = 13
输出：10
解释：丑数序列为 2, 4, 6, 8, 10, 11, 12, 13... 其中第 5 个是 10。
|
示例 4：
1
2
| 输入：n = 1000000000, a = 2, b = 217983653, c = 336916467
输出：1999999984
|
提示：
1 <= n, a, b, c <= 10^91 <= a * b * c <= 10^18- 本题结果在
[1, 2 * 10^9] 的范围内
This is copyright.