leetcode 263. Ugly Number 、264. Ugly Number II 、313. Super Ugly Number 、204. Count Primes

263. Ugly Number

注意:1.小于等于0都不属于丑数

    2.while循环的判断不是num >= 0, 而是能被2 、3、5整除,即能被整除才去除这些数

class Solution {
public:
bool isUgly(int num) {
if(num <= )
return false;
while(num % == )
num /= ;
while(num % == )
num /= ;
while(num % == )
num /= ;
return num == ? true : false;
}
};

264. Ugly Number II

用一个数组去存第n个前面的所有整数,然后记录2 、3、5当前数的索引,每次选择最小的数。注意每次满足最小数,是索引加1,不是数值本身加1

class Solution {
public:
int nthUglyNumber(int n) {
int result[n + ];
result[] = ;
int index = ,index2 = ,index3 = ,index5 = ;
while(index < n){
index++;
int num2 = result[index2] * ;
int num3 = result[index3] * ;
int num5 = result[index5] * ;
int min_num = min(num2,min(num3,num5));
result[index] = min_num;
if(num2 == min_num)
index2++;
if(num3 == min_num)
index3++;
if(num5 == min_num)
index5++;
}
return result[n];
}
};

313. Super Ugly Number

这个和Ugly Number II 几乎是一样的,不同的是Ugly Number II是固定了2 、3、5这三个数,这个题是给一个数组。

class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
int result[n+];
result[] = ;
vector<int> index(primes.size(),);
int ind = ;
while(ind < n){
ind++;
int min_num = INT_MAX;
for(int i = ;i < primes.size();i++)
min_num = min(result[index[i]] * primes[i],min_num);
result[ind] = min_num;
for(int i = ;i < primes.size();i++){
if(result[index[i]] * primes[i] == min_num)
index[i]++;
}
}
return result[n];
}
};

204. Count Primes

质数(prime number)又称素数,有无限个。质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数。

这个题跟丑数的题一样,也需要用数组存。

思路:用j=2一个一个乘以质数i,只要乘到的值都不是质数,因为质数只能是1和他本身

class Solution {
public:
int countPrimes(int n) {
if(n <= )
return ;
vector<bool> flag(n+,true);
int count = ;
for(int i = ;i < n;i++){
if(flag[i] == true){
count++;
for(int j = ;j*i < n;j++)
flag[j*i] = false;
}
}
return count;
}
};

https://www.jianshu.com/p/12c0e91c696e

https://blog.csdn.net/github_39261590/article/details/73864039 图解

更新代码:   

    如果问题变成:求不超过10000的最大质数?用最快方法找到1到10000的质数?

    只要把上面代码里面为false的坐标+1就可以得到,但是有个问题,子循环是j=1开始的,也就是会把当前的质数也变成true,对于计算个数问题不大,但是你如果要再把这些提取出来就错误了,从2开始才是真正可以泛化到其他两个问题的通用代码

上一篇:Linux 查看磁盘容量、查找大文件、查找大目录


下一篇:Spring事务总结