丑数（数学、动态规划、二分搜索）
丑数Ⅰ
给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。（1通常被认为丑数）
输入：n = 8 输出：true 解释：8 = 2 × 2 × 2
- 1
- 2
- 3
我的解法：
根据题目的描述可以得到下面结论，如果一个数为丑数，那么一定能够被2，3，5轮流整除，最后结果为1。
class Solution {
public:
bool isUgly(int n) {
if(n==0) return false;
if(n==1) return true;//先对特殊情况进行判断
while(n!=1) {
if(n%2==0||n%3==0||n%5==0) {//如果能被2，3，5整除
if(n%2==0) {
n=n/2;
}
else if(n%3==0) {
n=n/3;
}
else if(n%5==0) {
n=n/5;
}
}
else return false;//如果不能被整除
}
return true;//循环结束后表明为丑数
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
算法思想是一样的，时间和空间复杂度也相同，但是下面的解法更加简洁
leetcode解法
class Solution {
public:
bool isUgly(int n) {
if (n <= 0) {
return false;
}
vector<int> factors = {2, 3, 5};
for (int factor : factors) {//一直除2，3，5 不辗转除
while (n % factor == 0) {
n /= factor;
}
}
return n == 1;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
相同的思想下，如何让代码更加整洁，也是非常有必要的。
丑数Ⅱ
给你一个整数
n，请你找出并返回第n个 丑数 。丑数 就是只包含质因数
2、3和/或5的正整数。输入：n = 10 输出：12 解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
- 1
- 2
- 3
我的解法：
分析题目，结合丑数Ⅰ，从2开始往后遍历，判断每一个数是否为丑数，直至满足题意的第n个丑数。
class Solution {
public:
int nthUglyNumber(int n) {
int ans;
for(int i=1,j=1;j<=n;i++) {
if(isUgly(i)==true) {//isUgly()函数声明在丑数Ⅰ代码段
j++;
ans=i;
}
}
return ans;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
错误原因：
提交结果的时候报错为超出时间限制，分析代码可以看出调用了两个循环。
leetcode解法：
1. 动态规划
对于丑数而言，根据其定义可以看出，任何丑数都是由2，3，5乘积而成的，即可以通过2，3，5不断构造新的丑数。
算法思想：
-
定义数组dp，dp[i]存储第i个丑数，由定义可知，dp[1]=1；
-
定义三个指针数p2，p3，p5，初始值均初始化为1；
-
当 2 ≤ i ≤ n时，取dp[i]=min { dp[p2]×p2，dp[p3]×p3，dp[p5]×p5 }；
（如果是 dp[i-1]×p2|p3|p5，那么会存在遗漏情况，并且上述的最小值一定大于已经存储的丑数）
-
然后分别比较dp[i]和 { dp[p2]×p2，dp[p3]×p3，dp[p5]×p5 }的大小；
-
如果相等，那么对应的指针值加1，如此循环，直至到第n个丑数结束。
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> dp(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] = min(min(num2, num3), num5);
if (dp[i] == num2) {
p2++;
}
if (dp[i] == num3) {
p3++;
}
if (dp[i] == num5) {
p5++;
}
}
return dp[n];
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
丑数Ⅲ
给你四个整数：
n、a、b、c，请你设计一个算法来找出第n个丑数。丑数是可以被
a或b或c整除的 正整数 。
注意题目描述，不为因子，而是能够整除的正整数。
我的解法：
参照丑数Ⅱ的动态规划和三指针的解法，也采用动态规划和三指针：
class Solution {
public:
int nthUglyNumber(int n, int a, int b, int c) {
vector<int> dp(n+1);
vector<int> p={0,1,1,1};//整除基 依此生成丑数
int p1=a,p2=b,p3=c;
for(int i=1;i<=n;i++) {
int num1=p[1]*p1;
int num2=p[2]*p2;
int num3=p[3]*p3;
dp[i] = min(min(num1, num2), num3);//取最小值
if (dp[i] == num1) {
p[1]++;
}
if (dp[i] == num2) {
p[2]++;
}
if (dp[i] == num3) {
p[3]++;
}
}
return dp[n];
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
在数据规模较小的情况下，可以给出正确答案，但是题目要求 109的规模大下，就会超出时间限制报错。
二分搜索以及容斥原理：
算法思想：
-
因为数据规模较大，采用动态规划或者回溯，可能会超出时间限制，因此想到二分搜索，时间复杂度为O（logn）；
-
确定二分搜索最开始的范围，左边界为 GCD(a,b,c)，右边界为 2×109,然后取 mid；
-
对于范围内的一个丑数X，如何确定它是第几个丑数，就需要用到数学集合中的容斥原理了：
sum(情况) = X/a + X/b + X/c - X/LCM(a,b) - X/LCM(a,c) - X/LCM(b,c) + X/LCM(a,b,c) (LCM表示最小公倍数)
- 如何求最大公倍数：它们的***最小公倍数 = a×b/GCD(a,b)，最大公约数可以通过辗转相除法得到。***（GDC表示最大公约数）
class Solution {
public:
int nthUglyNumber(int n, int a, int b, int c) {
long ab = getLcm(a, b);
long ac = getLcm(a, c);
long bc = getLcm(b, c);
long lcm = getLcm(ab, c);//最小公倍数
long max = 2e9;//2*10^9 题目设定的最大值
long left = min(min(a, b), c);//最初左边界
long right = max;//最初右边界
while (left < right) {
long mid = left + (right - left) / 2;//注意这里为right-left 防止溢出
long num = mid / a + mid / b + mid / c - mid / ab - mid / ac - mid / bc + mid / lcm;//容斥原理
if (num >= n) {
right = mid;
}
else {
left = mid + 1;
}
}
return left;
}
long getGcd(long a, long b) {//求最大公约数 递归（如果用while 超出时间限制）
return !b ? a : gcd(b, a % b);
}
long getLcm(long a, long b) {//求最小公倍数
return a * b / getGcd(a, b);
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
思考：为什么getGcd函数中使用递归比循环的消耗时间更少？
long getGcd(long a,long b) {//求最大公约数 循环
while (a != b) {
if (a > b) {
a = a - b;
}
else {
b = b - a;
}
}
return a;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
实际上，二者算法不同：递归的算法为辗转相除法，循环的算法为辗转相减法。相比之下前者的时间复杂度或许更低。
将辗转相除法的递归形式用循环形式改写，提交编译通过！
long getGcd(long a,long b) {
int temp;
while(b!=0) {
temp = b;
b = a%b;
a = temp;
}
return a;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9