素数

判断n是素数

解法一，暴解

如果n是素数，那么n不能被任何数（1和n除外）的数字整除。暴力的方法就是从2~n-1进行探测，探测\(\frac{n}{k}, k = 2,3,...,n-1\) 是否是整数

private boolean ifPrime(int n){
  if(n < 2) return false;
  for(int k = 2; k < n; ++k){
    if(n % k == 0) return false;
  }
  return true;
}

解法二，优化

事实上，如果n不是素数，那么一定存在\(n = a \times b\) ，而a和b的可能性有：

a	b
2	n/2
3	n/3
...	...
n/3	3
n/2	2

我们发现，a和b有重复计算的部分，即如果a < sqrt(n) , 那么b > sqrt(n) 。因此a只用探测到sqrt(n)即可。

private boolean ifPrime(int n){
  if(n < 2) return false;
  int sqrt = (int)Math.sqrt(n);
  for(int k = 2; k < sqrt; ++k){
    if(n % k == 0) return false;
  }
  return true;
}

解法三，素数筛——生成素数序列：埃拉托斯特尼筛法

素数筛能非常高效地生成素数序列。原理是剔除所有可被素数整除的非素数。

列出2~max所有的数字
剔除所有2的倍数（2保留）
剔除下一个没有被划掉的倍数
循环直到max

public int countPrimes(int n) {
       boolean[] notPrime = new boolean[n]; // notPrime[i]==true代表i-1不是素数
       int counter = 0;
       for(int i = 2; i <= n; ++i){
           if(notPrime[i] == false){
               ++counter;
               for(int k = 2; k*i < n; ++k){
                   notPrime[k*i] = true;
               }
           }
       }
       return counter;
   }

面积问题

Perfect Rectangle

假设一个矩形有四个数表示[a,b,c,d] 。其中[a,b] 代表left bottom角的坐标，[c,d] 表示right top的坐标。给一堆矩形，判断它是否能刚刚好（不重合也不漏缺）地构成一个大的矩形

这道题耗费了较长时间。因为没想通。

核心思想就是:能够正好围成一个矩形的情况就是: 有且只有:

最左下最左上最右下最右上的四个点只出现过一次,其他肯定是成对出现的(保证完全覆盖)
上面四个点围成的面积,正好等于所有子矩形的面积之和(保证不重复)

class Pair{
    int x;
    int y;
    Pair(int x, int y){
        this.x = x;
        this.y = y;
    }

    public boolean equals(Object oo){
        Pair o = (Pair)oo;
        return this.x == o.x && this.y == o.y;
    }
    public int hashCode(){ //在使用HashSet（contains也是调用HashMap中的方法）、HashMap等集合时，如果用到contains系列方法时，记得需同时重写equals与hashCode方法。
        return x + y*10;
    }
    public String toString(){
        return  "["+ x + "," + y + "]";
    }
}
int left = 0, bottom = 1, right = 2, top = 3;
public boolean isRectangleCover(int[][] rectangles) {
    // 能够成矩形的条件：
    // 1. 最边上的四个点只到达了一次
    // 2. 其余的所有点到达了两次
    // 3. 最大矩阵面积 = 所有面积的和 // 这个很容易忽略
    HashMap<Pair,Integer> memo = new HashMap<>();

    int[] corner = new int[4];
    for(int i = 0; i < rectangles[0].length; ++i){
        corner[i] = rectangles[0][i];
    }
    int area = 0;
    int[][] corners4 = {{left, bottom},{right,top}, {left,top},{right,bottom}};
    for(int[] rectangle : rectangles){
        corner[left] = Math.min(rectangle[left], corner[left]);
        corner[bottom] = Math.min(rectangle[bottom], corner[bottom]);
        corner[top] = Math.max(rectangle[top],corner[top]);
        corner[right] = Math.max(rectangle[right], corner[right]);
        for(int[] cor : corners4){
            Pair pair = new Pair(rectangle[cor[0]], rectangle[cor[1]]);
            memo.put(pair, memo.getOrDefault(pair, 0) + 1);
        }
        area += (rectangle[2] -rectangle[0])*(rectangle[3] - rectangle[1]);
    }
    // 检查面积
    if(area != (corner[2] - corner[0])*(corner[3] - corner[1])) return false;
    // 检查四个角是否只到达了一次
    for(int[] cor : corners4){
        Pair pair = new Pair(corner[cor[0]], corner[cor[1]]);
        if(memo.getOrDefault(pair,0) != 1) return false;
        memo.remove(pair);
    }
    // 检查其余节点是否都是两次
    for(Map.Entry<Pair, Integer> entry : memo.entrySet()){
        if(entry.getValue() != 2 && entry.getValue() != 4) return false;
    }
    return true;
}

Perfect Number

定义完美数字为：除了它自己以外的所有除数相加都等于它本身。判断一个数是不是一个完美数字。

与上面的类似解法

public boolean checkPerfectNumber(int num) {
        if(num == 1) return false;
        // 寻找所有的除数
        int sum = 1;
        int max = (int)Math.sqrt(num);
        for(int i = 2; i <= max; ++i){
            if(num % i == 0){
                sum += i;
                sum += num/i;
            }
        }
        return sum == num;
    }

组合数学

环形染色问题

如果把一个圆环分成n个区域\(A_n\)。用m种不同颜色为这n个区域染色。要求相邻两个区域\(A_i\) 和 \(A_{i+1}\) 颜色不同，则不同的染色方式有多少种？

对于区域\(A_1\) ，有m种染色法；
对于区域\(A_2,...,A_{n-1}\) ，分别有m-1种染色法
假设暂时不考虑\(A_n\) 与\(A_1\) ，那么对于区域\(A_n\) ，有\(m-1\) 种染法。
- 如果\(A_n\) 与\(A_1\) 同色，那么就将这两个看成同一个区域，这就退化成了n-1个区域的染色种类，即\(a_{n-1}\)
因此有\[a_n + a_{n-1} = m(m-1)^{n-1}\]

接下来通过数列递推公式求通项公式：

由于对上式两边同时减去\((m-1)^n\)：

\[a_n + a_{n-1} - (m-1)^n = m(m-1)^{n-1} - (m-1)^n\] ，递推可得：

因此，环形染色问题的解为：

\[a_n = (m-1)^n + (-1)^n(m-1)\]

计算几何

Valid Square

验证给定的四个点是否能组成正方形。

class Solution {
    public boolean validSquare(int[] a, int[] b, int[] c, int[] d) {
        
        /** 矩形: 对角线一定相等且垂直且平分
        **/
        if(diagonal(a,b,c,d) && equal(a,b,c,d) && divideEqual(a,b,c,d)) return true;
        if(diagonal(a,c,b,d) && equal(a,c,b,d) && divideEqual(a,c,b,d)) return true;
        if(diagonal(a,d,c,b) && equal(a,d,c,b) && divideEqual(a,d,c,b)) return true;
        return false;
    }
    // 判断ab与cd互相平分
    private boolean divideEqual(int[] a, int[] b, int[] c, int[] d){
        int[] media_ab = {a[0] + b[0], a[1] + b[1]};
        int[] media_cd = {c[0] + d[0], c[1] + d[1]};
        return media_ab[0] == media_cd[0] && media_ab[1] == media_cd[1];
    }
    /**判断ab与cd两直线相等**/
    private boolean equal(int[] a, int[] b, int[] c, int[] d){
        return dist(a,b) != 0 && dist(a,b) == dist(c,d);
    }
    private int dist(int[] a, int[] b){
        return (a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1]);
    }
    /**
    判断ab与cd两直线是否垂直
    **/
    private boolean diagonal(int[] a, int[] b, int[] c, int[] d){
        int[] vector_ab = {a[0] - b[0], a[1] - b[1]};
        int[] vector_cd = {c[0] - d[0], c[1] - d[1]};
        
        // dot
        int dot = vector_ab[0]*vector_cd[0] + vector_ab[1]*vector_cd[1];
        return dot == 0;
    }
}

甲乙小朋友的房子

算法-数学相关习题

素数