1.质数数量
nullhttps://leetcode.cn/problems/count-primes/description/解题思路:
遍历大于1 且小于n的每个数的倍数,设置为非质数,剩下的就都是质数了。
代码:
class Solution {
public:int countPrimes(int n) {if(n<2) return 0;vector<bool> prime(n, true);int count = n-2;for(int i=2;i<n;i++){if(prime[i]){for(int j=2*i;j<n;j=j+i){if(prime[j]){prime[j] = false;count--;}}}}return count;}
};
2.进制转换
力扣https://leetcode.cn/problems/base-7/description/
这道题是十进制转成七进制,但其实进制转换都是一样的,无论是转成二进制,还是十六进制。
十进制数num转成N进制:
a = num/N b = num%N
a赋给num,b添加在N进制结果的第一位
重复循环,直到num为0
class Solution {
public:string convertToBase7(int num) {if(num==0) return "0";string res;int flag = 1;if(num<0){flag = -1;num = -num;}int m,n;while(num>0){m = num/7;n = num%7;res = to_string(n) + res;num = m;}return flag==-1?"-"+res:res;}
};
3.阶乘的0 的个数
力扣https://leetcode.cn/problems/factorial-trailing-zeroes/description/解题思路:
找0的个数就是找5*2的个数,比如10!有两个0,因为有两个5,8个2因子。
因为2因子显然比5因子多很多,所以只需要计算5因子的数量。
当计算100!,可以知道1-100这100个数中每五个数,就有一个5的倍数,每二十五个数中,就有一个25的倍数。
所以要计算5因子的数量,就是用n/5来计算5的倍数,再用n/25来计算25的倍数,一直计算,直到n/(5^x)为0
代码:
class Solution {
public:int trailingZeroes(int n) {return n==0?0:n/5 + trailingZeroes(n/5);}
};
4.判断一个数是不是3的幂
力扣https://leetcode.cn/problems/power-of-three/description/最初的解法很简单,就是这个数循环整除3,看余数是不是为零。
可以做出来,但是比较慢。
class Solution {
public:bool isPowerOfThree(int n) {while(n>=3){if(n%3) return false;n = n/3;}return n==1?true:false;}
};
另一个解法是:如果n是3的幂,那么存在一个整数m,使得m^3 = n。
所以 m = log3(n) = log10(n) / log10(3),对m取余数来判断m是不是整数,m是整数,则说明n是3的幂。
class Solution {
public:bool isPowerOfThree(int n) {return fmod(log10(n)/log10(3), 1) == 0;}
};