第四讲 数学知识

1. 质数

质数: 大于1，比如：2, 3, 5, 7, 11......等只含有1和本身，这两个约数

acwing 866. 试除法判定质数 https://www.acwing.com/problem/content/868/

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            if (isPrime(x)) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
        sc.close();
    }
    public static boolean isPrime(int x) {
        if (x < 2) {
            return false;
        }
        int sqrt = (int)Math.pow(x, 0.5);
        for (int i = 2; i <= sqrt; i++) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }
}

第三章 搜索与图论

1. DFS

这里对角线数组，利用了斜率为1的直线截距，y = x + b 和 y = -x + b

那么 b = y - x 或 b = y + x

对应截距位置是否为true，表示该直线上是否有皇后

反对角线：

正对角线：

由于y - x可能为负，因此 加一个偏置n，即n + y - x

这样两个对角线数组，只需要开2n大小就能满足

第二讲 数据结构

1. KMP

算法作用：字符串S中匹配 模式串P

时间复杂度（M + N），M为S串长，N为P串长

首先需要找到：最长的相同前缀后缀：abcab是 ab 和 ab，而abc 和 cab不满足，a 和 b不满足

第一讲 基础算法

1. 前缀和

二维前缀和就是可以O（1）时间内求出任意两点组成的矩形的所有元素的和

acwing 796. 子矩阵的和 https://www.acwing.com/problem/content/description/798/

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt(), m = sc.nextInt(), q = sc.nextInt();
        int[][] arr = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                arr[i][j] += arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1];
            }
        }
        
        for (int i = 0; i < q; i++) {
            int x1 = sc.nextInt(), y1 = sc.nextInt(), x2 = sc.nextInt(), y2 = sc.nextInt();
            System.out.println(arr[x2][y2] - arr[x2][y1 - 1] - arr[x1 - 1][y2] + arr[x1 - 1][y1 - 1]);
        }
        
        sc.close();
    }
}

72. 优化算法

momentum动量：