正数，原码 == 反码 == 补码
负数
- 反码，除符号位取反
- 补码，反码 + 1
二进制没有减法运算，即计算机没有减法运算。(A原码 - B原码) == (A原码 + B补码) 即将时钟逆时针转动，转化为顺时针转动
10000000 => -0，00000000 => +0。出现两个0，而-0没有意义。所以就规定-0时候，储存数字为-128

2. 位运算

public class _01_PrintBinary {

    private static void print(int num) {
        for (int i = 31; i >= 0; i--) {
            // flag 位运算为0，或者其他10进制数
            // 左移不带符号的，右移带符号的
            int flag = num & (1 << i);
            // System.out.print( flag == 1 ? "1" : "0"); 是错误的
            System.out.print(flag == 0 ? "0" : "1");
        }
        System.out.println();
    }

    /**
     * 打印int的底层二进制数
     * int 4字节，32位。左移一位num * 2
     */
    @Test
    public void test1() {
        int num = 1;
        print(num);         // 00000000000000000000000000000001
        print(num << 1);    // 00000000000000000000000000000010
        print(num << 2);    // 00000000000000000000000000000100
    }

    /**
     * 整型最大值21亿多，01111111111111111111111111111111
     * C++ 无符号整型 2^32 - 1
     * java 有符号整型 (-2^31) ~ (2^31-1)
     */
    @Test
    public void test2() {
        int maxValue = Integer.MAX_VALUE;
        int minValue = Integer.MIN_VALUE;

        // 2^31-1 (01111111111111111111111111111111)
        System.out.println(maxValue);
        print(maxValue);
        // -2^31 (10000000000000000000000000000000)
        System.out.println(minValue);
        print(minValue);
    }

    /**
     * 负数：取反 + 1
     * 1. 通过首位确定符号
     * 2. (取反 + 1) 按绝对值来算
     */
    @Test
    public void test3() {
        print(-1);          // 11111111111111111111111111111111
        int minValue = Integer.MIN_VALUE;
        print(minValue);    // 10000000000000000000000000000000

        int a = 1;          // 00000000000000000000000000000001
        int b = ~a;         // 11111111111111111111111111111110
        print(a);
        print(b);
    }

    /**
     *  & | ~ ^ (与、或、取反、异或)
     */
    @Test
    public void test4() {
        int a = 1;
        int b = ~a;
        print(a);       // 00000000000000000000000000000001
        print(b);       // 11111111111111111111111111111110
        System.out.println("=============");

        int c = 12319283;
        int d = 3819283;
        print(c);       // 00000000101110111111101000110011
        print(d);       // 00000000001110100100011100010011
        System.out.println("=============");
        print(c | d);   // 00000000101110111111111100110011
        print(c & d);   // 00000000001110100100001000010011
        print(c ^ d);   // 00000000100000011011110100100000
    }

    /**
     * 右移
     */
    @Test
    public void test5() {
        int a = Integer.MIN_VALUE;
        print(a);       // 10000000000000000000000000000000
        print(a >> 1);  // 带符号右移     11000000000000000000000000000000
        print(a >>> 1); // 不带符号右移   01000000000000000000000000000000
    }

    /**
     * 相反数 (取反 + 1)
     * 0 （取反 + 1 溢出舍弃，仍为0）
     */
    @Test
    public void test6() {
        int c = Integer.MIN_VALUE;
        // int d = ~c + 1;
        int d = -c;
        print(c);   // 10000000000000000000000000000000
        print(d);   // 10000000000000000000000000000000
    }
}

1. 两数比较

/**
 * 返回两个数中较大的数
 */
public class _03_GetMax {

    /**
     * 取 (0, 1) 相反
     */
    public static int flip(int n) {
        return n ^ 1;
    }

    /**
     * 判断一个数正、负
     */
    public static int sign(int n) {
        // (n >> 31) & 1 判断正、负
        return flip((n >> 31) & 1);
    }

    public static int getMax1(int a, int b) {
        int c = a - b;
        int scA = sign(c);
        int scB = flip(scA);
        // (scA, scB) 一个为1，一个为0
        return a * scA + b * scB;
    }

    public static int getMax2(int a, int b) {
        int c = a - b;
        int sa = sign(a);
        int sb = sign(b);
        int sc = sign(c);           // 负值可能溢出

        int difSab = sa ^ sb;       // 异号1，同号0
        int sameSab = flip(difSab);
        // 同号：不可能溢出，大小取决于sc
        // 异号：大小取决于sa正负
        int returnA = difSab * sa + sameSab * sc;

        int returnB = flip(returnA);
        return a * returnA + b * returnB;
    }

    public static void main(String[] args) {
        int a = 16;
        int b = 19;
        System.out.println(getMax1(a, b));
        System.out.println(getMax2(a, b));

        a = 2147483647;
        b = -2147480000;
        System.out.println(getMax1(a, b)); // wrong answer because of overflow
        System.out.println(getMax2(a, b));
    }

}

3. 算法

有具体的问题
有设计解决这个问题的具体流程
有评价处理流程的可量化指标（时间复杂度、空间复杂度）

分类：

明确知道怎么算的流程
明确知道怎么尝试的流程

1. 阶乘和

1! + 2! + 3! + 4! + … + N!

public class _02_SumOfFactorial {

    /**
     * 阶乘和, 算法一
     */
    public static long f1(int N) {
        long ans = 0;
        for (int i = 1; i <= N; i++) {
            ans += factorial(i);
        }
        return ans;
    }

    /**
     * 阶乘算法
     */
    public static long factorial(int N) {
        long ans = 1;
        for (int i = 1; i <= N; i++) {
            ans *= i;
        }
        return ans;
    }

    // ---------------------------------------------

    /**
     * 阶乘和, 算法二
     */
    public static long f2(int N) {
        long ans = 0;
        long cur = 1;
        for (int i = 1; i <= N; i++) {
            cur = cur * i;
            ans += cur;
        }
        return ans;
    }

    /**
     * 1! + 2! + 3! + 4! + … + N!
     */
    public static void main(String[] args) {
        int N = 10;
        System.out.println(f1(N));
        System.out.println(f2(N));
    }
}

2. 排序

public class _03_Sort {

    /**
     * 数组交换元素
     */
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }

    /**
     * 打印数组
     */
    public static void printArray(int[] arr) {
        for (int j : arr) {
            System.out.print(j + " ");
        }
        System.out.println();
    }

    // ------------------------------------------------------

    /**
     * 1. 选择排序
     */
    public static void selectSort(int[] arr) {
        // 处理边界条件
        if (arr == null || arr.length < 2) {
            return;
        }
        // 0 ~ n-1
        // 1 ~ n-1
        // 2 ~ n-1
        int N = arr.length;
        for (int i = 0; i < N; i++) {
            int minValueIndex = i;
            for (int j = i + 1; j < N; j++) {
                minValueIndex = arr[j] < arr[minValueIndex] ? j : minValueIndex;
            }
            swap(arr, i, minValueIndex);
        }
    }

    // ------------------------------------------------------

    /**
     * 2. 冒泡排序
     */
    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // 0 ~ n-1
        // 0 ~ n-2
        // 0 ~ n-3
        int N = arr.length;
        for (int end = N - 1; end >= 0; end--) {
            // 0 ~ end （相临元素比较）
            // 0 1, 1 2, 2 3 ... end-1 end
            for (int second = 1; second <= end; second++) {
                if (arr[second - 1] > arr[second]) {
                    swap(arr, second - 1, second);
                }
            }
        }
    }

    // ------------------------------------------------------

    /**
     * 3. 插入排序1（摸牌，新来一张牌）
     */
    public static void insertSort1(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // 0 ~ 0 完成
        // 0 ~ 1
        // 0 ~ 2
        // 0 ~ 3
        // 0 ~ n-1
        int N = arr.length;
        for (int end = 1; end < N; end++) {
            int newNumIndex = end;
            while (newNumIndex - 1 >= 0 && arr[newNumIndex - 1] > arr[newNumIndex]) {
                swap(arr, newNumIndex - 1, newNumIndex);
                newNumIndex--;
            }
        }
    }

    // ------------------------------------------------------

    /**
     * 4. 插入排序2（摸牌，新来一张牌）
     */
    public static void insertSort2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int N = arr.length;
        for (int end = 1; end < N; end++) {
            for (int pre = end - 1; pre >= 0 && arr[pre] > arr[pre + 1]; pre--) {
                swap(arr, pre, pre + 1);
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {7, 1, 3, 5, 1, 6, 8, 1, 3, 5, 7, 5, 6};
        printArray(arr);
        insertSort2(arr);
        printArray(arr);
    }
}

1. 选择排序

public class _04_SelectionSort {

    public static void selectionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void comparator(int[] arr) {
        Arrays.sort(arr);
    }

    // 随机数组
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        // Math.random() [0,1)
        // Math.random() * N [0,N)
        // (int)(Math.random() * N) [0, N-1]
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            // [-? , +?]
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    // for test
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        System.arraycopy(arr, 0, res, 0, arr.length);
        return res;
    }

    // for test
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1 == null ^ arr2 == null) {
            return false;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    // for test
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int j : arr) {
            System.out.print(j + " ");
        }
        System.out.println();
    }

	// for test
	public static void main(String[] args) {
		int testTime = 500_000;
		int maxSize = 100;
		int maxValue = 100;
		boolean succeed = true;
		for (int i = 0; i < testTime; i++) {
			int[] arr1 = generateRandomArray(maxSize, maxValue);
			int[] arr2 = copyArray(arr1);
			selectionSort(arr1);
			comparator(arr2);
			if (!isEqual(arr1, arr2)) {
				succeed = false;
				printArray(arr1);
				printArray(arr2);
				break;
			}
		}
		System.out.println(succeed ? "Nice!" : "Fucking fucked!");

		int[] arr = generateRandomArray(maxSize, maxValue);
		printArray(arr);
		selectionSort(arr);
		printArray(arr);
	}

}

2. 冒泡排序

public class _05_BubbleSort {

	public static void bubbleSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for (int end = arr.length - 1; end > 0; end--) {
			for (int i = 0; i < end; i++) {
				if (arr[i] > arr[i + 1]) {
					swap(arr, i, i + 1);
				}
			}
		}
	}

	// 交换arr的i和j位置上的值
	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

	// for test
	public static void comparator(int[] arr) {
		Arrays.sort(arr);
	}

	// for test
	public static int[] generateRandomArray(int maxSize, int maxValue) {
		int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
		}
		return arr;
	}

	// for test
	public static int[] copyArray(int[] arr) {
		if (arr == null) {
			return null;
		}
		int[] res = new int[arr.length];
		for (int i = 0; i < arr.length; i++) {
			res[i] = arr[i];
		}
		return res;
	}

	// for test
	public static boolean isEqual(int[] arr1, int[] arr2) {
		if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
			return false;
		}
		if (arr1 == null && arr2 == null) {
			return true;
		}
		if (arr1.length != arr2.length) {
			return false;
		}
		for (int i = 0; i < arr1.length; i++) {
			if (arr1[i] != arr2[i]) {
				return false;
			}
		}
		return true;
	}

	// for test
	public static void printArray(int[] arr) {
		if (arr == null) {
			return;
		}
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	// for test
	public static void main(String[] args) {
		int testTime = 500_000;
		int maxSize = 100;
		int maxValue = 100;
		boolean succeed = true;
		for (int i = 0; i < testTime; i++) {
			int[] arr1 = generateRandomArray(maxSize, maxValue);
			int[] arr2 = copyArray(arr1);
			bubbleSort(arr1);
			comparator(arr2);
			if (!isEqual(arr1, arr2)) {
				succeed = false;
				break;
			}
		}
		System.out.println(succeed ? "Nice!" : "Fucking fucked!");

		int[] arr = generateRandomArray(maxSize, maxValue);
		printArray(arr);
		bubbleSort(arr);
		printArray(arr);
	}

}

3. 插入排序

public class _06_InsertionSort {

    public static void insertionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 1; i < arr.length; i++) { // 0 ~ i 做到有序
            for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                swap(arr, j, j + 1);
            }
        }
    }

    // i和j, 数交换
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // for test
    public static void comparator(int[] arr) {
        Arrays.sort(arr);
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        // Math.random() ->  [0,1) 所有的小数，等概率返回一个
        // Math.random() * N -> [0,N) 所有小数，等概率返回一个
        // (int)(Math.random() * N) -> [0,N-1] 所有的整数，等概率返回一个
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())]; // 长度随机
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    // for test
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    // for test
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    // for test
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // for test
    public static void main(String[] args) {
        int testTime = 500_000;
        int maxSize = 100;      // 随机数组的长度0～100
        int maxValue = 100;     // 值：-100～100
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            insertionSort(arr1);
            comparator(arr2);
            if (!isEqual(arr1, arr2)) {
                // 打印arr1
                // 打印arr2
                succeed = false;
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");

        int[] arr = generateRandomArray(maxSize, maxValue);
        printArray(arr);
        insertionSort(arr);
        printArray(arr);
    }

}

4. 归并排序

递归版本

非递归版本

/**
 * 归并排序
 * O(nlogN)
 */
public class _01_MergeSort {

    // ------------------- 递归（二分处理） -------------------

    /**
     * 递归方法实现
     */
    public static void mergeSort1(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    /**
     * arr[L...R]范围上的数，有序！
     */
    public static void process(int[] arr, int L, int R) {
        // L R 上只有一个数，不需要排序，直接返回
        if (L == R) {
            return;
        }
        // int mid = (L + R) / 2 可能越界，写法更安全
        int mid = L + ((R - L) >> 1);
        process(arr, L, mid);
        process(arr, mid + 1, R);
        merge(arr, L, mid, R);
    }

    /**
     * 将左右排序好的数组合并 => O(n)
     *
     * @param arr arr 待排序数组
     * @param L   L 左下标
     * @param M   M 中下标
     * @param R   R 右下标
     */
    public static void merge(int[] arr, int L, int M, int R) {
        // 辅助数组
        int[] help = new int[R - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = M + 1;
        // 都不越界
        while (p1 <= M && p2 <= R) {
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        // 要么p1越界，要么p2越界。只会中一个
        // 不可能出现：共同越界
        while (p1 <= M) {
            help[i++] = arr[p1++];
        }
        while (p2 <= R) {
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; i++) {
            arr[L + i] = help[i];
        }
    }

    // ------------------- 非递归（步长处理） -------------------

    /**
     * 归并排序（非递归实现，手敲版）=> O(nlogN)
     */
    public static void mergeSort2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // 步长
        int step = 1;
        int N = arr.length;
        // 步长 == 总长度，右边已经没有数据了
        while (step < N) {
            int L = 0;
            while (L < N) {
                int M;
                // 规避 M 越界
                // (N - 1) - L + 1
                if (N - L >= step) {
                    M = L + step - 1;
                } else {
                    M = N - 1;
                }
                if (M == N - 1) {
                    break;
                }

                int R;
                // 规避 R 越界
                // (N - 1) - (M + 1) + 1
                if (N - 1 - M >= step) {
                    // R = (M + 1) + step - 1;
                    R = M + step;
                } else {
                    R = N - 1;
                }
                merge(arr, L, M, R);

                // 下一个L
                if (R == N - 1) {
                    break;
                } else {
                    L = R + 1;
                }
            }
            // 防止step溢出，必须是>，(N / 2)向下取整
            if (step > N / 2) {
                break;
            }
            step *= 2;
        }
    }

    /**
     * 归并排序（非递归实现，标准版）
     */
    public static void mergeSort3(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int N = arr.length;
        int mergeSize = 1;
        while (mergeSize < N) {
            int L = 0;
            while (L < N) {
                if (mergeSize >= N - L) {
                    break;
                }
                int M = L + mergeSize - 1;
                int R = M + Math.min(mergeSize, N - M - 1);
                merge(arr, L, M, R);
                L = R + 1;
            }
            if (mergeSize > N / 2) {
                break;
            }
            mergeSize <<= 1;
        }
    }

    // ------------------- 对数器 -------------------

    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        System.arraycopy(arr, 0, res, 0, arr.length);
        return res;
    }

    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int j : arr) {
            System.out.print(j + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int testTime = 500_000;
        int maxSize = 100;
        int maxValue = 100;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            mergeSort1(arr1);
            mergeSort2(arr2);
            if (!isEqual(arr1, arr2)) {
                System.out.println("出错了！");
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }
        System.out.println("测试结束");
    }

}

5. 快速排序

<=区、>区

<区、=区、>区

快速排序原理。不断得在 <区、>区 进行区域划分

public class _02_PartitionAndQuickSort {

    /**
     * [3 6 9 7 6 2 8 2 7]
     * 一个数组中：<= 放左边，> 放右边。内部可以无序
     */
    public static void splitNum1(int[] arr) {
        // 小于等于区下标
        int lessEqualR = -1;
        int index = 0;
        int N = arr.length;
        while (index < N) {
            if (arr[index] <= arr[N - 1]) {
                // 当前值和<=区的下一个交换
                swap(arr, ++lessEqualR, index++);
            } else {
                index++;
            }
        }
    }

    /**
     * [3 4 4 6 4 7 0 1 5 2 4]
     * 一个数组中：< 放左边，= 放中间，> 放右边。内部可以无序
     */
    public static void splitNum2(int[] arr) {
        int N = arr.length;
        int lessR = -1;
        int moreL = N - 1;
        int index = 0;
        // arr[N-1] 划分值
        while (index < moreL) {
            // curr和<区下一个交换，<区扩充
            if (arr[index] < arr[N - 1]) {
                swap(arr, ++lessR, index++);
            }
            // curr和<区下一个交换，<区扩充
            else if (arr[index] > arr[N - 1]) {
                swap(arr, --moreL, index);
            }
            // 直接下一个
            else {
                index++;
            }
        }
        swap(arr, moreL, N - 1);
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // ---------------------------------------------------------------

    /**
     * arr[L...R]范围上，拿arr[R]做划分值
     * L....R   `<区、=区、>区1`
     * int[] => 等于区左右边界
     */
    public static int[] partition(int[] arr, int L, int R) {
        if (L > R) {
            return new int[]{-1, -1};
        }
        if (L == R) {
            return new int[]{L, R};
        }
        int lessR = L - 1;
        int moreL = R;
        int index = L;
        while (index < moreL) {
            if (arr[index] < arr[R]) {
                swap(arr, ++lessR, index++);
            } else if (arr[index] > arr[R]) {
                swap(arr, --moreL, index);
            } else {
                index++;
            }
        }
        swap(arr, moreL, R);
        return new int[]{lessR + 1, moreL};
    }

    // ---------------------------------------------------------------

    /**
     * 递归快排
     */
    public static void quickSort1(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    /**
     * 不断对`<区、>区`进行递归快速排序。=区已经排好确定
     */
    public static void process(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        // 随机确定一个最右数
        swap(arr, L + (int) (Math.random() * (R - L + 1)), R);

        int[] equalE = partition(arr, L, R);
        // equalE[0] 等于区域第一个数
        process(arr, L, equalE[0] - 1);
        // equalE[1] 等于区域最后一个数
        process(arr, equalE[1] + 1, R);
    }

    // ------------------------------ 非递归快排 ------------------------------

    public static class Job {
        public int L;
        public int R;

        public Job(int left, int right) {
            L = left;
            R = right;
        }
    }

    /**
     * 非递归快排
     */
    public static void quickSort2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        Stack<Job> stack = new Stack<>();
        stack.push(new Job(0, arr.length - 1));
        while (!stack.isEmpty()) {
            Job cur = stack.pop();
            int[] equals = partition(arr, cur.L, cur.R);
            // 有 < 区域
            if (equals[0] > cur.L) {
                stack.push(new Job(cur.L, equals[0] - 1));
            }
            // 有 > 区域
            if (equals[1] < cur.R) {
                stack.push(new Job(equals[1] + 1, cur.R));
            }
        }
    }

    // ----------------------------- 对数器 -----------------------------

    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        System.arraycopy(arr, 0, res, 0, arr.length);
        return res;
    }

    public static boolean isEqual(int[] arr1, int[] arr2) {
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1 == null ^ arr2 == null) {
            return false;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    // ---------------------------------------------------------------------

    public static void main(String[] args) {
        int[] arr = {7, 1, 3, 5, 4, 5, 1, 4, 2, 4, 2, 4};

        // <区, =区, >区
        splitNum2(arr);
        for (int j : arr) {
            System.out.print(j + " ");
        }

        System.out.println("===========================");

        int testTime = 500_000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        System.out.println("test begin");
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            int[] arr3 = copyArray(arr1);
            quickSort1(arr1);
            quickSort2(arr2);
            if (!isEqual(arr1, arr2) || !isEqual(arr1, arr3)) {
                System.out.println("Oops!");
                succeed = false;
                break;
            }
        }
        System.out.println("test end");
        System.out.println(succeed ? "Nice!" : "Oops!");
    }

}

4. 数据结构

数据结构是存储、组织数据的方式
精心选择的数据结构，可以带来更高的运行、存储效率
数据结构是很多算法得以进行的载体

最基本的数据结构

数组（便于寻址，不便于增、删数据）
链表（便于增、删数据，不便于寻址）

1. 前缀和数组

求：sum(arry, index1, index2)

1. 二维数组

(3, 4, 2, 1, 6, 7, 8)

2. 一维数组

sum(arry, index1, index2) = sum(arry, 0, index2) - sum(arry, 0, index1)

/**
 * 一段数组arr和
 */
public class _01_PreSum {

	/**
	 * 1. 普通累加
	 */
	public static class RangeSum1 {
		private final int[] arr;

		public RangeSum1(int[] array) {
			arr = array;
		}

		public int rangeSum(int L, int R) {
			int sum = 0;
			for (int i = L; i <= R; i++) {
				sum += arr[i];
			}
			return sum;
		}
	}

	/**
	 * 2. 前缀和
	 */
	public static class RangeSum2 {
		// 构造前缀数组
		private final int[] preSum;

		public RangeSum2(int[] array) {
			int N = array.length;
			preSum = new int[N];
			preSum[0] = array[0];
			for (int i = 1; i < N; i++) {
				preSum[i] = preSum[i - 1] + array[i];
			}
		}

		public int rangeSum(int L, int R) {
			return L == 0 ? preSum[R] : preSum[R] - preSum[L - 1];
		}
	}

}

2. 随机函数

Math.random()
Math.random() * 8
(int) (Math.random() * K)
[0,x) 的概率 (x -> x^2)
从a~b随机等概率，到c~d随机等概率
[0, 1]不等概率 -> [0, 1]等概率

public class _02_RandToRand {

    private static final int testTimes = 10_000_000;

    /**
     * Math.random()
     */
    @Test
    public void test1() {
        // Math.random() -> double -> [0, 1)
        // 等概率随机返回一个，数学上是做不到的，计算机是有精度的
        int count = 0;
        for (int i = 0; i < testTimes; i++) {
            if (Math.random() < 0.75) {
                count++;
            }
        }
        System.out.println((double) count / (double) testTimes);
    }

    /**
     * Math.random() * 8
     */
    @Test
    public void test2() {
        // [0, 1) -> [0, 8)
        int count = 0;
        for (int i = 0; i < testTimes; i++) {
            if (Math.random() * 8 < 5) {
                count++;
            }
        }
        System.out.println((double) count / (double) testTimes);
        System.out.println((double) 5 / (double) 8);
    }

    /**
     * [0, K) -> [0, K-1]
     * (int) (Math.random() * K)
     */
    @Test
    public void test3() {
        int K = 9;
        int[] counts = new int[9];
        for (int i = 0; i < testTimes; i++) {
            int ans = (int) (Math.random() * K);
            counts[ans]++;
        }
        for (int i = 0; i < K; i++) {
            System.out.println(i + " 这个数，出现了 " + counts[i] + " 次");
        }
    }

    // ----------------------------------------------------------------------------

    /**
     * [0,x) 的概率 (x -> x^2)
     */
    @Test
    public void test4() {
        int count = 0;
        double x = 0.17;
        for (int i = 0; i < testTimes; i++) {
            if (xToXPower2() < x) {
                count++;
            }
        }
        System.out.println((double) count / (double) testTimes);
        System.out.println(Math.pow(x, 2));
    }

    /**
     * 返回[0,1)的一个小数
     * 任意的x，x属于[0,1)，[0,x)范围上的数出现概率由原来的x调整成x^2
     */
    public static double xToXPower2() {
        return Math.max(Math.random(), Math.random());
    }

    public static double xToXPower3() {
        return Math.max(Math.random(), Math.max(Math.random(), Math.random()));
    }

    // ----------------------------------------------------------------------------

    /**
     * 从a~b随机等概率，到c~d随机等概率
     */
    @Test
    public void test5() {
        int count = 0;
        for (int i = 0; i < testTimes; i++) {
            if (f2() == 0) {
                count++;
            }
        }
        System.out.println((double) count / (double) testTimes);

        int[] counts = new int[8];
        for (int i = 0; i < testTimes; i++) {
            // int num = f3();
            // int num = f4();
            int num = g();
            counts[num]++;
        }
        for (int i = 0; i < 8; i++) {
            System.out.println(i + "这个数，出现了 " + counts[i] + " 次");
        }
    }

    /**
     * lib里的，不能改！
     * 等概率[1, 5]
     */
    public static int f1() {
        return (int) (Math.random() * 5) + 1;
    }

    /**
     * 随机机制，只能用f1
     * 等概率[0, 1]
     */
    public static int f2() {
        int ans;
        do {
            ans = f1();
        } while (ans == 3);
        // 1,2 => 0
        // 4,5 => 1
        return ans < 3 ? 0 : 1;
    }

    /**
     * 得到000 ~ 111
     * 等概率[0, 7]
     */
    public static int f3() {
        return (f2() << 2) + (f2() << 1) + f2();
    }

    /**
     * 等概率[0, 6]
     */
    public static int f4() {
        int ans;
        do {
            ans = f3();
        } while (ans == 7);
        return ans;
    }

    /**
     * 等概率[1, 7]
     */
    public static int g() {
        return f4() + 1;
    }

    // ------------------------------------------------------------

    /**
     * [0, 1]不等概率 -> [0, 1]等概率
     */
    @Test
    public void test6() {
        int count = 0;
        for (int i = 0; i < testTimes; i++) {
            if (y() == 0) {
                count++;
            }
        }
        System.out.println((double) count / (double) testTimes);
    }

    /**
     * 你只能知道，x会以固定概率返回0和1，但是x的内容，你看不到！
     */
    public static int x () {
        return Math.random() < 0.84 ? 0 : 1;
    }

    /**
     * 等概率返回0和1
     */
    public static int y() {
        int ans;
        do {
            ans = x();
        } while (ans == x());
        // ans = 0 1
        // ans = 1 0
        return ans;
    }

    // ------------------------------------------------------------

    // 这个结构是唯一的随机机制
    // 只能初始化并使用，不可修改
    public static class RandomBox {
        private final int min;
        private final int max;

        // 初始化时请一定不要让mi==ma
        public RandomBox(int mi, int ma) {
            min = mi;
            max = ma;
        }

        // 13 ~ 17
        // 13 + [0,4]
        public int random() {
            return min + (int) (Math.random() * (max - min + 1));
        }

        public int min() {
            return min;
        }

        public int max() {
            return max;
        }
    }

    // 利用条件RandomBox，如何等概率返回0和1
    public static int rand01(RandomBox randomBox) {
        int min = randomBox.min();
        int max = randomBox.max();
        // min ~ max
        int size = max - min + 1;
        // size是不是奇数，odd奇数
        boolean odd = (size & 1) != 0;
        int mid = size / 2;
        int ans;
        do {
            ans = randomBox.random() - min;
        } while (odd && ans == mid);        // 奇数且等于中间数
        return ans < mid ? 0 : 1;
    }

    // 给你一个RandomBox，这是唯一能借助的随机机制
    // 等概率返回from~to范围上任何一个数
    // 要求from<=to
    public static int random(RandomBox randomBox, int from, int to) {
        if (from == to) {
            return from;
        }
        // (3 ~ 9) => (0 ~ 6)
        // 0 ~ range
        int range = to - from;
        int num = 1;
        // 求0~range需要几个2进制位
        while ((1 << num) - 1 < range) { // 全是1的二进制数，
            num++;
        }

        // 一共需要num位
        // 最终的累加和。首先：0位上1或0，1位上1或0，2位1或0...
        int ans;
        do {
            ans = 0;
            for (int i = 0; i < num; i++) {
                ans |= (rand01(randomBox) << i);
            }
        } while (ans > range); // 超出部分舍弃
        return ans + from;
    }

}

[0, 1]不等概率 -> [0, 1]等概率

public class _04_EqualProbabilityRandom {

    // 内部内容不可见
    public static int f() {
        return Math.random() < 0.8 ? 0 : 1;
    }

    // 等概率返回 0,1
    public static int g() {
        int first;
        do {
            first = f(); // 0,1
        } while (first == f());
        return first;
    }

    // 这个结构是唯一的随机机制
    // 只能初始化并使用，不可修改
    public static class RandomBox {
        private final double p;

        // 初始化时请一定满足：(0 < zeroP < 1)
        public RandomBox(double zeroP) {
            p = zeroP;
        }

        public int random() {
            return Math.random() < p ? 0 : 1;
        }
    }

    // 底层依赖一个以p概率返回0，以1-p概率返回1的随机函数rand01p
    // 如何加工出等概率返回0和1的函数
    public static int rand01(RandomBox randomBox) {
        int num;
        do {
            num = randomBox.random();
        } while (num == randomBox.random());
        return num;
    }

    public static void main(String[] args) {
        // (0, 1)
        int[] count = new int[2];
        for (int i = 0; i < 1_000_000; i++) {
            int ans = g();
            count[ans]++;
        }
        System.out.println(count[0] + ", " + count[1]);

        double zeroP = 0.88;
        RandomBox randomBox = new RandomBox(zeroP);

        System.out.println("------------------------------------------------");

        int testTime = 10_000_000;
        int num = 0;
        for (int i = 0; i < testTime; i++) {
            if (rand01(randomBox) == 0) {
                num++;
            }
        }
        System.out.println((double) num / (double) testTime);
    }

}

3. 对数器

选择、冒泡、插入排序的对数器验证

public class _03_Comp {

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // 1. 选择排序
    public static void selectionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);
        }
    }

    // 2. 插入排序
    public static void insertionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 1; i < arr.length; i++) {
            // 0 ~ i 有序
            for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                swap(arr, j, j + 1);
            }
        }
    }

    // ---------------------------------------------------------------

    @Test
    public void test() {
        int maxLen = 5;
        int maxValue = 1_000;
        int testTime = 10_000;
        for (int i = 0; i < testTime; i++) {
            int[] arr = lenRandomValueRandomArray(maxLen, maxValue);
            // 备份
            int[] tmp = copyArray(arr);
            selectionSort(arr);
            if (!isSorted(arr)) {
                // 打印备份，找到错误例子
                for (int k : tmp) {
                    System.out.print(k + " ");
                }
                System.out.println();
                System.out.println("选择排序错了！");
                break;
            }
        }
    }

    /**
     * 随机数组（长度、值 随机）
     * 返回一个数组arr，arr长度[0, maxLen-1]，arr中的每个值[0, maxValue-1]
     */
    public static int[] lenRandomValueRandomArray(int maxLen, int maxValue) {
        int len = (int) (Math.random() * maxLen);
        int[] ans = new int[len];
        for (int i = 0; i < len; i++) {
            ans[i] = (int) (Math.random() * maxValue);
        }
        return ans;
    }

    /**
     * copyArray
     */
    public static int[] copyArray(int[] arr) {
        int[] ans = new int[arr.length];
        System.arraycopy(arr, 0, ans, 0, arr.length);
        return ans;
    }

    /**
     * 排序验证，后一个大于前一个
     */
    public static boolean isSorted(int[] arr) {
        if (arr.length < 2) {
            return true;
        }
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max > arr[i]) {
                return false;
            }
            max = Math.max(max, arr[i]);
        }
        return true;
    }

}

5. 二分法

1. 找num

arr有序，找num

public class _01_BSExist {

    /**
     * 二分法在数组中，查找元素
     */
    public static boolean find(int[] arr, int num) {
        if (arr == null || arr.length == 0) {
            return false;
        }
        int L = 0;
        int R = arr.length - 1;
        while (L <= R) {
            int mid = (L + R) / 2;
            if (arr[mid] == num) {
                return true;
            } else if (arr[mid] < num) {
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        return false;
    }

    /**
     * 对数器
     */
    public static boolean test(int[] sortedArr, int num) {
        for (int cur : sortedArr) {
            if (cur == num) {
                return true;
            }
        }
        return false;
    }

    /**
     * 生成随机数组
     */
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    /**
     * 有序数组中找到num
     */
    public static void main(String[] args) {
        int testTime = 500_000;
        int maxSize = 10;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr = generateRandomArray(maxSize, maxValue);
            Arrays.sort(arr);
            int value = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
            if (test(arr, value) != find(arr, value)) {
                System.out.println("出错了！");
                succeed = false;
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    }

}

2. `>=num`最左index

public class _02_BSNearLeft {

    /**
     * arr有序，>=num 最左index
     */
    public static int mostLeftNoLessNumIndex(int[] arr, int num) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int L = 0;
        int R = arr.length - 1;
        int ans = -1;
        while (L <= R) {
            int mid = (L + R) / 2;
            if (arr[mid] >= num) {
                ans = mid;
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return ans;
    }

    /**
     * 对数器
     */
    public static int test(int[] arr, int value) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] >= value) {
                return i;
            }
        }
        return -1;
    }

    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int j : arr) {
            System.out.print(j + " ");
        }
        System.out.println();
    }

    /**
     * 有序数组中，找到>=num最左的位置
     */
    public static void main(String[] args) {
        int testTime = 500_000;
        int maxSize = 10;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr = generateRandomArray(maxSize, maxValue);
            Arrays.sort(arr);
            int value = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
            if (test(arr, value) != mostLeftNoLessNumIndex(arr, value)) {
                printArray(arr);
                System.out.println(value);
                System.out.println(test(arr, value));
                System.out.println(mostLeftNoLessNumIndex(arr, value));
                succeed = false;
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    }

}

3. 局部最小

定义：
1. [0] < [1]
2. [N-2] < [N-1]
3. 左 < [i] < 右
返回一个局部最小

public class _04_BSAwesome {

    /**
     * arr 整体无序
     * arr 相邻的数不相等！
     */
    public static int oneMinIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int N = arr.length;
        if (N == 1) {
            return 0;
        }
        if (arr[0] < arr[1]) {
            return 0;
        }
        if (arr[N - 1] < arr[N - 2]) {
            return N - 1;
        }
        int L = 0;
        int R = N - 1;
        // L...R 肯定有局部最小
        // 1. (R - 1) 确保三个节点，才进入while体
        while (L < R - 1) {
            int mid = (L + R) / 2;
            if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
                return mid;
            } else {
                if (arr[mid] > arr[mid - 1]) {
                    R = mid - 1;
                } else {
                    L = mid + 1;
                }
            }
        }
        // 2. 只有两个数
        return arr[L] < arr[R] ? L : R;
    }

    /**
     * 生成随机数组，`相邻数不相等`
     */
    public static int[] randomArray(int maxLen, int maxValue) {
        int len = (int) (Math.random() * maxLen);
        int[] arr = new int[len];
        if (len > 0) {
            arr[0] = (int) (Math.random() * maxValue);
            for (int i = 1; i < len; i++) {
                do {
                    arr[i] = (int) (Math.random() * maxValue);
                } while (arr[i] == arr[i - 1]);
            }
        }
        return arr;
    }

    /**
     * 对数器
     */
    public static boolean check(int[] arr, int minIndex) {
        if (arr.length == 0) {
            return minIndex == -1;
        }
        int left = minIndex - 1;
        int right = minIndex + 1;
        // boolean leftBigger = left >= 0 ? arr[left] > arr[minIndex] : true;
        boolean leftBigger = left < 0 || arr[left] > arr[minIndex];
        // boolean rightBigger = right < arr.length ? arr[right] > arr[minIndex] : true;
        boolean rightBigger = right >= arr.length || arr[right] > arr[minIndex];
        return leftBigger && rightBigger;
    }

    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int maxLen = 100;
        int maxValue = 200;
        int testTime = 1_000_000;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int[] arr = randomArray(maxLen, maxValue);
            int ans = oneMinIndex(arr);
            if (!check(arr, ans)) {
                printArray(arr);
                System.out.println(ans);
                break;
            }
        }
        System.out.println("测试结束");
    }

}

6. 时间复杂度

1. 常数操作

+, -, *, /, arr[x] 和数据量无关的去处，都是常数操作
复杂度： $O(1)$

2. 引入

冒泡排序、选择排序 => $O(N^2)$
不关心低阶项，也不关心系数

S_n = na_1 + \frac{n(n-1)}{2}d,n \in N ^ *

二分查找 => $O(log_2^N)$
最差情况下的复杂度

3. 常见复杂度

$O(1) < O(logN) < O(n) < O(nlogN) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)$

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面
不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面
内排序：所有排序操作都在内存中完成
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行
时间复杂度：一个算法执行所耗费的时间
空间复杂度：运行完一个程序所需内存的大小

4. 动态数组

ArrayList 动态扩容 1 + 2 + 4 + 8 + ... + N 等比数列 => $O(N)$ ，均摊下来 $O(1)$

5. 哈希表

增删查改均为： $O(1)$ 👍。比较大的常数时间（相比，数组寻址、+, -, *, /）

public static class Node {
    public int value;

    public Node(int v) {
        value = v;
    }
}

/**
 * (K V)表
 * 1. 哈希表（hashMap)
 * 2. 有序表（treeMap)
 */
@Test
public void test1() {
    // 1. 增删查改：O(1)，只是每次操作都慢一些（相对于数组寻址，`+, -, *, /`）
    HashMap<String, String> map = new HashMap<>();

    map.put("ooxx", "我是ooxx");
    System.out.println(map.containsKey("ooxx"));
    System.out.println(map.get("ooxx"));

    map.put("ooxx", "他是ooxx");
    System.out.println(map.get("ooxx"));

    map.remove("ooxx");
    System.out.println(map.get("ooxx"));

    // 2. 值传递 hashMap占用内存为 key + value
    HashMap<Integer, String> map2 = new HashMap<>();
    map2.put(1234567, "我是1234567");

    Integer a = 1234567;
    Integer b = 1234567;
    // 内存地址
    System.out.println(a == b);
    // hash表里`Integer, Double, Float, String`按值传递
    System.out.println(map2.containsKey(a));
    System.out.println(map2.containsKey(b));

    // 3. 引用传递 hashMap占用内存为(key引用 + value引用)，16字节
    // 非原生类型，按引用传递，对象内存地址作为key。重写hashCode()另算
    Node node1 = new Node(1);
    Node node2 = new Node(1);
    HashMap<Node, String> map3 = new HashMap<>();
    map3.put(node1, "我进来了！");
    System.out.println(map3.containsKey(node1));
    System.out.println(map3.containsKey(node2));
}

6. 有序表

增删查改均为： $O(logN)$

@Test
public void test2() {
    // 1. 增删查改：O(logN)
    TreeMap<Integer, String> treeMap = new TreeMap<>();
    treeMap.put(3, "我是3");
    treeMap.put(0, "我是3");
    treeMap.put(7, "我是3");
    treeMap.put(2, "我是3");
    treeMap.put(5, "我是3");
    treeMap.put(9, "我是3");

    System.out.println(treeMap.containsKey(7));
    System.out.println(treeMap.containsKey(6));
    System.out.println(treeMap.get(3));

    treeMap.put(3, "他是3");
    System.out.println(treeMap.get(3));

    treeMap.remove(3);
    System.out.println(treeMap.get(3));

    System.out.println(treeMap.firstKey());
    System.out.println(treeMap.lastKey());
    // <=5 离5最近的key告诉我
    System.out.println(treeMap.floorKey(5));
    // <=6 离6最近的key告诉我
    System.out.println(treeMap.floorKey(6));
    // >=5 离5最近的key告诉我
    System.out.println(treeMap.ceilingKey(5));
    // >=6 离6最近的key告诉我
    System.out.println(treeMap.ceilingKey(6));


    // cannot be cast to java.lang.Comparable
    // 2. key 必须是可比较的。构造方法必须自定义
    Node node3 = new Node(3);
    Node node4 = new Node(4);
    TreeMap<Node, String> treeMap1 = new TreeMap<>();
    treeMap1.put(node3, "我是node3");
    treeMap1.put(node4, "我是node4");
}

01-位运算-排序

1. 反码, 补码

2. 位运算

1. 两数比较

3. 算法

1. 阶乘和

2. 排序

1. 选择排序

2. 冒泡排序

3. 插入排序

4. 归并排序

5. 快速排序

4. 数据结构

1. 前缀和数组

1. 二维数组

2. 一维数组

2. 随机函数

3. 对数器

5. 二分法

1. 找num

2. `>=num`最左index

3. 局部最小

6. 时间复杂度

1. 常数操作

2. 引入

3. 常见复杂度

4. 动态数组

5. 哈希表

6. 有序表