基础算法

1.输入和输出

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            System.out.println(a + b);
        }
    }
}

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException { // 记得抛异常
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
        while (st.nextToken() != StreamTokenizer.TT_EOF){
            // String str = st.sval; //读取String类型数据
            int a = (int) st.nval;  // 读取第一个数字a
            st.nextToken();      // 读取下一个token
            double b = (double) st.nval;   // 读取第二个数字b
            pw.println(a + b);
        }
        pw.flush(); // 最后flush

    }
}

2.map计数

for (int num : nums){
    map.put(num, map.getOrDefault(num, 0) + 1);
}

3.快速排序

// 调用：quick_sort(a, 0, n - 1)
void quick_sort(int[] q, int l, int r){
    if (l >= r)
        return;
    // i从左往右扫描找比x大的，j从右往左扫描找比x小的
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j){
        while (q[++i] < x);
        while (q[--j] > x);
        if (i < j){
            int temp = q[i];
            q[i] = q[j];
            q[j] = temp;
        }
    }
    // 从上到下分治
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

4.归并排序

    int[] temp = new int[n]; // 辅助数组
    // 将[l, r]排好序
    void merge_sort(int[] q, int l, int r){
        if (l >= r)
            return;
        int mid = l + r >> 1;
        // 从下到上
        // 分
        merge_sort(q, l, mid);
        merge_sort(q, mid + 1, r);
        // 治
        // k:辅助数组的索引, i:左数组索引, j:右数组索引
        int k = 0, i = l, j = mid + 1;
        while (i <= mid && j <= r){
            if (q[i] <= q[j])
                temp[k++] = q[i++];
            else
                temp[k++] = q[j++];
        }
        // 左数组不为空
        while (i <= mid)
            temp[k++] = q[i++];
        // 右数组不为空
        while (j <= r)
            temp[k++] = q[j++];
        // 复制到原数组
        for (i = l, k = 0; i <= r; i++, k++){
            q[i] = temp[k];
        }
    }

5.二分

    // 是否满足条件
    boolean check(int x){/*....*/}
    // 找左边界(满足条件的最小的那个)
    int bsearch(int l, int r){
        while (l < r){
            int mid = l + r >> 1;
            if (check(mid))
                r = mid;
            else
                l = mid + 1;
        }
        return r;
    }
    // 找右边界(满足条件的最大的那个)
    int bsearch(int l, int r){
        while (l < r){
            int mid = l + r + 1 >> 1;
            if (check(mid))
                l = mid;
            else
                r = mid - 1;
        }
        return l;
    }

6.一维前缀和

    //S(i+1) = S(i) + a(i)
    // a(l)+a(l+1)+...+a(r) = S(r+1)-S(l)
    for (int i = 0; i < n; i++){
        s[i + 1] = s[i] + a[i];
    }

7.一维差分

    // 给区间[l, r]中的每个数加上c
    void insert(int l, int r, int c){
        B[l] += c;
        B[r + 1] -= c;
    }
    // 初始化差分数组
    for (int i = 0; i < n; i++) {
        insert(i, i, a[i]);
    }
    // 输出前缀和数组
    for (int i = 0; i < n; i++){
        B[i + 1] += B[i];
    }

8.双指针

    // i从头到尾，j不回头
    for (int i = 0, j = 0; i < n; i++){
        while (j < i && check(i, j))
            j++;
    }

9.位运算

1. 求n的右数第k位二进制数

n >> k & 1;

2. 返回n的最后一位1

// 101100返回100
int lowbit(int x){
    return x & -x; // -x是x的反码加1
}

3. 清除最右边的1

// 101100变为101000
n % (n - 1);

4. 统计一个数的二进制有多少个1

Integer.bitCount(int x);

10.最大公约数

int gcd(int a, int b){
    return b != 0 ? gcd(b, a % b) : a;
}

11.求最大子数组之和（Kadane算法）

public int maxSubArray(int[] nums) {
    int pre = 0, maxAns = nums[0];
    for (int x : nums) {
        pre = Math.max(pre + x, x);
        maxAns = Math.max(maxAns, pre);
    }
    return maxAns;
}