Skip to content

Latest commit

 

History

History
446 lines (378 loc) · 9.74 KB

8_数学问题.md

File metadata and controls

446 lines (378 loc) · 9.74 KB
Raw

数学问题

一、素数

1、素数分解

每一个数都可以分解成素数的乘积。例如 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) * ...

*2、计数素数（204）

204. 计数质数

//思路一：先判断是否是素数，然后再进行统计
//超出了时间限制
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));
}

二、最大公约数和最小公倍数

*1、最大公约数

//求 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));
}

2、最小公倍数

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));
}

*3、使用位操作和减法求解最大公约数

//思路：使用位操作和减法求解最大公约数
//对于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));
}

三、位运算

1、只出现依次的数字(136)

136. 只出现一次的数字

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));
}

2、位1的个数(191)

191. 位1的个数

//思路：实际上就是统计 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
};

3、缺失数字（268）

268. 缺失数字

//思路:使用位运算性质
// 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));
}

4、找不同（389）

389. 找不同

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));
}

*5、子数组按位或操作（898）

898. 子数组按位或操作

//思路：动态规划
//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();
}

四、求众数

1、求众数（169）

169. 求众数

/**
 * 思路一：
 * 先对数组排序，最中间那个数出现次数一定多于 n / 2。
 */
public int majorityElement(int[] nums) {
    Arrays.sort(nums);
    return nums[nums.length/2];
}
/**
 * 思路二：
 * 利用 Boyer-Moore Majority Vote Algorithm 来解决这个问题，使得时间复杂度为 O(N)。
 * 可以这么理解该算法：
 * 使用 cnt 来统计一个元素出现的次数，当遍历到的元素和统计元素不相等时，令 cnt--。
 * 如果前面查找了 i 个元素，且 cnt == 0，说明前 i 个元素没有 majority，或者有 majority，
 * 但是出现的次数少于 i / 2，因为如果多于 i / 2 的话 cnt 就一定不会为 0。
 * 此时剩下的 n - i 个元素中，majority 的数目依然多于 (n - i) / 2，因此继续查找就能找出 majority。
 */
public int majorityElement(int[] nums) {
    int cnt=0;
    //假设第一个元素是主元素
    int majority=nums[0];
    for(int i=0;i<nums.length;i++){
        int num=nums[i];
        /**
         * 如果前面查找了 i 个元素，且 cnt == 0，说明前 i 个元素没有 majority，
         * 或者有 majority，但是出现的次数少于 i / 2，因为如果多于 i / 2 的话 cnt 就一定不会为 0。
         */
        if(cnt==0){
            majority=num;
        }
        /**
         * 剩下的 n - i 个元素中，majority 的数目依然多于 (n - i) / 2，
         * 因此继续查找就能找出 majority。
         */
        if(majority==num){
            cnt++;
        }else{
            cnt--;
        }
    }
    return majority;
}

2、 求众数 II（229）

229. 求众数 II

public List<Integer> majorityElement(int[] nums) {
    List<Integer> res=new ArrayList<>();
    if(nums==null || nums.length==0){
        return res;
    }
    //出现次数大于三分之n的数字最多只有 2 个
    int majority1=nums[0];
    int majority2=-nums[0];
    int cnt1=0;
    int cnt2=0;

    for(int num : nums){
        if(majority1==num){
            cnt1++;
        }else if(majority2==num){
            cnt2++;
        }else if(cnt1==0){
            majority1=num;
            cnt1=1;
        }else if(cnt2==0) {
            majority2 = num;
            cnt2 = 1;
        } else{
            cnt1--;
            cnt2--;
        }
    }

    cnt1=0;
    cnt2=0;
    for(int num:nums){
        if(majority1==num){
            cnt1++;
        }else if(majority2==num){
            cnt2++;
        }
    }
    int n=nums.length;
    if(cnt1>n/3){
        res.add(majority1);
    }
    if(cnt2>n/3){
        res.add(majority2);
    }
    return res;
}