每一个数都可以分解成素数的乘积。例如 84 = 22 * 31 * 50 * 71 * 110 * 130 * 170 * …
-
整除
每一个数都可以分解成素数的乘积。则
令 x = 2m0 * 3m1 * 5m2 * 7m3 * 11m4 * …
令 y = 2n0 * 3n1 * 5n2 * 7n3 * 11n4 * …
如果 x 整除 y（y mod x == 0），则对于所有 i，mi <= ni。
-
最大公约数和最小公倍数
x 和 y 的最大公约数为：gcd(x,y) = 2min(m0,n0) * 3min(m1,n1) * 5min(m2,n2) * ...
x 和 y 的最小公倍数为：lcm(x,y) = 2max(m0,n0) * 3max(m1,n1) * 5max(m2,n2) * ...
//思路一：先判断是否是素数，然后再进行统计
//超出了时间限制
public int countPrimes(int n) {
int res=0;
for(int i=2;i<n;i++){ // 2是最小的非负素数
if(isPrime(i)){
res++;
}
}
return res;
}
//判断一个数是否是素数
private boolean isPrime(int num){
if(num<=1){
return false;
}
for(int i=2;i*i<=num;i++){
if(num%i==0){
return false;
}
}
return true;
}
@Test
public void test(){
int n=10;
System.out.println(countPrimes(n));
}//思路二：使用数组标记是否为素数
public int countPrimes(int n) {
//notPrimes[i]==true,说明 i 不是素数
//notPrimes[i]==false,说明 i 是素数
boolean[] notPrimes = new boolean[n];
int res=0;
for(int num=2;num<n;num++){ // 2 是最小的非负素数
if(notPrimes[num]){
//notPrimes[num]==true,说明num不是素数，查看下一个数
continue;
}
res++;
//即使 num 是素数
//j = num*num 必然不是素数
//j += num 即 j = num*(num+1) 也必然不是素数
//j += num 即 j = num*(num+2) 也必然不是素数
for (long j = (long) (num) * num; j < n; j += num) {
notPrimes[(int) j] = true;
}
}
return res;
}
@Test
public void test(){
int n=10;
System.out.println(countPrimes(n));
}//求 a、b 的最大公约数
public int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
@Test
public void test(){
//int a=10;
//int b=20;
//gcd(a,b)=10
int a=6;
int b=9;
//gcd(a,b)=3
System.out.println(gcd(a,b));
}public int lcm(int a,int b){
return (a*b)/gcd(a,b);
}
//先获取 a,b 最大公约数
private int gcd(int a,int b){
return b==0? a:gcd(b,a%b);
}
@Test
public void test(){
//int a=10;
//int b=20;
//lcm(a,b)=20
int a=6;
int b=9;
//lcm(a,b)=18
System.out.println(lcm(a,b));
}//思路：使用位操作和减法求解最大公约数
//对于a和b的最大公约数 gcd(a, b)，有：
//如果a和b均为偶数:gcd(a, b) = 2*gcd(a/2, b/2);
//如果a是偶数,b是奇数:gcd(a, b) = gcd(a/2, b);
//如果a是奇数,b是偶数:gcd(a, b) = gcd(a, b/2);
//如果a和b均为奇数:gcd(a, b) = gcd(b, a-b);
//注意 /2 操作可以通过右移 1 位来实现
public int gcd(int a,int b){
if(b==0){
return a;
}
if(a<b){
return gcd(b,a);
}
boolean isAEven = isEven(a);
boolean isBEven = isEven(b);
if(isAEven && isBEven){
return 2 * gcd(a >> 1, b >> 1);
}else if (isAEven && !isBEven) {
return gcd(a >> 1, b);
} else if (!isAEven && isBEven) {
return gcd(a, b >> 1);
} else {
return gcd(b, a - b);
}
}
//判断 num 是否是偶数
private boolean isEven(int num){
if(num%2==0){
return true;
}
return false;
}
@Test
public void test(){
int a=10;
int b=20;
//gcd(a,b)=10
//int a=6;
//int b=9;
//gcd(a,b)=3
System.out.println(gcd(a,b));
}public int singleNumber(int[] nums) {
int ret=nums[0];
for(int i=1;i<nums.length;i++){
ret^=nums[i];
}
return ret;
}
@Test
public void test(){
//int[] nums={2,2,1};
int[] nums={4,1,2,1,2};
System.out.println(singleNumber(nums));
}//思路：实际上就是统计 n 变成二进制后 1 的个数
//写法一：每次移动一位
public int hammingWeight(int n) {
if(n==0){
return 0;
}
int res = 0;
for(int i=0;i<32;i++){
res += (n & 1);
n >>= 1;
}
return res;
}//写法二：每次移动 4 位
public int hammingWeight(int n) {
if(n==0){
return 0;
}
int res = 0;
for(int i=0;i<8;i++){
res += bits[n & 0xf];
n >>= 4;
}
return res;
}
// bits[i] 表示数值为 i 时转换为二进制时出现 1 的次数
private int[] bits={
0,1,1,2,
1,2,2,3,
1,2,2,3,
2,3,3,4
};//思路:使用位运算性质
// a ^ a = 0
// a ^ 0 = a
public int missingNumber(int[] nums) {
int n = nums.length;
int res= 0;
for(int i=0;i<n;i++){
res ^=(nums[i]^i);
}
res^= n;
return res;
}
@Test
public void test(){
//int[] nums={3,0,1};
int[] nums={9,6,4,2,3,5,7,0,1};
System.out.println(missingNumber(nums));
}public char findTheDifference(String s, String t) {
char[] ss = s.toCharArray();
char[] tt = t.toCharArray();
char res = 0;
for(int i=0;i<ss.length;i++){
res ^= ss[i];
}
for(int i=0;i<tt.length;i++){
res ^= tt[i];
}
return res;
}
@Test
public void test(){
String s = "abcd",t = "abcde";
System.out.println(findTheDifference(s,t));
}//思路：动态规划
//memo[i]表示以A[i]结尾的所有子数组的位或结果，
//注意：这里使用set，不同的子数组位或的结果可能是相同的。
//memo[i - 1] 表示以A[i-1]结尾的所有子数组的位或结果。
//显然，子数组只有 A[i] 元素，则 A[i] 元素也是位或结果。
public int subarrayBitwiseORs(int[] A) {
Set<Integer> memo=new HashSet<>();
Set<Integer> res=new HashSet<>();
for(int a : A){
Set<Integer> cur = new HashSet<>();
//cur 存储当前以 a 元素结尾的位或结果
//为什么不适用 memo ? 因为此时 memo 实际上存的是 memo[i-1] 的位或结果
for(int num : memo){
cur.add(num | a);
}
cur.add(a);//子数组只有 A[i] 元素，则 A[i] 元素也是位或结果。
memo = cur;
res.addAll(cur);
}
return res.size();
}169
229