B站链接

细节都写在注释里了

最近想要用伪代码实现之前写过的代码

排序

交换数组中的两个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//常规方法
public static void swap1(int[]arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
}
//用位运算,执行速度更快,少申请一个变量
//本质：得到两数的二进制数中不同的位数，各自取反
public static void swap2(int[] arr,int i,int j){
        if(arr[i] == arr[j]){//如果arr[i]和arr[j]指向同一块内存会出错,所以干脆不交换
            return;
        }
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[j] ^ arr[i];
        arr[i] = arr[i] ^ arr[j];
}

生成随机数组

1
2
3
4
5
6
7
8
9
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++) {
            //一个随机正数减去另一个随机正数,生成一个[-maxValue,maxValue]的随机数
            arr[i] = (int)((maxValue+1)*Math.random()) 
                - (int)((maxValue+1)*Math.random());
        }
        return arr;
}

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 每一轮会使较大的值浮上去
 * 时间复杂度:
 * 每次比较的次数-1,等差数列,O(N^2)
 * 有稳定性
 */
//        for(每一轮选出一个最大值放后面){
//            for(从0位置开始,每轮比较的次数减少1){
//                当前数比后面的数大,就交换
//            }
//        }
public static void bubbleSort(int[] arr){
    if(arr == null || arr.length <2){
        return;
    }
    for(int i = 1; i < arr.length; i++){
        for(int j = 0; j < arr.length - i; j++){
            if (arr[j + 1] < arr[j]) {
                swap(arr,j + 1,j);
            }
        }
    }
}

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 选出最小值排在前面
 * 时间复杂度:
 * 每次比较的次数-1,等差数列,O(N^2)
 * 没有稳定性
 */
//        for(每一轮选一个最小值放前面){
//            int minIndex记录最小值的下标
//            for(遍历剩下的数找最小值的下标){
//                if(当前数小于minIndex对应的数){
//                    把当前数的下标记为minIndex
//                }
//            }
//            把minIndex对应的数换到最前面
//        }
public static void selectSort(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[minIndex] > arr[j]){
                minIndex = j;
            }
        }
        swap(arr,minIndex,i);
    }
}

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 每次拿出一个数插入前面已经排好序的数字中
 * 时间复杂度:
 * 等差数列,O(N^2)
 * 有稳定性
 */
//        for(每次拿出一个数插入前面已经排好序的数字中){
//            for(如果这个数比前面的数小,就一直往前找){
//                找到合适位置后插入
//            }
//        }
public static void insertSort(int[] arr){
    if(arr == null || arr.length <2){
        return;
    }
    for(int i = 1;i < arr.length;i++){
        for(int j = i; j > 0 && arr[j] < arr[j-1];j--){
            swap(arr,j,j - 1);
        }
    }
}

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//给定一个L~M有序,M~R有序的数组,把L~R范围变有序
//        int[] help 用来存放排好序的数;
//        int p1 左半部分的指针;
//        int p2 右半部分的指针;
//        while(两个指针都没越界){
//            p1指向的数和p2指向的数作比较,较小的放入help中;
//            放入数字的时候,对应指针向右移动一位;
//            直到有一个指针越界
//        }
//        下面这两个while循环只会中一个
//        while(p1还没越界){
//            剩下的肯定都是有序且较大的数;
//            直接放到help数组末尾
//        }
//        while(p2还没越界){
//            剩下的肯定都是有序且较大的数;
//            直接放到help数组末尾
//        }
//        把排好序的数复制回原数组
public static void merge(int[] arr,int L,int M,int R){
    int[] help = new int[R - L + 1];
    int p1 = L;
    int p2 = M + 1;
    int i = 0;
    while(p1 <= M && p2 <= R){
        help[i++] = arr[p1] <= arr[p2]? arr[p1++]:arr[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];
    }
}

递归实现

1
2
3
4
5
6
7
8
9
10
//让arr上L~R变有序
public void mergesort(int[] arr,int L,int R){
    if(L == R){//递归回溯条件
        return;
    }
    int mid = L + ((R - L) >> 1);
    mergesort(arr,L,mid);//让L~M有序
    mergesort(arr,mid +1,R);//让M~R有序
    merge(arr,L,mid,R);//调用上面的merge,让整体变有序
}

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//        mergeSize 每次merge的大小是mergeSize的两倍;
//        每次mergeSize都会翻倍
//        while(mergeSize < 数组长度){
//            设置一个从0开始的左指针
//            while(左指针没越界){
//                设置中线:左指针+mergeSize 为左半部分;
//                if(中线越界了){
//                    break;
//                }
//                设置一个右指针:(中线 + mergesize)如果越界取最右边界;
//                merge(arr, 左指针, 中线, 右指针);
//                左指针设为右指针+1;
//                循环直到中线或左指针越界;
//            }
//            if(mergeSize > 数组长度的一半){
//                break;防止翻倍后溢出
//            }
//            mergeSize翻倍;
//        }
public static void mergesort02(int[] arr){
    if(arr == null || arr.length < 2){
        return;
    }
    int mergeSize = 1;
    int N = arr.length;
    while(mergeSize < N){
        int L = 0;
        while(L < N){
            int M = L + mergeSize;
            if(M >= N){
                break;
            }
            int R =Math.min(M + mergeSize,N - 1);
            merge(arr,L,M,R);
            L = R + 1;
        }
        if(mergeSize > (N >> 1)){
            break;
        }
        mergeSize <<= 1;
    }
}

快速排序

Partition

给一个数，把数组中小于等于这个数的数放左边，其他放右边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public static int partition(int[] arr,int L,int R){
    if(L > R){
        return -1;
    }
    if(L == R){
        return L;
    }
    int less = L - 1;
    int more = R;
    int index = L;
    while(L < R){
        if(arr[index] == arr[R]){
            index++;
        }else if(arr[index] < arr[R]){
            swap(arr,index++,++less);
        }else{
            swap(arr,index,--more);
        }
    }
    swap(arr,more,R);
    return more;
}
public static void swap(int[] arr,int i,int j){
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

荷兰国旗问题

给一个数，把数组中小于这个数的数放左边，等于放中间，大于放右边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public static int partition(int[] arr,int L,int R){
    if(L > R){
        return -1;
    }
    if(L == R){
        return L;
    }
    int less = L - 1;
    int more = R;
    int index = L;
    while(L < R){
        if(arr[index] == arr[R]){
            index++;
        }else if(arr[index] < arr[R]){
            swap(arr,index++,++less);
        }else{
            swap(arr,index,--more);
        }
    }
    swap(arr,more,R);
    return more;
}
public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

快排1.0

用partition

1
2
3
4
5
6
7
8
public static void quicksort01(int[] arr,int L,int R){
    if(L >= R){
        return;
    }
    int M = partition(arr,L,R);
    quicksort01(arr,L,M);
    quicksort01(arr,M + 1,R);
}

快排2.0

用荷兰国旗

1
2
3
4
5
6
7
8
public static void quicksort02(int[] arr, int L, int R) {
    if (L >= R) {
        return;
    }
    int[] equalArea = netherlandsFlag(arr, L, R);
    quicksort02(arr, L, equalArea[0] - 1);
    quicksort02(arr, equalArea[1] + 1, R);
}

快排3.0（随机快排）

在2.0的基础上加随机，达到s时间复杂度O（N*logN）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void quicksort03(int[] arr,int L,int R){
    if (L <= R){
        return;
    }
    swap(arr,L + (int) (Math.random() * (R - L + 1)),R);
    int[] equalArea = NetherlandsFlag.netherlandsFlag(arr,L,R);
    quicksort03(arr,L,equalArea[0] - 1);
    quicksort03(arr,equalArea[1] + 1,R);
}
public static void swap(int[]arr,int i,int j){
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

结论：每种情况出现是等概率时，所有情况的时间复杂度的期望是O（N*logN）

堆排序

见二叉树部分的堆的内容

跳转

几乎有序的数组

桶排序

不基于比较的排序

应用范围很有限，如果数据有变动，算法很可能要大规模重写

计数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 *  O(logN)
 */
public static void countSort(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        int max = Integer.MIN_VALUE;
    	//找出最大值
        for(int i = 0; i < arr.length; i++){
            max = Math.max(max,arr[i]);
        }
    	//准备一个max + 1 个桶
        int[] bucket = new int[max + 1];
    	//计数
        for(int i = 0; i < arr.length; i++){
            bucket[arr[i]]++;
        }
        int i = 0;
    	//倒出
        for(int j = 0; j < bucket.length; j++){
            while(bucket[j]-- > 0){
                arr[i++] = j;
            }
        }
    }

基数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/**
 * O(N*lg(max)) N乘以,以十为底数组中最大值的对数 (N乘以最大值的位数)
 */
public class RadixSort {
    //只能处理非负值
    public static void radixSort(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        radixSort(arr,0,arr.length - 1,maxBits(arr));
    }

    /**
     * @param arr 要排序的数组
     * @return 最大值的位数
     */
    public static int maxBits(int[]arr){
        int max = Integer.MIN_VALUE;
        for(int i = 0;i < arr.length; i++){
            max = Math.max(max,arr[i]);
        }
        int res = 0;
        while(max != 0){
            res++;
            max /= 10;
        }
        return res;
    }

    public static void radixSort(int[] arr, int L, int R, int digit){
        final int radix = 10;//十进制
        int i = 0, j = 0;
        int[] help = new int[R - L +1];//等长数组
        for(int d = 1; d <= digit; d++) {//从个位开始,每一位入桶
            int[] count = new int[radix];
            //count
            for(i = L;i <= R; i++){
                j = getDigit(arr[i], d);
                count[j]++;
            }
            //count'
            for(i = 1; i < radix; i++){
                count[i] += count[i - 1];
            }
            //help
            for(i = R; i >= L; i--){
                j = getDigit(arr[i], d);
                help[count[j] - 1] = arr[i];
                count[j]--;
            }
            //倒回去
            for(i = L,j =0; i <= R; i++,j++){
                arr[i] = help[j];
            }
        }
    }

    /**
     * @param num 数字
     * @param digit 要取哪一位
     * @return num的第digit位
     */
    public static int getDigit(int num, int digit){
        int bits = 0;
        int cloneOfNum = num;
        while(cloneOfNum != 0){
            bits++;
            cloneOfNum /= 10;
        }
        if(digit > bits || digit <= 0){
            return 0;
        }
        return (num / (int)Math.pow(10,digit - 1)) % 10;
    }
}

总结

基于比较 时间复杂度 空间复杂度 稳定性
选择排序 O(N^2) O(1) 无
冒泡排序 O(N^2) O(1) 有
插入排序 O(N^2) O(1) 有
归并排序 O(N*logN) O(N) 有
随即快排 O(N*logN) O(logN) 无
堆排序 O(N*logN) O(1) 无
不基于比较
计数排序 O(N) O(M) 有
基数排序 O(N) O(N) 有

  • 比时间，选快排

  • 比空间，选堆排

  • 比稳定性，选归并

二分法

有序数组中查找某个数是否存在

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
    /**
     * 时间复杂度:
     * 每次查找的范围缩小一半,所以最多查找logN次
     * O(logN)
     */
public static boolean dichotomySearch(int[] arr,int target){
    if(arr == null || arr.length ==0){
        return false;
    }
    int L = 0;
    int R = arr.length-1;
    int mid = 0;
    while(L < R){
        mid = L + ((R - L) >> 1);
        if(arr[mid] == target){
            return true;
        }
        else if(arr[mid] > target){
            R = mid - 1;
        }
        else {
            L = mid + 1;
        }

    }
    return arr[L] == target;
}

有序数组中,找>=某个数最左侧的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int firstLeft(int[]arr,int target){
    int L = 0;
    int R = arr.length -1;
    int mid = 0;
    int res = -1;
    while(L <= R){
        mid = L + ((R - L) >> 1);
        if(arr[mid] >= target){
            res = mid;
            R = mid -1;
        }
        else{
            L = mid + 1;
        }
    }
    return res;
}

局部最小值

无序数组中，任何相邻的两个数都不相等，找局部最小值，局部最小值定义为既小于左边数，也小于右边数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public static int localMin(int[] arr){
    if(arr == null || arr.length == 0){
        return -1;
    }
    int L = 0;
    int R = arr.length - 1;
    //先看开头和末尾是不是局部最小
    if(arr.length == 1 || arr[0] < arr[1]){
        return 0;
    }
    if(arr[R] < arr[R - 1]){
        return R - 1;
    }
    //如果开头和末尾没有局部最小,则中间必定存在局部最小
    //按这种思路二分,总会找到
    while(L < R){
        int mid = L + ((R - L) >> 1);
        if(arr[mid] > arr[mid + 1]){
            L = mid + 1;
        }else if(arr[mid] > arr[mid -1]){
            R = mid - 1;
        }else{
            return mid;
        }
     }
    return -1;
    //这里return什么都可以,因为不可能执行到这一步，上面那个while必找到局部最小
    //任何相邻不相等的数组必存在局部最小
}

位运算

  1. 0 ^ N == N N ^ N == 0
  2. 异或运算满足交换律和结合律
  3. 用无进位相加来理解异或运算

交换数组中的两个数

1
2
3
4
5
6
7
8
public static void swap2(int[] arr,int i,int j){
        if(arr[i] == arr[j]){//如果arr[i]和arr[j]指向同一块内存会出错,所以干脆不交换
            return;
        }
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[j] ^ arr[i];
        arr[i] = arr[i] ^ arr[j];
}

数组中只有一种数出现了奇数次,打印这种数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void onlyOne(int[] arr){
    if(arr == null){
        return;
    }
    if(arr.length < 2){
        System.out.println(arr[0]);
        return;
    }
    int ans = arr[0];
    for(int i = 1;i < arr.length;i++){
        ans ^= arr[i];
    }
    System.out.println(ans);
}

提取最右侧的1

举例：把二进制数0111100变成0000100

取反加1再相与

N&((~N)+1)

1
2
3
public static int farRightOne(int num){
    return num & ((~num)+1);
}

数组中有两种数出现了奇数次,打印这两种数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void twoOddTimes(int[] arr){
    int eor = arr[0];
    for(int i = 1;i < arr.length;i++){
        eor ^= arr[i];
    }
    //假设答案是a和b,全部相与,得到a^b的值
    //eor = a ^ b
    //eor != 0
    //eor必然有一个位置是1
    //a和b中必然有一个数某一位是1,但另一个数这一位不是1
    int farRightOne = eor & ((~eor)+1);//提取最右侧的1
    int eor1 = 0;
    //将数组分为某一位是1和0的两组
    for(int i = 0;i < arr.length;i++){
        if((arr[i] & farRightOne) != 0){//相与不为0说明这一位上是1
            eor1 ^= arr[i];
        }
    }
    System.out.println(eor1 + " " + (eor1 ^ eor));
}

数出一个数的二进制形式中有几个1

1
2
3
4
5
6
7
8
9
public static int howManyOnes(int num){
    int count = 0;
    while(num != 0){
        int farRightOne = num & ((~num)+1);
        num ^= farRightOne;//每次消去最右侧的1
        count ++;
    }
    return count;
}

用位运算优化N皇后

见暴力递归N皇后plus

不用比较运算符获得最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
     * 给定两个有符号32位整数a和b,返回较大的那个
     * 不能使用比较运算符
     */
    public static int getMax(int a, int b){
        //因为不同符号的两个数相减有可能溢出,而同符号的数相减不会溢出
        //所以同符号时候用相减来判断大小
        //不同符号的时候用符号来判断大小

        //判断a和b的符号
        int sa = ~(a >> 31);//非负为1,负为0
        int sb = ~(b >> 31);//非负为1,负为0
        //判断a和b是否同号
        int ifSame = ~(sa ^ sb);//同号为1,异号为0
        //如果同号
        //先判断a是否大于b
        int greater = ~((a - b) >> 31);//a > b为1, a < b为0
        //如果a>b返回a,如果a<b返回b
        int sameReturn = greater * a + (~ greater) * b;

        //如果异号,返回非负的那个
        int diffReturn = sa * a + sb * b;

        //如果同号,返回sameReturn,否则返回diffReturn
        return ifSame * sameReturn + (~ ifSame) * diffReturn;
    }

2的幂、4的幂

1
2
3
4
5
6
7
8
//判断一个32位正数是不是2的幂、4的幂
public static boolean powerOf2(int num){
        return (num & (num - 1)) == 0;
    }
public static boolean powerOf4(int num){
    //0x55555555 -> 01010101.....010101(32位)
    return (num & (num - 1)) == 0 && (num & 0x55555555) != 0;
}

加减乘除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
     * 给定两个有符号32位整数a和b
     * 不能使用算术运算符
     * 实现加减乘除
     * 不用考虑溢出
     */
    public static int plus(int a, int b){
        int sum = a;//假设b等于0,和就为a
        while(b != 0){//如果b不为0
            sum = a ^ b;//无进位相加
            b = (a & b) << 1;//进位信息
            a = sum;
        }
        //没有进位时
        return sum;
    }

    public static int minus(int a, int b){
        //取反加一变为相反数
        b = plus((~b),1);
        //减去一个数等于加上这个数的相反数
        return plus(a, b);
    }
    public static int multi(int a, int b){
        int res = 0;
        while(b != 0){
            if((b & 1) != 0){
                res = plus(res, a);
            }
            a <<= 1;
            b >>>= 1;
        }
        return res;
    }

链表

单向链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class Node {
    public int value;
    public Node next;

    public Node(int data){
        value = data;
    }
	//翻转
    public static Node reverseLinkedList(Node head){
        Node next = null;
        Node last = null;
        while(head != null){
            next = head.next;

            head.next = last;

            last = head;

            head = next;
        }
        return last;
    }
	//删除指定元素
    public static Node removeValue(Node head,int num){
        while(head != null){
            if(head.value != num){
                break;
            }
            head = head.next;
        }
        Node last = head;
        Node cur = head;
        while(cur != null){
            if(cur.value == num){
                last.next = cur.next;
            }else{
                last = cur;
            }
            cur = cur.next;
        }
        return head;
    }
}

双向链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public class DoubleNode <T>{
    public T value;
    public DoubleNode<T> next;
    public DoubleNode<T> last;
    public DoubleNode(T data){
        value = data;
    }
	//翻转
    public DoubleNode<T> reverseDoubleList(DoubleNode<T> head){
        DoubleNode<T> last = null;
        DoubleNode<T> next = null;
        while(head != null){
            head.next = next;

            head.next = last;
            head.last = next;

            last = head;

            head = next;
        }
        return last;
    }
	//删除指定元素
    public DoubleNode<T> removeValue(DoubleNode<T> head, T num){
        while(head != null){
            if(head.value != num){
                break;
            }
            head = head.next;
        }
        DoubleNode<T> last = head;
        DoubleNode<T> cur = head;
        DoubleNode<T> next = head.next;
        while(cur != null){
            if(cur.value == num){
                last.next = next;
                next.last = last;
            } else{
                last = cur;
            }
            next = cur.next;
            cur = cur.next;
        }
        return head;
    }

}

双向链表实现队列和栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public class MyNode <T>{
    public DoubleNode<T> H;
    public DoubleNode<T> T;

    public void pushFromHead(T data){
        DoubleNode<T> newNode = new DoubleNode<>(data);
        if(H == null){
            T = newNode;
        }else {
            H.last = newNode;
            newNode.next = H;
        }
        H = newNode;
    }

    public void pushFromTail(T data){
        DoubleNode<T> newNode = new DoubleNode<>(data);
        if(T == null){
            H = newNode;
        }else{
            T.next = newNode;
            newNode.last = T;
        }
        T = newNode;
    }

    public T popFromHead(){
        if(H == null){
            return null;
        }
        DoubleNode<T> popNode = H;
        if(H == T){
            H = null;
            T = null;
        }else {
            H = H.next;
            H.last = null;
            popNode.next = null;
        }
        return popNode.value;
    }
    public T popFromTail(){
        if(T == null){
            return null;
        }
        DoubleNode<T> popNode = T;
        if(H == T){
            H = null;
            T = null;
        }else {
            T = T.last;
            T.next = null;
            popNode.last = null;
        }
        return popNode.value;
    }
}

实现队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class ListQueue <T>{
    MyNode<T> node;
    public ListQueue(){
        node = new MyNode<T>();
    }

    public void push(T value){
        node.pushFromTail(value);
    }

    public void pop(){
        node.popFromHead();
    }
}

实现栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class ListStack<T> {
    MyNode<T> node;
    public ListStack(){
        node = new MyNode<T>();
    }

    public void push(T value){
        node.pushFromTail(value);
    }

    public void pop(){
        node.popFromTail();
    }
}

返回中点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import java.util.ArrayList;

public class GetMid {
    //笔试用Arraylist
    //时间复杂度:O(N)
    //空间复杂度:O(N)
    public static Node getMid01(Node head){
        if(head == null){
            return null;
        }
        ArrayList<Node> help = new ArrayList<>();
        while(head.next != null){
            help.add(head);
            head = head.next;
        }
        return help.get((help.size() - 1) / 2);//返回中点或上中点
    }
    //面试用双指针
    //时间复杂度O(N)而且比上面的Arraylist节省一半的时间
    //空间复杂度O(1)
    //双指针
    //中点和上中点
    public static Node getMid02(Node head){
        if(head == null){
            return null;
        }
        Node f = head;
        Node s = head;
        while(f.next != null && f.next.next != null){
            f = f.next.next;
            s = s.next;
        }
        return s;
    }

    //中点和下中点
    public static Node getMid03(Node head){
        if(head == null || head.next == null){
            return head;
        }
        Node f = head;
        Node s = head.next;
        while(f.next != null && f.next.next != null){
            f = f.next.next;
            s = s.next;
        }
        return s;
    }
}

是否为回文结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class IsPalindrome {
    public static boolean isPalindrome(Node head){
        if(head == null || head.next == null){
            return true;
        }
        Node help = GetMid.getMid02(head);
        Node l = help.next;
        Node r = null;
        //让后半部分的指针反向指
        while(l != null){
            r = l.next;
            l.next = help;
            help = l;
            l = r;
        }
        r = help;
        l = head;
        boolean res = true;
        //对比前半部分和后半部分
        while(r != null && l != null){
            if(r.value != l.value){
                res = false;
                break;//不直接return false是因为要把链表还原回去
            }
            r = r.next;
            l = l.next;
        }
        r = help.next;
        help.next = null;
	    //还原
        while(r != null){
            l = r.next;
            r.next = help;
            help = r;
            r = l;
        }
        return res;
    }
}

Partition

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public static Node listPartition(Node head, int value){
    Node lh = null;
    Node lt = null;
    Node eh = null;
    Node et = null;
    Node mh = null;
    Node mt = null;
    Node next = null;
    while(head != null){
        next = head.next;
        head.next = null;
        if(head.value < value){
            if(lh == null){
                lh = head;
            }else{
                lt.next = head;
            }
            lt = head;
        }else if(head.value == value){
            if(eh == null){
                eh = head;
            }else{
                et.next = head;
            }
            et = head;
        }else{
            if(mh == null){
                mh = head;
            }else{
                mt.next = head;
            }
            mt = head;
        }
        head = next;
    }
    if(lt != null){
        lt.next = eh;
        et = et == null ? lt : et;
    }
    if(et != null){
        et.next = mh;
    }
    return lh != null ? lh : eh != null ? eh : mh;
}

rand克隆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import java.util.HashMap;

public class Node {
    int value;
    Node next;
    Node rand;
    public Node(int v){
        value = v;
    }
}

public class Clone {
    //用hashmap
    public static Node clone01(Node head){
        HashMap<Node,Node> hashMap = new HashMap<>();
        Node cur = head;
        while(cur != null){
            hashMap.put(cur,new Node(cur.value));
            cur = cur.next;
        }
        cur = head;
        while(cur != null){
            hashMap.get(cur).next = hashMap.get(cur.next);
            hashMap.get(cur).rand = hashMap.get(cur.rand);
            cur = cur.next;
        }
        return hashMap.get(head);
    }
	//不用hashmap
    public static Node clone02(Node head){
        if(head == null){
            return null;
        }
        Node cur = head;
        while(cur != null){
            Node cloneNode = new Node(cur.value);
            cloneNode.next = cur.next;
            cur.next = cloneNode;
            cur = cloneNode.next;
        }
        cur = head;
        while(cur != null){
            cur.next.rand = cur.rand == null ? null : cur.rand.next;
            cur = cur.next.next;
        }
        Node res = head.next;
        cur = head;
        Node help;
        while(cur != null){
            help = cur.next;
            cur.next = cur.next.next == null ? null : cur.next.next;
            help.next = cur.next == null ? null : cur.next.next;
            cur = cur.next;
        }
        return res;
    }
}

入环节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @param head 头
 * @return 有环就返回入环节点,无环就返回null
 */
public static Node loopInNode(Node head){
    //节点数小于3返回null
    if(head == null || head.next == null || head.next.next == null){
        return null;
    }
    Node s = head.next;
    Node f = head.next.next;
    while(!s.equals(f)){
        //为null说明无环
        if(f.next == null || f.next.next == null){
            return null;
        }
        s = s.next;
        f = f.next.next;
    }
    //相遇后f回到head的位置
    f = head;
    //再次相遇时便是入环节点的位置
    while(!s.equals(f)){
        f = f.next;
        s = s.next;
    }
    return s;
}

证明：
快指针与慢指针均从X出发，在Z相遇。此时，慢指针行使距离为a+b，快指针为a+b+n(b+c）。

所以2*(a+b)=a+b+n*(b+c),推出

a=(n-1)b+nc=(n-1)(b+c)+c;

得到，将此时两指针分别放在起始位置和相遇位置，并以相同速度前进，当一个指针走完距离a时，另一个指针恰好走出 绕环n-1圈加上c的距离。

环形链表第一个入环节点

相交节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
public class IntersectionList {
    /**
     * 两个无环链表
     * @param n1 链表1
     * @param n2 链表2
     * @return 第一个相交节点 or null
     */
    public static Node noLoop(Node n1, Node n2){
        if(n1 == null || n2 == null){
            return null;
        }
        int count = 0;
        Node p1 = n1;
        Node p2 = n2;
        while(p1.next != null){
            count++;
            p1 = p1.next;
        }
        while(p2.next != null){
            count--;
            p2 = p2.next;
        }
        if(p1 != p2){
            return null;
        }
        p1 = count > 0 ? n1 : n2;
        p2 = p1 == n1 ? n2 : n1;
        count = Math.abs(count);
        while(count != 0){
            p1 = p1.next;
            count--;
        }
        while(p1 != p2){
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }

    /**
     * 两个有环链表
     * 假设入环节点是同一个
     * @param n1 链表1
     * @param n2 链表2
     * @return 第一个相交节点
     */
    public static Node haveLoop1(Node n1, Node n2){
        int count = 0;
        Node p1 = n1;
        Node p2 = n2;
        while(p1.next != LoopInNode.loopInNode(p1)){
            count++;
            p1 = p1.next;
        }
        while(p2.next != LoopInNode.loopInNode(p2)){
            count--;
            p2 = p2.next;
        }
        p1 = count > 0 ? n1 : n2;
        p2 = p1 == n1 ? n2 : n1;
        count = Math.abs(count);
        while(count != 0){
            p1 = p1.next;
            count--;
        }
        while(p1 != p2){
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }

    /**
     * 两个有环链表
     * 假设入环节点不同
     * @param n1 链表1
     * @param n2 链表2
     * @return 任意一个入环节点(即第一个相交节点) or null
     */
    public static Node haveLoop2(Node n1, Node n2){
        Node loop1 = LoopInNode.loopInNode(n1);
        Node loop2 = LoopInNode.loopInNode(n2);
        Node n = loop1.next;
        while(n != loop1){
            if(n == loop2){
                return loop1;
            }
            n = n.next;
        }
        return null;
    }

    /**
     * 两个有环链表
     * @param n1 链表1
     * @param n2 链表2
     * @return 第一个相交节点 or null
     */
    public static Node haveLoop(Node n1, Node n2){
        Node loop1 = LoopInNode.loopInNode(n1);
        Node loop2 = LoopInNode.loopInNode(n2);
        if(loop1 == loop2){
            return haveLoop1(n1,n2);
        }
        return haveLoop2(n1,n2);
    }

    /**
     * 判断两个链表是否相交
     * 如果相交,返回第一个相交节点
     * 否则返回null
     * @param n1 链表1
     * @param n2 链表2
     * @return 第一个相交节点 or null
     */
    public static Node intersection(Node n1, Node n2){
        Node loop1 = LoopInNode.loopInNode(n1);
        Node loop2 = LoopInNode.loopInNode(n2);
        if(loop1 == null && loop2 == null){//都无环
            return noLoop(n1,n2);
        }else if (loop1 != null && loop2 != null){//都有环
            return haveLoop(n1, n2);
        }else{//一个有环,一个无环
            return null;
        }
    }
}

LRU

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/**
 * 设计LRU缓存结构，该结构在构造时确定大小，假设大小位K，并有如下两个功能
 * set(key, value) : 将记录(key, value)插入该结构
 * get(key) :返回key对应的value值
 * 要求:
 * 1.set和get时间复杂度O(1)
 * 2.当某个key的set或get操作一旦发生，认为这个key记录成为了最常使用的
 * 3.当缓存的大小超过K时，移除最不经常使用的记录
 */

import java.util.HashMap;
public class LRU <K, V> {
    public static class Node<K, V> {
        private K key;
        private V val;
        private Node<K, V> last;
        private Node<K, V> next;
        public Node(K k,V v){
            val = v;
            key = k;
        }
    }
    private final HashMap<K, Node<K, V>> map;
    private Node<K, V> tail;
    private Node<K, V> head;
    private final int sizeLimit;
    private int size;
    public LRU(int l) {
        map = new HashMap<>();
        sizeLimit = l;
        size = 0;
        tail = null;
        head = null;
    }

    public void set(K k, V v){
        if(map.containsKey(k)){
            map.get(k).val = v;
            update(k);
            return;
        }
        Node<K, V> node = new Node<>(k, v);
        if(map.isEmpty()){
            head = node;
        }else {
            node.last = tail;
            tail.next = node;
        }
        tail = node;
        map.put(k,node);
        if(size == sizeLimit){
            map.remove(head.key);
            head = head.next;
            head.last = null;
        }else{
            size++;
        }
    }
    public V get(K k){
        if(!map.containsKey(k)){
            return null;
        }
        update(k);
        return map.get(k).val;
    }

    private void update(K k){
        if(!map.containsKey(k) || map.get(k) == tail){
            return;
        }
        Node<K, V> cur = map.get(k);
        if(cur == head){
            head = head.next;
        }else{
            cur.last.next = cur.next;
            cur.next.last = cur.last;
        }
        cur.next = null;
        cur.last = tail;
        tail.next = cur;
        tail = cur;
    }
}

数组和字符串

固定大小的数组实现队列和栈

实现队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class ArrayQueue {
    private Object[] arr;
    private int size;
    private int H;
    private int T;
    private final int limit =7;

    public ArrayQueue(){
        arr = new Object[7];
        size = 0;
        H = 0;
        T = 0;
    }

    public void push(Object value){
        if(size == limit){
            System.out.println("Queue is full");
            return;
        }
        if(++T >= limit){
            T = 0;
        }
        arr[T] = value;
        size++;
    }

    public Object pop(){
        if(size == 0){
            System.out.println("Queue is empty");
            return null;
        }
        Object popValue = arr[H];
        if(H != T){
            if(++H >=limit){
                H = 0;
            }
        }
        size--;
        return popValue;
    }
}

实现栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class ArrayStack {
    Object[] arr;
    int size;
    public ArrayStack(){
        arr = new Object[7];
        size = 0;
    }

    public void push(Object value){
        if(size == 7){
            System.out.println("Stack is full");
            return;
        }
        arr[size++] = value;
    }

    public Object pop(){
        if(size == 0){
            System.out.println("Stack is empty");
            return null;
        }
        return arr[--size];
    }
}

矩阵

之字形打印矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class Zigzag {
    /**
     * 举例:
     * 1  2  3  4
     * 5  6  7  8    -> 1 2 5 9 6 3 4 7 10 11 8 12
     * 9  10 11 12
     */
    public static void zigzag(int[][] arr){
        /**
         * 相当于若干次45度角从下往上或者从上往下打印斜线上的数
         * 用a,b两点标记斜线起始坐标和终止坐标一次打印
         */
        int a_row = 0;//a的行号(纵坐标)
        int a_column = 0;//a的列号(横坐标)
        int b_row = 0;//b的行号(纵坐标)
        int b_column = 0;//b的列号(横坐标)
        boolean formUp = false;//true表示从上往下.false表示从下往上
        while(a_row != arr.length){
            zigzagPrint(arr,a_row,a_column,b_row,b_column,formUp);
            //坐标变化的顺序很重要!
            //a点向右走到头再向下走
            a_row += a_column == arr[0].length - 1 ? 1 : 0;
            a_column += a_column == arr[0].length - 1 ? 0 : 1;
            //b点向下走到头再向右走
            b_column += b_row == arr.length - 1 ? 1 : 0;
            b_row += b_row == arr.length - 1 ? 0 : 1;
            //每次打印的方向都会改变
            formUp = !formUp;
        }
    }
    public static void zigzagPrint(int[][] arr, int a_row, int a_column, int b_row, int b_column, boolean f){
       if(f){
           while(a_row <= b_row){//从上往下
               System.out.print(arr[a_row++][a_column--] + " ");
           }
       }else{
           while(b_row >= a_row){//从下往上
               System.out.print(arr[b_row--][b_column++] + " ");
           }
       }
    }
}

螺旋打印矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class Spiral {
    public static void spiral (int[][] arr){
        //用对角线的两个点确认层数
        int startRow = 0;
        int startColumn = 0;
        int endRow = arr.length - 1;
        int endColumn = arr[0].length - 1;
        //由外向内一层一层打印
        while(startRow <= endRow && startColumn <= endColumn){
            print(arr,startRow++,startColumn++,endRow--,endColumn--);
        }
    }
    public static void print(int[][] arr,int startRow, int startColumn, int endRow, int endColumn){
        if(startRow == endRow){//只有一行
            while(startColumn <= endColumn){
                System.out.print(arr[startRow][startColumn++] + " ");
            }
        }else if(startColumn == endColumn){//只有一列
            while(startRow >= endRow){
                System.out.print(arr[startRow++][startColumn] + " ");
            }
        }else{
            int curRow = startRow;
            int curColumn = startColumn;
            while(curColumn < endColumn){//左上->右上
                System.out.print(arr[curRow][curColumn++] + " ");
            }
            while(curRow < endRow){//右上->右下
                System.out.print(arr[curRow++][curColumn] + " ");
            }
            while(curColumn > startColumn){//右下->左下
                System.out.print(arr[curRow][curColumn--] + " ");
            }
            while(curRow > startRow){//左下->左上
                System.out.print(arr[curRow--][curColumn] + " ");
            }
        }
    }
}

原地旋转正方形矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class rotate {
    /**
     * 1  2  3  4       13 9  5  1
     * 5  6  7  8    -> 14 10 6  2
     * 9  10 11 12      15 11 7  3
     * 13 14 15 16      16 12 8  4
     * 
     * 由外向内一层一层分组旋转
     * 第一层
     * 第一组 1换到4,4换到16,16换到13,13换到1
     * 第二组 2换到8,8换到15,15换到9,9换到2
     * ...
     * 第二层
     * 以此类推..
     */
    public static void rotate (int[][] arr){
        int start = 0;
        int end = arr.length - 1;
        //由外向内一层一层旋转
        while(start <= end){
            process(arr,start++,end--);
        }
    }
    public static void process(int[][] arr,int start, int end){
        int num = 0;
        int tmp = 0;
        while(start + num < end){
            tmp = arr[start][start + num];
            arr[start][start + num] = arr[end - num][start];
            arr[end - num][start] = arr[end][end - num];
            arr[end][end - num] = arr[start + num][end];
            arr[start + num][end] = tmp;
            num ++;
        }
    }
}

岛的数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class Island {
    /**
     * 一个矩阵中只有0和1两种值,
     * 每个位置都可以和自己的上下左右四个位置相连,
     * 如果有一片1连在一起,这个部分叫做一个岛,
     * 求一个矩阵中有多少个岛
     *
     * 进阶:
     * 如何设计一个并行算法解决这个问题
     */
    public static int countIsland(int[][] arr){
        if(arr == null || arr.length == 0){
            return 0;
        }
        int count = 0;
        int rows = arr.length;
        int columns = arr[0].length;
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < columns; j++){
                if(arr[i][j] == 1){
                    inflect(arr, i, j, rows, columns);
                    count++;
                }
            }
        }
        return count;
    }
    public static void inflect(int[][] arr,int i,int j, int r, int c){
        if(i < 0 || i >= r || j < 0 || j >= c || arr[i][j] != 1){
            return;
        }
        arr[i][j] = 2;
        inflect(arr, i + 1, j, r, c);
        inflect(arr, i, j + 1, r, c);
        inflect(arr, i - 1, j, r, c);
        inflect(arr, i, j - 1, r, c);
    }
    /**
     * 进阶
     * 用并查集
     * 把矩阵分成几份同时计算
     * 然后再合并
     * mapreduce
     */
}

是否为子串KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
public class KMP {
    //对应力扣第28题
    /**
     * 判断一个字符串是不是另一个字符串的子串
     * 是的话返回子串第一个字符的位置.不是返回-1
     */

    public static int KMP(String s1, String s2) {
        if (s1 == null || s2 == null || s2.length() < 1 || s1.length() < s2.length()) {
            return -1;
        }
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        int i1 = 0;//s1指针
        int i2 = 0;//s2指针
        int[] next = nextArr(str2);
        while (i1 < str1.length && i2 < str2.length) {
            if (str1[i1] == str2[i2]) {
                i1++;
                i2++;
            } else if (i2 == 0) {//不能往前跳 next[i2] == -1,已经跳到最开头了
                i1++;//s1换个开头继续配
            } else {//能往前跳
                i2 = next[i2];//因为最长前缀的下一个字符的坐标正好和最长前缀的长度相等
            }
        }
        //上面while循环出来后,i1和i2至少有一个越界了
        //如果i2越界.说明配出来了
        //如果i1越界,说明配不出来
        //如果i2越界,i2 == i2 == str2.length
        return i2 == str2.length ? i1 - str2.length : -1;
        //返回i1减去s2的长度或-1
    }

    /**
     * 记录每个位置的字符最大前缀是多少
     */
    public static int[] nextArr(char[] s) {
        if( s.length == 1){
            return new int[] {-1};
        }
        int[] next = new int[s.length];
        next[0] = -1;
        next[1] = 0;
        int i = 2;//遍历指针
        int cn = 0;//对照指针
        //cn既代表上一个字符最长前缀的长度
        //也代表上一个字符最长前缀的下一个字符的坐标
        while(i < next.length){
            //i - 1位置的字符等于i - 1最长前缀的下一个字符
            /**
             * 例子
             * a b c cn .... a b c (i - 1) i
             */
            /**
             * 另一个例子
             * a b b s t a b b e c a b b s t a b b (i - 1) i
             * 此时i - 1位置的最大前缀为8
             * 比对下标为8的元素'e'和i-1位置的元素
             * 如果相等,则i位置的最大前缀为9
             * 如果不相等
             *      比对3位置的元素's'和i-1位置的元素
             *      这里's'是'e'最大前缀的下一个元素
             *      如果相等,i位置的最大前缀为4
             *      如果不相等,则比对's'最大前缀的下一个元素
             *
             */
            if(s[i - 1] == s[cn]){
                next[i++] = ++cn;
            } else if(cn != 0){
                cn = next[cn];
            } else {//cn == 0
                next[i++] = 0;
            }
        }
        return next;
    }
}

最长回文子串Manacher

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class Manacher {
    /**
     * 最长回文子串的长度
     */
    public static int manacher(String s){
        int n = s.length() * 2 + 1;
        //回文半径数组
        int[] pArr = new int[n];
        char[] str = new char[n];
        for(int i = 0; i < n; i++){
            if(i % 2 == 0){
                str[i] = '?';//随便选一个字符
            } else {
                str[i] = s.charAt(i / 2);
            }
        }
        //最远右回文右边界再右的一个位置
        int R = -1;
        //最远回文的中心
        int C = -1;
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < n; i ++){
            pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
            while(i + pArr[i] < n && i - pArr[i] >= 0){
                if(str[i + pArr[i]] == str[i - pArr[i]]){
                    pArr[i]++;
                }else{
                    break;
                }
            }
            if(i + pArr[i] > R){
                R = i + pArr[i];
                C = i;
            }
            max = Math.max(max, pArr[i]);
        }
        return max - 1;
    }
}

滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.LinkedList;

public class SlidingWindow {
    //滑动窗口最大值
    public int[] maxSlidingWindow(int[] arr, int w) {
        if (arr == null || w < 1 || arr.length < w){
            return null;
        }
        LinkedList<Integer> qmax = new LinkedList<>();
        int[] res = new int[arr.length - w + 1];
        int index = 0;
        for(int i = 0; i < arr.length; i++){
            while(!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]){
                qmax.pollLast();
            }
            qmax.addLast(i);
            if(qmax.peekFirst() == i - w) {
                qmax.pollFirst();
            }
            if(i >= w - 1){
                res[index++] = arr[qmax.peekFirst()];
            }
        }
        return res;
    }
    
}

分割数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.HashMap;

public class CutArray {
    /**
     * 给定一个长度大于3的数组arr.
     * 以其中3个数变为分割线
     * 能不能把数组分成累加和相等的四个部分
     */
    public static boolean cut(int[] arr){
        if(arr == null || arr.length < 7){
            return false;
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        int sum = arr[0];
        for(int i = 1; i < arr.length; i++){
            map.put(sum,i);
            sum += arr[i];
        }
        int lsum = arr[0];
        for(int s1 = 1; s1 < arr.length - 5; s1++){
            int checkSum = lsum * 2 + arr[s1];
            if(map.containsKey(checkSum)) {
                int s2 = map.get(checkSum);
                checkSum += lsum + arr[s2];
                if (map.containsKey(checkSum)) {
                    int s3 = map.get(checkSum);
                    if(checkSum + arr[s3] + lsum == sum){
                        return true;
                    }
                }
            }
            lsum += arr[s1];
        }
        return false;
    }
}

凑数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class MakeUp {
    /**
     * 给定一个有序正数数组arr,数组中每个数能用一次
     * 给定一个目标range
     * 返回数组最少还缺几个数能够让它凑出1~range上的所有数
     */
    public static int makeUp(int[] arr, int range){
        int touch = 0;
        int ans = 0;
        for(int i = 0; i < arr.length; i++){
            while(arr[i] > touch + 1){
                touch += touch + 1;
                ans++;
                if(touch >= range) {
                    return ans;
                }
            }
            touch += arr[i];
            if(touch >= range){
                return ans;
            }
        }
        while(range >= touch + 1){
            touch += touch + 1;
            ans++;
        }
        return ans;
    }
}

排序最小子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class 最小子数组 {
    /**
     * 给定一个无序数组arr,如果只能对一个子数组进行排序
     * 但是想让数组整体变有序,求需要排序的最短子数组长度
     */
    public static int minSubArr(int[] arr){
         int last = arr[0];
         int r = 0;
         int l = arr.length - 1;
        for(int i = 1; i <= l; i++){
            if(arr[i] > last){
                last = arr[i];
            }else{
                r = i;
            }
        }
        last = arr[l];
        for(int i = l; i >= 0; i--){
            if(arr[i] < last){
                last = arr[i];
            }else{
                l = i;
            }
        }
        return r - l;
    }
}

缺失的第一个正数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//力扣41
class Solution {
    public int firstMissingPositive(int[] nums) {
        int l = 0;//0~l-1的位置是排好序的1~l这些数
        int r = nums.length;//大于等于r的位置是期望之外的那些数(垃圾区)
        //期望的数的区间[l + 1, r]
        //所以一开始期望[1,nums.length]
        while(l < r){
            if(nums[l] == l + 1){//当前数是我期望的数
                l++;
            }else if(nums[l] < l + 1 || nums[l] > r || nums[nums[l] - 1] == nums[l]){//不是我期望的数
                //不在[l + 1, r]的范围,或者是重复的数
                swap(nums, l, --r);//丢到垃圾区,期望区间变小
            }else{//当前数在我期望的区间内,但没有在它该在的位置
                swap(nums, l, nums[l] - 1);
            }
        }
        return r + 1;//期望区间的下一个数即是答案
    }
    public void swap(int[] arr, int i,int j){
        if(arr[i] == arr[j]){
            return;
        }
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[j] ^ arr[i];
        arr[i] = arr[i] ^ arr[j];
    }
}

栈和队列

可以返回最小元素的栈

实现一个特殊的栈，再基本功能的基础上，再实现返回栈中最小元素的功能

  1. pop、push、getMin操作的时间复杂度都是O（1）
  2. 设计的栈类型可以用现成的栈结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class MinStack {
    private Stack<Integer> dataStack;
    private Stack<Integer> minStack;
    int min;
    public MinStack(){
        dataStack = new Stack<>();
        minStack = new Stack<>();
    }
    public void push(int value){
        minStack.push(minStack.peek() > value? value:minStack.peek());
        dataStack.push(value);
    }
    public int getMin(){
        return minStack.peek();
    }
    public Object pop(){
        minStack.pop();
        return dataStack.pop();
    }
}

用栈实现队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class StackToQueue<T> {
    private Stack<T> pushStack;
    private Stack<T> popStack;
    public StackToQueue(){
        pushStack = new Stack<>();
        popStack = new Stack<>();
    }
    public void push(T value){
        pushStack.push(value);
    }
    public T pop(){
        if(popStack.isEmpty() && pushStack.isEmpty()){
            System.out.println("Queue is empty");
            return null;
        }else if(popStack.isEmpty()){
            while(!pushStack.isEmpty()){
                popStack.push(pushStack.pop());
            }
        }
        return popStack.pop();
    }
}

用队列实现栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class QueueToStack<T> {
    LinkedList<T> l1;
    LinkedList<T> l2;
    public QueueToStack(){
        l1 = new LinkedList<>();
        l2 = new LinkedList<>();
    }
    public void push(T value){
        if(l2.isEmpty()){
            l1.push(value);
        }else {
            l2.push(value);
        }
    }
    public T pop(){
        if(l1.isEmpty() && l2.isEmpty()){
            System.out.println("Stack is empty");
            return null;
        }
        if(l2.isEmpty()){
            for(int i = 0;i < l1.size()-1;i++){
                l2.push(l1.pop());
            }
            return l1.pop();
        }else {
            for(int i = 0;i < l2.size()-1;i++){
                l1.push(l2.pop());
            }
            return l2.pop();
        }
    }
}

递归与动态规划

Master公式

形如

T(N) = a * T(N/b) + O(N^d)(其中a、b、d都是常数)

的递归函数，可以直接通过Master公式来确定时间复杂度

如果log(b,a) < d，复杂度为O(N^d)

如果log(b,a) > d，复杂度为O(N^log(b,a))

如果log(b,a) = d，复杂度为O(N^d * logN)

用递归实现数组上下标L到R的最大值

1
2
3
4
5
6
7
8
9
public static int getMax(int[] arr,int L,int R){
    if(L == R){
        return arr[L];
    }
    int mid = L + ((R - L) >> 1);
    int leftMax = getMax(arr,L,mid);
    int rightMax = getMax(arr,mid + 1,R);
    return Math.max(leftMax,rightMax);
}

数组小和

在一个数组中，一个数左边比它小的数的总和，叫数的小和，数组中所有数的小和，叫数组小和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public int smallSum(int[] arr,int L,int R){
    if(L == R){
        return 0;
    }
    int M = L + ((R - L) >> 1);
    return smallSum(arr,L,M)
            +
            smallSum(arr,M + 1,R)
            +
            merge(arr,L,M,R);
}
public static int merge(int[] arr,int L,int M,int R){
    int[] help = new int[R - L + 1];
    int i = 0;
    int res = 0;
    int p1 = L;
    int p2 = M + 1;
    while(p1 <= M && p2 <= R){
        res = arr[p1] < arr[p2]? (R - p2 + 1) * arr[p1]:0;
        help[i++] = arr[p1] <= arr[p2]?arr[p1++]:arr[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];
    }
    return res;
}

暴力递归

汉诺塔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
public class ViolentRecursion {
    public static void hanoi1 (int n) {
        leftToRight(n);
    }
    public static void leftToRight(int n){
        if(n == 1){
            System.out.println("num1,left -> right");
            return;
        }
        leftToMid(n -1);
        System.out.println("num" + n + ",left -> right");
        midToRight(n - 1);
    }
    public static void leftToMid(int n) {
        if(n == 1) {
            System.out.println("num1,left -> mid");
        }
        leftToRight(n - 1);
        System.out.println("num" + n + ",left -> mid");
        rightToMid(n - 1);
    }
    public static void midToRight(int n){
        if(n == 1){
            System.out.println("num1,mid -> right");
            return;
        }
        midToLeft(n -1);
        System.out.println("num" + n + ",mid -> right");
        leftToRight(n - 1);
    }
    public static void midToLeft(int n){
        if(n == 1){
            System.out.println("num1,mid -> left");
            return;
        }
        midToRight(n -1);
        System.out.println("num" + n + ",mid -> left");
        rightToLeft(n - 1);
    }
    public static void rightToLeft(int n){
        if(n == 1){
            System.out.println("num1,right -> left");
            return;
        }
        rightToMid(n -1);
        System.out.println("num" + n + ",right -> left");
        midToLeft(n - 1);
    }
    public static void rightToMid(int n){
        if(n == 1){
            System.out.println("num1,right -> mid");
            return;
        }
        rightToLeft(n -1);
        System.out.println("num" + n + ",right -> mid");
        leftToMid(n - 1);
    }
    public static void hanoi2 (int n) {
        if(n > 0){
            func(n, "left","right","mid");
        }
    }
    public static void func(int n, String from, String to, String other){
        if(n == 1){
            System.out.println("num" + 1 + "," + from + " -> " + to);
        }else{
            func(n - 1,from,other,to);
            System.out.println("num" + n + "," + from + " -> " + to);
            func(n - 1,other,to,from);
        }
    }

    public static void main(String[] args) {
        int n = 3;
        hanoi1(n);
        System.out.println("================");
        hanoi2(n);
    }
}

逆序栈

给你一个栈

逆序这个栈

不能申请额外数据结构

只能用递归函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.Stack;

public class ReverseStackUsingRecursive {
    public static void reverse(Stack<Integer> stack) {
        if(stack.isEmpty()){
            return;
        }
        int i = f(stack);
        reverse(stack);
        stack.push(i);
    }
    public static int f(Stack<Integer> stack){
        int result = stack.pop();
        if(stack.isEmpty()){
            return result;
        }else{
            int last = f(stack);
            stack.push(result);
            return last;
        }
    }
}

N皇后和N皇后plus

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
public class N_Queens {
    public static int nQueens (int n){
        if(n < 1){
            return 0;
        }
        int[] record = new int[n];
        return process(0, record, n);
    }

    /**
     *  0~i-1行摆好的情况下,剩下的行有多少种摆法
     * @param i 当前的行数
     * @param record 记录已经放了的皇后的位置,下标代表行号,值代表列
     * @param n n皇后
     * @return 0~i-1行摆好的情况下,剩下的行有多少种摆法
     */
    public static int process(int i,int[] record,int n){
        if(i == n){ // i== n说明超出了范围,因为i应该在0~n-1才有意义
            return 1;//i超出范围说明所有的皇后都放了,返回一种有效摆法
        }
        int res =0;
        for (int j = 0; j < n; j++){//在i行从0列开摆
            if(isValid(record,i,j)){//能摆的话
                record[i] = j;//记录
                res += process(i + 1, record, n);//跳下一行
            }
        }
        return res;
    }

    /**
     * @param record 已经摆好行的记录
     * @param i 当前行
     * @param j 当前列
     * @return 能不能把皇后放在当前行j列,能返回true,不能返回false
     */
    public static boolean isValid(int[] record,int i,int j){
        for(int k = 0; k < i; k++){//判断当前位置和第k行是否冲突
            if(j == record[k] //共列
            ||Math.abs(record[k] - j) == Math.abs(i - k)//共斜线,看两个位置连线斜率是否为1
            ){
                return false;
            }
        }
        return true;
    }
    
    
    /**
     * 用位运算优化以后可以大幅提高效率
     */
    public static int nQueensPlus (int n){
        if(n < 1 || n > 32) {//超过32位溢出了
            return 0;
        }
        //固定范围,右边n位全是1,剩下都是0
        int limit = n == 32 ? -1 : (1 << n) - 1;//超过32位没法算,溢出了
        return process2(limit,0,0,0);
    }

    /**
     * @param limit 固定范围,右边n位全是1,剩下都是0
     * @param colLim 记录那些列已经摆了皇后,摆了的位置为1
     * @param leftDiaLim 左斜线限制,不能放皇后的位置为1
     * @param rightDiaLim 右斜线限制,不能放皇后的位置为1
     * @return 在这些限制的情况下,还剩多少种摆法
     */
    public static int process2(int limit,
                               int colLim,
                               int leftDiaLim,
                               int rightDiaLim){
        if(colLim == limit){//说明每一列都摆了皇后
            return 1;
        }
        /**
         * pos的解释:
         * colLim | leftDiaLim | rightDiaLim 所有限制的全集
         * 取反(~)为了消除超出范围的限制
         * 与limit相与(&)把能摆皇后的位置标记为1,其他位置都是0
         * 所以pos记录哪些地方能摆皇后
         */
        int pos = limit & ( ~(colLim | leftDiaLim | rightDiaLim));
        int mostRightOne = 0;//最右侧的1
        int res = 0;
        while(pos != 0) {
            //一个数与上自己取反加1的结果就是最右侧的1
            mostRightOne = pos & (~pos + 1);//表示当前判断哪个位置
            res += process2(limit,//limit始终不变
                    colLim | mostRightOne,//在各种限制中加上当前位置去判断下一行
                    (leftDiaLim | mostRightOne) << 1,//左移一位
                    (rightDiaLim | mostRightOne) >>> 1);//逻辑右移
            //当前位置判断完毕,去掉最右侧的1去判断下一个位置
            //pos = pos - mostRightOne;
            //也可以改成位运算的异或
            pos = pos ^ mostRightOne;
        }
        return res;
    }
}

斐波那契数列

1
2
3
4
5
6
public static int f(int n) {
    if ( n <= 2){
        return 1;
    }
    return f(n - 1) + f ( n - 2 );
}

暴力递归到动态规划的套路

所有由n个可变参数写成的暴力递归都可以改成动态规划

Robot

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
public class Robot {
    /**
     * 假设有排成一行的N个位置,记为1~N,N一定大于等于2
     * 开始时机器人在其中的M位置上
     * 如果机器人来到1位置,那下一步只能往右来到2位置
     * 如果机器人来到N位置,那下一步只能往左来到N-1位置
     * 如果机器人在中间位置,那下一步可以往左或往右
     * 规定机器人必须走K步,最终来到P位置
     * 给四个参数N,M,K,P,求一共有多少种走法
     */
    public static int ways1(int N,int M,int K,int P){
        if(N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N){
            return 0;
        }
        return walk1(N,M,K,P);
    }

    /**
     * @param n 一共有几个位置
     * @param cur 当前来到的位置
     * @param rest 还剩几步
     * @param p 目标位置
     * @return 多少种走法
     */
    public static int walk1(int n, int cur, int rest, int p){
        if(rest == 0){
            return cur == p ? 1 : 0;
        }
        if(cur == 1){
            return walk1(n,2,rest - 1,p);
        }
        if(cur == n){
            return walk1(n,n - 1,rest - 1,p);
        }
        return walk1(n,cur + 1,rest - 1,p)
                + walk1(n,cur - 1,rest - 1,p);
    }

    //加缓存
    //动态规划记忆化搜索
    public static int waysCache(int N, int M, int K, int P){
        if(N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N){
            return 0;
        }
        int[][] dp = new int[N + 1][K + 1];
        for (int[] ints : dp) {
            for (int anInt : ints) {
                anInt = -1;
            }
        }
        return walkCache(N,M,K,P,dp);
    }

    public static int walkCache(int n, int cur, int rest, int end, int[][] dp){
        if(dp[cur][rest] != -1){
            return dp[cur][rest];
        }
        if(rest == 0){
            dp[cur][rest] = cur == end ? 1 : 0;
        } else if(cur == 1){
            dp[cur][rest] = walkCache(n,2,rest - 1,end,dp);
        } else if(cur == n){
            dp[cur][rest] = walkCache(n,n - 1,rest - 1,end,dp);
        } else{
            dp[cur][rest] = walkCache(n,cur + 1,rest - 1,end,dp)
                    + walkCache(n,cur - 1,rest - 1,end,dp);
        }
        return dp[cur][rest];
    }
    
    //改成动态规划
    public static int ways2(int n,int cur,int rest,int end){
        if(n < 2 || rest < 1 || cur < 1 || cur > n || end < 1 || end > n){
            return 0;
        }
        int[][] dp = new int[n + 1][rest + 1];
        dp[0][end] = 1;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= rest; j++){
                if(j == 1){
                    dp[i][j] = dp[i - 1][j - 1];
                }else if(j == rest){
                    dp[i][j] = dp[i - 1][j + 1];
                }else{
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
                }
            }
        }
        return dp[cur][rest];
    }
}

字符串的全部子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

public class Subsequence {
    /**
     * 打印一个字符串的全部子序列
     */
    public static List<String> subsequence1 (String s) {
        char[] str = s.toCharArray();
        String path = "";//已经处理过的字符
        List<String> ans = new ArrayList<>();
        process1(str,0,ans,path);
        return ans;
    }

    /**
     * 先尝试，缺什么补什么
     * @param s 字符串
     * @param index 当前来到哪个字符
     * @param ans 结果集
     * @param path 已经有哪些字符决定好了
     */
    public static void process1(char[] s,int index,List<String> ans,String path) {
        if(index == s.length) {
            ans.add(path);
            return;
        }
        String no = path;//当前字符不要的情况下
        process1(s,index + 1, ans, no);
        String yes = path + s[index];//当前字符要的情况下
        process1(s,index + 1, ans, yes);
    }

    /**
     * 打印一个字符串的全部子序列
     * 要求不要出现重复字面值的子序列
     * 字符串里有重复的字符
     * 把上面的代码中的list换成set自动去重
     */
    public static List<String> subsequenceNoRepeat(String s) {
        char[] str = s.toCharArray();
        String path = "";
        HashSet<String> set = new HashSet<>();
        process2(str,0,set,path);
        List<String> ans = new ArrayList<>();
        for (String cur : set) {
            ans.add(cur);
        }
        return ans;
    }
    public static void process2(char[] s,int index,HashSet<String> set,String path) {
        if(index == s.length) {
            set.add(path);
            return;
        }
        String no = path;//当前字符不要的情况下
        process2(s,index + 1, set, no);
        String yes = path + s[index];//当前字符要的情况下
        process2(s,index + 1, set, yes);
    }
    /**
     * 一个字符串中所有不重复子序列的个数
     */
}

字符串的全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

public class Permutations {
    /**
     * 打印一个字符串的全部排列
     */
    public static List<String> permutations (String s){
        List<String> ans = new ArrayList<>();
        if(s == null || s.length() == 0){
            return ans;
        }
        char[] str = s.toCharArray();
        process1(str,ans,0);
        return ans;
    }
    //s从0到n-1已经做好决定了
    //index及其以后的字符都有机会来到i位置
    public static void process1(char[] s, List<String> ans, int index){
        if(index == s.length){
            ans.add(Arrays.toString(s));
        }
        //i表示index后的所有字符
        for(int i = index; i < s.length; i++){
            swap(s,index,i);
            process1(s,ans,index + 1);
            swap(s,index,i);//还原,回溯
        }
    }
    public static void swap(char[] s,int i, int j){
        char temp = s[i];
        s[i] = s[j];
        s[j] = temp;
    }
    /**
     * 打印一个字符串的全部排列
     * 要求不出现重复的排列
     */
    //比较low的做法就是把上面的list改成hashset自动去重
    //这是暴力递归加过滤
    //这里就不写了

    /**
     * 用set记录重复的字符
     * 这是剪枝
     * 肯定比暴力递归加过滤更快
     */
    public static List<String> permutationsNoRepeat (String s){
        List<String> ans = new ArrayList<>();
        if(s == null || s.length() == 0){
            return ans;
        }
        char[] str = s.toCharArray();
        process2(str,ans,0);
        return ans;
    }
    public static void process2(char[] s, List<String> ans, int index){
        if(index == s.length){
            ans.add(Arrays.toString(s));
        }
        HashSet<Character> set = new HashSet<>();
        //i表示index后的所有字符
        for(int i = index; i < s.length; i++){
            if(!set.contains(s[i])){
                set.add(s[i]);//登记
                swap(s,index,i);
                process2(s,ans,index + 1);
                swap(s,index,i);//还原,回溯
            }
        }
    }
}

转化数字字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
public class LeftToRight {
    /**
     * 规定1和A对应、2和B对应、3和C对应。。。
     * 那么一个数字字符串比如"111"就可以转化为:
     * "AAA","KA"和"AK"
     * 给定一个数字字符串,返回有多少种转化结果
     */
    public static int number(String str){
        if(str == null || str.length() == 0){
            return 0;
        }
        return process(str.toCharArray(),0);
    }
    public static int process(char[] str, int i){
        if(i == str.length){
            return 1;
        }
        //当前字符是0
        if(str[i] == '0'){
            return 0;//表示没法转换,无效结果
        }
        //当前字符是1
        if(str[i] == '1'){
            int res = process(str,i + 1);//选'1'的情况
            if(i + 1 < str.length){//如果后面的字符没越界
                res += process(str,i + 2);//把'1'和后面字符组合起来的情况
            }
            return res;
        }
        //当前字符是2
        if(str[i] == '2'){
            int res = process(str, i + 1);//选'2'的情况
            //如果后面的字符没越界且合并起来是20到26的情况
            if(i + 1 < str.length && (str[i + 1] >= '0' && str[i + 1] <= '6')) {
                res += process(str, i + 2);
            }
            return res;
        }
        //当前字符是3到9,就不用考虑和后面字符合并了
        // str[i] = '3' ~ '9'
        return process(str, i + 1);
    }

    //改成动态规划
    public static int dp(String s) {
        if(s == null || s.length() == 0){
            return 0;
        }
        char[] str = s.toCharArray();
        int n = str.length;
        int[] dp = new int[n + 1];
        dp[n] = 1;
        for(int i = n - 1; i >= 0; i--){
            if(str[i] == '0'){
                dp[i] = 0;
            }
            if(str[i] == '1'){
                dp[i] = dp[i + 1];
                if(i + 1 < str.length){
                    dp[i] += dp[i + 2];
                }
            }
            if(str[i] == '2'){
                dp[i] = dp[i + 1];
                if(i + 1 < str.length && (str[i + 1] >= '0' && str[i + 1] <= '6')) {
                    dp[i] += dp[i + 2];
                }
            }
        }
        return dp[0];
    }
}

背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
public class Bag {
    /**
     * 给定两个长度都为N的数组weight和values
     * weights[i]和values[i]分别代表i号物品的重量和价值
     * 给定一个正数bag,表示一个载重bag的背包
     * 你装的物品不能超过这个重量
     * 返回你能装下最多的价值是多少
     */
    public static int bag1(int[] w, int[] v,int bag){
        return process1(w,v,0,0,bag);
    }

    /**
     * @param w 重量
     * @param v 价值
     * @param index 当前判断的物品
     * @param alreadyW 包里已经装了多少重量
     * @param bag 包
     * @return 能装下的最多价值
     */
    public static int process1(int[] w, int[] v, int index, int alreadyW, int bag) {
        if(alreadyW > bag) {
            return -1;//重量超了,方案无效
        }
        if (index == w.length){
            return 0;//已经全部判断完了,base case
        }
        //没要当前的物品
        int v1 = process1(w,v,index + 1,alreadyW,bag);

        //要当前的物品
        //先判断当前物品后面的过程
        int v2next = process1(w,v,index + 1,alreadyW + w[index],bag);
        int v2 = -1;
        if(v2next != -1){//如果后面的过程有效
            v2 = v[index] + v2next;
        }
        //在不要当前物品的情况和要当前物品的情况中选价值最高的
        return Math.max(v1,v2);
    }


    public static int bag2(int[] w, int[] v,int bag){
        return process2(w,v,0,bag);
    }

    /**
     *
     * @param w 重量
     * @param v 价值
     * @param index 当前物品
     * @param rest 还剩多少重量
     * @return 能装下的最多价值
     */
    public static int process2(int[] w,int[] v,int index,int rest){
        if(rest < 0){
            return -1;
        }
        if(index == w.length) {
            return 0;
        }
        //不要当前物品,剩余物品和空间能获得的最大价值
        int v1 = process2(w,v,index + 1,rest);

        //要当前的物品,剩余物品和空间能获得的最大价值
        int v2 = -1;
        //判断当前物品后面的过程
        int v2Next = process2(w,v,index + 1,rest - w[index]);
        if(v2Next != -1){//如果后面的过程有效
            v2 = v[index] + v2Next;
        }
        //在不要当前物品的情况和要当前物品的情况中选价值最高的
        return Math.max(v1,v2);
    }
    
    
    //改成动态规划
    public static int bag3 (int[] w, int[] v, int bag){
        int n = w.length;
        //行代表物品编号,列代表剩余载重
        int[][] dp = new int[n + 1][bag + 1];
        int v1;//不加入当前物品,剩余的最大价值
        int v2;//加入当前物品后,剩余的最大价值
        /**
         * 因为要靠index+1来判断当前index的价值
         * 而index = n代表所有物品都已经装入或剩余载重不足以装下任何物品,
         * 所以index = n时剩余价值都为0
         * 这样从n-1行(index = n -1)开始,
         * 就能够依靠下一行(index + 1)的价值来判断当前情况的价值
         * 所以从下往上遍历
         */
        for(int index = n - 1; index >= 0; index--){
            //rest表示剩余多少载重
            for(int rest = 0; rest <= bag; rest++){

//                int v1 = process2(w,v,index + 1,rest);
//                int v2 = -1;
//                int v2Next = process2(w,v,index + 1,rest - w[index]);
//                if(v2Next != -1){
//                    v2 = v[index] + v2Next;
//                }
//                return Math.max(v1,v2);
                //改写上面注释的过程
                v1 = dp[index + 1][rest];//不装的剩余最大价值
                v2 = -1;//装的剩余价值,默认装不下
                if(rest - w[index] >= 0){//如果能装下
                    //v[index] == 当前物品的价值
                    //dp[index + 1][rest - w[index]] == 装之后剩下的最大价值
                    v2 = v[index] + dp[index + 1][rest - w[index]];
                }
                //在装和不装当前物品剩余最大价值中选最大的
                dp[index][rest] = Math.max(v1, v2);
            }
        }
        //返回来到第0个物品,剩余载重为bag(即没装任何物品)的最大价值
        return dp[0][bag];

//        //简化写法
//        int[][] dp = new int[w.length + 1][bag + 1];
//        for(int index = w.length - 1; index >= 0; index--){
//            for(int rest = 0; rest <= bag; rest++ ){
//                dp[index][rest] = rest - w[index] >= 0 ?
//                        Math.max(dp[index + 1][rest],
//                                v[index] + dp[index + 1][rest - w[index]])
//                        : dp[index + 1][rest];
//            }
//        }
//        return dp[0][bag];
    }
}

纸牌博弈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
public class Scope {
    /**
     * 给定一个整型数组arr,代表数值不同的纸牌排成一条线
     * 玩家A和玩家B依次拿走每张纸牌
     * A先拿
     * 但是每个玩家每次只能拿走最右或最左的纸牌
     * 假设AB都很聪明,返回最后获胜者的分数
     */
    public static int win1(int[] arr){
        if(arr == null || arr.length == 0){
            return 0;
        }
        return Math.max(
                firstHand(arr,0,arr.length-1),//a的分数
                backHand(arr,0,arr.length -1)//b的分数
                 );
    }
    //l到r先手情况的分数
    public static int firstHand (int[] arr,int l, int r){
        if(l == r) {
            return arr[l];
        }
        return Math.max(
                arr[l] + backHand(arr,l + 1,r),
                arr[r] + backHand(arr,l,r-1) );
    }
    //l到r后手情况的分数
    public static int backHand(int[] arr,int l,int r) {
        if(l == r){
            return 0;
        }
        return Math.min(
                firstHand(arr,l + 1, r),
                firstHand(arr,l,r - 1));
    }


    //改成动态规划
    public static int win2(int[] arr){
        if(arr == null || arr.length == 0){
            return 0;
        }
        int n = arr.length;
        int[][] firstHand = new int[n][n];
        int[][] backHand = new int[n][n];
        for(int i = 0; i < n; i++){
            firstHand[i][i] = arr[i];
        }
        int l;
        int r;
        for(int i = 1; i < n; i++){
            l = 0;
            r = i;
            while(l < n && r < n){
                firstHand[l][r] = Math.max(
                        arr[l] + backHand[l + 1][r],
                        arr[r] + backHand[l][r - 1] );
                backHand[l][r] = Math.min(
                        firstHand[l + 1][r],
                        firstHand[l][r - 1]);
                l++;
                r++;
            }
        }
        return Math.max(
                firstHand[0][n - 1],
                backHand[0][n -1]
        );
    }
}

货币面值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

public class FaceValue {
    /**
     * 数组中每个数代表货币的面值
     * 给一个目标钱数,用数组中的面值凑成这个钱数
     * 返回有多少种方法
     * 数组无重复且都为正整数
     */
    //暴力递归
    public static int ways1(int[] arr, int aim){
        if(arr == null || arr.length == 0 || aim <=0 ){
            return 0;
        }
        return process1(arr,0,aim);
    }
    //可以用index及以后的面值
    //距离aim还剩rest
    public static int process1(int[] arr,int index,int rest){
//        if(rest < 0){
//            return 0;
//        }//for循环里加了限制,这里不用加了
        if(index == arr.length){
            return rest == 0 ? 1 : 0;
        }
        int ways = 0;
        for(int i = 0;i * arr[index] <= rest ;i++){
            ways += process1(arr,index + 1,rest - i * arr[index]);
        }
        return ways;
    }

    //加傻缓存
    public static int ways2(int[] arr, int aim){
        if(arr == null || arr.length == 0 || aim <=0 ){
            return 0;
        }
        int n = arr.length;
        int[][] dp = new int[n + 1][aim + 1];
        for(int i = 0; i < dp.length; i++){
            for(int j = 0; j < dp[0].length; j++){
                dp[i][j] = -1;
            }
        }
        return process2(arr,0,aim,dp);
    }
    public static int process2(int[] arr,int index,int rest,int[][] dp){
        if(dp[index][rest] != -1){
            return dp[index][rest];
        }
        if(index == arr.length){
            dp[index][rest] = rest == 0 ? 1 : 0;
            return dp[index][rest];
        }
        int ways = 0;
        for(int i = 0;i * arr[index] <= rest ;i++){
            ways += process2(arr,index + 1,rest - i * arr[index],dp);
        }
        dp[index][rest] = ways;
        return ways;
    }

    //改动态规划
    public static int ways3(int[] arr, int aim){
        if(arr == null || arr.length == 0 || aim <=0 ){
            return 0;
        }
        int n = arr.length;
        int[][] dp = new int[n + 1][aim + 1];
        dp[n][0] = 1;
        for(int index = n - 1; index >= 0; index--){
            for(int rest = 0; rest < aim; rest++){
                for(int i = 0;i * arr[index] <= rest ;i++){
                    dp[index][rest] += dp[index + 1][rest - i * arr[index]];
                }
            }
        }
        return dp[0][aim];
    }

    //优化动态规划
    public static int ways4(int[] arr, int aim){
        if(arr == null || arr.length == 0 || aim <=0 ){
            return 0;
        }
        int n = arr.length;
        int[][] dp = new int[n + 1][aim + 1];
        dp[n][0] = 1;
        for(int index = n - 1; index >= 0; index--){
            for(int rest = 0; rest < aim; rest++){
                dp[index][rest] = dp[index + 1][rest];
                if(rest - arr[index] >= 0){
                    dp[index][rest] += dp[index][rest - arr[rest]];
                }
            }
        }
        return dp[0][aim];
    }
}

贴纸问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import java.util.HashMap;
public class Paster {

    /**
     * @param s 字符串
     * @param paster 贴纸,可以剪碎成一个个字符
     * @return 拼成s最少要几张贴纸
     */
    public static int paster(String s, String[] paster){
        int n = paster.length;
        int[][] map = new int[n][26];//行代表贴纸编号,列代表每个字母的数量
        //key = rest value = 至少几张贴纸
        HashMap<String, Integer> dp = new HashMap<>();
        //paster存入map
        for(int i = 0; i < n; i++){
            char[] str = paster[i].toCharArray();
            for(char c : str){
                map[i][c - 'a']++;
            }
        }
        //base case 之一
        dp.put("", 0);
        return process1(dp, map, s);
    }
    public static int process1(HashMap<String, Integer> dp,
                               int[][] map,
                               String rest){
        if(dp.containsKey(rest)){//如果算过就直接拿
            return dp.get(rest);
        }
        int ans = Integer.MAX_VALUE;//当前rest至少几张贴纸,默认最大值
        int n = map.length;
        int[] restMap = new int[26];//rest转为数组的形式
        char[] target = rest.toCharArray();
        for(char c : target){
            restMap[c - 'a']++;
        }
        //从还剩n-i种贴纸开始
        for(int i = 0; i < n; i++){
            //从rest的第一个字符开始搞定,
            // 如果map里第i个贴纸没有rest里的第一个字符
            //直接跳下一种贴纸
            //也可以理解为rest里至少有一个字符可以被搞定,才去试,不然递归就跑不完了
            //贴纸的使用顺序无所谓
            //所以从第一个字符开始可以减少重复解
            if(map[i][target[0] - 'a'] == 0){
                continue;
            }
            StringBuilder sb = new StringBuilder();
            for(int j = 0; j < 26; j ++){//枚举每个字母
                if(restMap[j] > 0){//如果需要这个字母
                    for(int k = 0; k < Math.max(0,restMap[j] - map[i][j]); k++){
                        //sb用来构造下一个rest
                        sb.append((char)('a' + j));
                    }
                }
            }
            String s = sb.toString();
            int tmp = process1(dp,map,s);
            if(tmp != -1){
                ans = Math.min(ans,1 + tmp);//i号贴纸加后序的贴指数
            }
        }
        dp.put(rest,ans == Integer.MAX_VALUE ? -1 : ans);
        return dp.get(rest);
    }
}

最长公共子序列LCS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class LCS {
    public static int lcs(String s1, String s2){
        int[][] dp = new int[s1.length()][s2.length()];
        dp[0][0] = s1.charAt(0) == s2.charAt(0) ? 1 : 0;
        for(int i = 1; i < s1.length(); i++){
            dp[i][0] = Math.max(dp[i - 1][0], s1.charAt(i) == s2.charAt(0) ? 1 : 0);
        }
        for(int j = 1; j < s2.length(); j++){
            dp[0][j] = Math.max(dp[0][j - 1], s1.charAt(0) == s2.charAt(j) ? 1 : 0);
        }
        for(int i = 1; i < dp.length; i ++){
            for(int j = 1; j < dp[0].length; j ++){
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                if(s1.charAt(i) == s2.charAt(j)){
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
                }
            }
        }
        return dp[s1.length() - 1][s2.length() - 1];
    }
}

洗杯子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
public class WashCups {
    /**
     * @param drinks 记录每个人喝完咖啡的时间点,升序数组
     * @param washTime 洗咖啡杯机只能串行地洗,洗一个杯子需要的时间
     * @param dryTime 不洗杯子让它自然挥发的时间
     * @return 最早洗完所有杯子的时间
     * 每个杯子要等喝完才能洗或者挥发
     * 不能挥发一半拿去洗
     * 一旦放进洗咖啡机里排队,那杯子就不会挥发了
     */
    public static int wash(int[] drinks, int washTime, int dryTime){
        if(drinks == null || drinks.length == 0){
            return 0;
        }
        if( washTime > dryTime){
            return drinks[drinks.length - 1] + dryTime;
        }
        return process(drinks,washTime,dryTime,0,0);
    }

    /**
     * @param index 该决定第i个杯子是否要放进洗咖啡杯机排队
     * @param washLine 洗咖啡杯机何时能洗完里面的杯子
     * @return index及以后的咖啡杯最早啥时候洗完
     */
    public static int process(int[] drinks, int washTime, int dryTime, int index, int washLine){
        int wash = Math.max(washLine, drinks[index]) + washTime;//选择洗
        int dry = drinks[index] + dryTime;//选择挥发
        if(index == drinks.length - 1){//如果来到最后一个杯子
            return Math.min(
                    wash,
                    dry
            );
        }
        //选择放进洗咖啡杯机里排队
        int next1 = process(drinks,washTime,dryTime,index + 1, wash);
        int p1 = Math.max(wash,next1);//取瓶颈因素
        //选择自然挥发
        int next2 = process(drinks,washTime,dryTime,index + 1,washLine);
        int p2 = Math.max(dry,next2);//取瓶颈因素
        //取最短时间
        return Math.min(p1,p2);
    }

    //改成动态规划
    public static int dp(int[] drinks, int washTime, int dryTime){
        if(drinks == null || drinks.length == 0){
            return 0;
        }
        if( washTime > dryTime){
            return drinks[drinks.length - 1] + dryTime;
        }
        int limit = 0;
        int n = drinks.length;
        for(int i = 0; i < n; i++){
            limit = Math.max(limit, drinks[i]) + washTime;
        }
        int[][] dp = new int[n][limit + 1];

        for(int washLine = 0; washLine < limit; washLine++){
            dp[n - 1][washLine] = Math.min(Math.max(washLine, drinks[n - 1]) + washTime,drinks[n - 1] + dryTime);
        }
        for(int index = n - 2; index >= 0; index--){
            for(int washLine = 0; washLine < limit; washLine++){

                int p1 = Integer.MAX_VALUE;
                int wash = Math.max(washLine, drinks[index]) + washTime;
                if(wash <= limit){
                    p1 = Math.max(wash,dp[index + 1][wash]);
                }

                int dry = drinks[index] + dryTime;
                int p2 = Math.max(dry,dp[index + 1][washLine]);

                dp[index][washLine] = Math.min(p1,p2);
            }
        }
        return dp[0][0];
    }
}

马走日

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Cheese {
    /**
     * 象棋中,马从(0,0)位置跳到(x,y)位置必须跳k步,有多少种方法
     */
    public static int getWays(int x,int y, int k){
        int[][][] dp = new int[10][9][k + 1];
        dp[0][0][0] = 1;
        for(int step = 1; step < k + 1; step++){
            for(int i = 0; i < 10; i++){
                for(int j = 0; j < 9; j++){
                    dp[i][j][step] += getVal(dp,i + 2, j + 1,step - 1);
                    dp[i][j][step] += getVal(dp,i + 2, j - 1,step - 1);
                    dp[i][j][step] += getVal(dp,i - 2, j + 1,step - 1);
                    dp[i][j][step] += getVal(dp,i - 2, j - 1,step - 1);
                    dp[i][j][step] += getVal(dp,i + 1, j + 2,step - 1);
                    dp[i][j][step] += getVal(dp,i + 1, j - 2,step - 1);
                    dp[i][j][step] += getVal(dp,i - 1, j + 2,step - 1);
                    dp[i][j][step] += getVal(dp,i - 1, j - 2,step - 1);
                }
            }
        }
        return dp[x][y][k];
    }
    public static int getVal(int[][][] dp, int i, int j,int k){
        if(i < 0 || i >= 10 || j < 0 || j >= 9) {
            return 0;
        }
        return dp[i][j][k];
    }
    public static void main(String[] args) {
        System.out.println(getWays(1,2,1));
    }
}

最小不可组成和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import java.util.Arrays;
public class MinIncomposableSum {
    /**
     * 给定一个正数数组arr,其中所有的值都为整数
     * 以下是最小不可组成和的概念
     * 把arr每个子集内的所有元素加起来会出现很多值
     * 其中最小的记为min,最大的记为max
     * 在区间[min, max]上,如果有数不可以被arr的某个子集相加得到
     * 那么其中最小的那个数是arr的最小不可组成和
     * 在区间[min, max]上,如果所有有数都可以被arr的某个子集相加得到
     * 那么max+1是arr的最小不可组成和
     */
    public static int minIncomposableSum(int[] arr){
        int n = arr.length;
        int min = Integer.MAX_VALUE;
        int sum = 0;
        for (int i : arr) {
            min = Math.min(min, i);
            sum += i;
        }
        boolean[][] dp = new boolean[n][sum + 1];
        dp[0][arr[0]] = true;
        for(int i = 1; i < n; i++){
            for(int j = 1; j < sum + 1; j++){
                if(arr[i] == j){
                    dp[i][j] = true;
                }else if(dp[i - 1][j]){
                    dp[i][j] = true;
                }else if(j - arr[i] >= 0 && dp[i - 1][j- arr[i]]){
                    dp[i][j] = true;
                }
            }
        }
        int ans = min;
        while(ans <= sum){
            if(dp[n - 1][ans]){
                return ans;
            }
            ans++;
        }
        return sum + 1;
    }

    /**
     * 如果arr中必有1,怎么优化
     */
    public static int plus(int[] arr){
        Arrays.sort(arr);
        int range = 1;
        for(int i = 1; i < arr.length; i++){
            if(arr[i] <= range + 1) {
                range += arr[i];
            } else {
                return range + 1;
            }
        }
        return range + 1;
    }
}

贿赂怪兽

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class BribeMonster {
    /**
     * 贿赂怪兽
     * 给俩数组d[] p[]
     * d[i] 表示i号怪兽的能力值
     * p[i] 表示贿赂i号怪兽需要的钱数
     * 你的初始能力值为0
     * 当你贿赂怪兽后,怪兽的能力值会加到你的能力值上
     * 你必须从0位置开始依次通过每个怪兽
     * 来到i位置时,如果你的能力值大于等于i号怪兽,可以直接通过,也可以选择贿赂它
     * 否则就只能贿赂当前怪兽
     * 返回通过所有怪兽需要的最少钱数
     */
    public static int bribeMonster(int[] d, int[] p){
        return process(d, p, 0, 0);
    }
    public static int process(int[] d, int[] p, int index, int value){
        if(index == d.length){
            return 0;
        }
        if(value >= d[index]){
            return Math.min(process(d, p, index + 1, value + p[index]),
                    process(d, p, index + 1, value));
        }else {
            return process(d, p, index + 1, value + p[index]);
        }
    }
    //改成动态规划
    public static int dp(int[] d, int[] p){
        int total = 0;
        for (int j : p) {
            total += j;
        }
        int[][] dp = new int[d.length + 1][total + 1];
        for(int index = d.length - 1; index >= 0; index--){
            for(int value = 0; value <= total; value++){
                if(value >= d[index]){
                    dp[index][value] = Math.min(dp[index + 1][value + p[index]],
                            dp[index + 1][value]);
                }else{
                    dp[index][value] = dp[index + 1][value + p[index]];
                }
            }
        }
        return dp[0][0];
    }

}

成为回文最少插入次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//力扣1312
class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        if(n == 1){
            return 0;
        }
        if(n == 2){
            return s.charAt(0) == s.charAt(1) ? 0 : 1;
        }
        int[][] dp = new int[n][n];
        char[] str = s.toCharArray();
        for(int i = 0; i < n - 1; i++){
            if(str[i] != str[i + 1]){
                dp[i][i + 1] = 1;
            }   
        }
        for(int l = n - 3; l >= 0; l--){
            for(int r = l + 2; r < n; r++){
                if(str[l] == str[r]){
                    dp[l][r] = Math.min(Math.min(dp[l + 1][r], dp[l][r - 1]) + 1, dp[l + 1][r - 1]);
                }else {
                    dp[l][r] = Math.min(dp[l + 1][r], dp[l][r - 1]) + 1;
                }
            }
        }
        return dp[0][n - 1];
    }
}

最长递增路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//力扣329
class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        int res = 0;
        int[][] dp = new int[matrix.length][matrix[0].length];
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                res = Math.max(res, process(matrix, i, j, dp));
            }
        }
        return res;
    }
    public int process(int[][] matrix, int i, int j, int[][] dp){
        if(dp[i][j] != 0){
            return dp[i][j];
        }
        int nextUp = 0;
        if(i > 0  && matrix[i - 1][j] > matrix[i][j]){
            nextUp = process(matrix, i - 1, j, dp);
        }
        int nextDown = 0;
        if(i < matrix.length - 1 && matrix[i + 1][j] > matrix[i][j]){
            nextDown = process(matrix, i + 1, j, dp);
        }
        int nextLeft = 0;
        if(j > 0  && matrix[i][j - 1] > matrix[i][j]){
            nextLeft = process(matrix, i, j - 1, dp);
        }
        int nextRight = 0;
        if(j < matrix[0].length - 1 && matrix[i][j + 1] > matrix[i][j]){
            nextRight = process(matrix, i, j + 1, dp);
        }
        dp[i][j] = Math.max(Math.max(nextLeft,nextRight),Math.max(nextDown,nextUp)) + 1;
        return dp[i][j];
    }
}

字符串解码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//力扣394
class Solution {
    public String decodeString(String s) {
        return process(s.toCharArray(), 0).res;
    }
    public class Info {
        private String res;
        private int stop;

        public Info(String r, int s){
            res = r;
            stop = s;
        }
    }
    public Info process(char[] s, int index){
        StringBuilder res = new StringBuilder();
        int count = 0;
        while(index < s.length && s[index] != ']'){
            if(s[index] == '['){
                Info info = process(s, index + 1);
                while(count > 0){
                    res.append(info.res);
                    count--;
                }
                index = info.stop + 1;
            } else {
                if(s[index] >= '0' && s[index] <= '9'){
                    count = count * 10 + s[index] - '0';
                }
                if(s[index] >= 'a' && s[index] <= 'z' ){
                    res.append(String.valueOf(s[index]));
                }
                
                index++;
            }
        }
        return new Info(res.toString(),index);
    }
}

树

堆

大根堆

任何子树最大值都是头结点的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
public class BigHeap {
    //heapSize既表示新来的数该放哪,又表示堆大小
    int heapSize;
    int[] heap;
    private final int limit;
    public BigHeap(int limit){
        heapSize = 0;
        heap = new int[limit];
        this.limit = limit;
    }
    public boolean isEmpty(){
        return heapSize == 0;
    }
    public boolean isFull(){
        return heapSize == limit;
    }

    /**
     * 加入一个树,调整为大根堆
     * 复杂度:O(logN)
     * @param value 加入的数
     */
    public void push(int value){
        if(isFull()){
            throw new RuntimeException("heap is full");
        }
        heap[heapSize] = value;
        heapInsert(heap,heapSize++);
    }

    /**
     * 从index位置往上浮,直到我不再比父节点大或我没有父节点
     * O(logN)
     * @param arr
     * @param index
     */
    private void heapInsert(int[] arr,int index){
        while(arr[index] > arr[(index - 1) / 2]){
            swap(arr,index,(index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    private void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 用户让你返回最大值,然后去掉最大值,剩下部分依然是大根堆
     * 复杂度:O(logN)
     * @return 堆中最大值
     */
    public int pop(){
        int ans = heap[0];
        //第一个数和最后一个数交换,
        swap(heap,0,--heapSize);
        heapify(heap,0,heapSize);
        return ans;
    }

    /**
     * 从index位置往下沉,直到我的孩子都不再比我大,或者没孩子了
     * O(logN)
     * @param arr 堆
     * @param index 数
     * @param heapSize 堆大小
     */
    private void heapify(int[] arr,int index,int heapSize){
        //左孩子下标
        int left = index * 2 + 1;
        //不越界时
        while(left < heapSize){
            //获取较大孩子的下标
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            //获取子树中最大值的下标
            largest = arr[largest] > arr[index] ? largest : index;
            //如果最大值就是自己,break
            if(largest == index){
                break;
            }
            //自己和最大值交换
            swap(arr,index,largest);
            //下沉
            index = largest;
            //左孩子下标
            left = index * 2 + 1;
        }
    }

}

堆排序

在时间复杂度O(N*logN)的情况下，额外空间复杂度可达到O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
public class HeapSort {
    /**
     * 给你一个数组,排成大根堆
     * 用heapify的方式
     * O(N)
     * @param arr
     */
    public void heapSort1(int[] arr){
        //从后往前heapify
        for(int i = arr.length - 1; i > 0; i--){ //O(N)
            heapify(arr, i, arr.length);//O(logN)
        }
    }
    /**
     * 给你一个数组,排成大根堆
     * 用heapInsert的方式
     * O(N*logN)
     * @param arr
     */
    public void heapSort2(int[] arr){
        for(int i = 0;i < arr.length; i++){ //O(N)
            heapInsert(arr,i);//O(logN)
        }
    }

    /**
     * 给你一个大根堆,排成有序
     * O(N*logN)
     * @param bigHeap
     */
    public void bigHeapSort(int[] bigHeap){
        int heapSize = bigHeap.length;
        while(heapSize > 0){ //O(N)
            swap(bigHeap,0,--heapSize);//O(1)
            heapify(bigHeap,0,heapSize);//O(logN)
        }
    }
    /**
     * 堆排序
     * O(N*logN)
     * @param arr
     */
    public void sort(int[] arr){
        heapSort1(arr);//O(N)
        bigHeapSort(arr);//O(N*logN)
    }
    /**
     * 从index位置往下沉,直到我的孩子都不再比我大,或者没孩子了
     * O(logN)
     * @param arr 堆
     * @param index 数
     * @param heapSize 堆大小
     */
    private void heapify(int[] arr,int index,int heapSize) {
        //左孩子下标
        int left = index * 2 + 1;
        //不越界时
        while (left < heapSize) {
            //获取较大孩子的下标
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            //获取子树中最大值的下标
            largest = arr[largest] > arr[index] ? largest : index;
            //如果最大值就是自己,break
            if (largest == index) {
                break;
            }
            //自己和最大值交换
            swap(arr, index, largest);
            //下沉
            index = largest;
            //左孩子下标
            left = index * 2 + 1;
        }
    }
    /**
     * 从index位置往上浮,直到我不再比父节点大或我没有父节点
     * O(logN)
     * @param arr
     * @param index
     */
    private void heapInsert(int[] arr,int index){
        while(arr[index] > arr[(index - 1) / 2]){
            swap(arr,index,(index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    private void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

系统实现的堆PriorityQueue

几乎有序的数组

题目：已知一个几乎有序的数组。几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离一定不会超过k，并且k相对于数组长度来说是比较小的

请选择一个合适的排序策略，对这个数组进行排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.PriorityQueue;
//在k小于数组长度时,时间复杂度O(N * logk)
//在k大于数组长度时,时间复杂度O(N * logN)
//所以在k小于数组长度时是非常好的排序策略
public class PriorityQueue_ {
    public static void AlmostOrderly(int[] arr,int k){
        PriorityQueue<Integer> pq = new PriorityQueue<>();//小根堆
        int index = 0;
        //所有数依次入堆
        for(int i = 0;i < arr.length;i++){//O(N)
            pq.add(arr[i]);//O(1)
            //前k + 1个数入堆后开始弹出
            if(pq.size() > k + 1 ){//O(logk)
                arr[index++] = pq.poll();
            }
        }
        //弹出剩下的k个数  每次弹出O(logk)
        //或者在数组长度不大于k的情况下,全部弹出 每次弹出O(logN)
        while(!pq.isEmpty()){
            arr[index++] = pq.poll();
        }
    }
}

比较器

用比较器把PriorityQueue改成大根堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static class MyComp implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
}
    
public static void main(String[] args) {
    PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>(new MyComp());
    //或者
    PriorityQueue<Integer> priorityQueue2 = new PriorityQueue<>(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });
}

TopK

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
import java.util.Comparator;
import java.util.PriorityQueue;

public class TopK {
    /**
     * 一堆数分布在两个有序数组中
     * 找出最大的K个数
     */
    public static class Node{
        private int ai;
        private int bi;
        private final int sum;
        public Node(int a, int b, int s){
            ai = a;
            bi = b;
            sum = s;
        }
    }
    public static int[] topK(int[] a, int[] b, int k){
        PriorityQueue<Node> heap = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o2.sum - o1.sum;
            }
        });
        int i = a.length - 1;
        int j = b.length - 1;
        k = Math.min(k,(i + 1) * (j + 1));
        boolean[][] check = new boolean[i + 1][j + 1];
        int[] res = new int[k];
        int index = 0;
        heap.add(new Node(i,j,a[i] + b[j]));
        check[i][j] = true;
        while(index < k){
            Node cur = heap.poll();
            res[index++] = cur.sum;
            i = cur.ai;
            j = cur.bi;
            if(i - 1 >= 0 && !check[i - 1][j]){
                check[i - 1][j] = true;
                heap.add(new Node(i - 1, j, a[i - 1] + b[j]));
            }
            if(j - 1 >= 0 && !check[i][j - 1]){
                check[i][j - 1] = true;
                heap.add(new Node(i, j - 1, a[i] + b[j - 1]));
            }
        }
        return res;
    }

    /**
     * 一个二维数组,每一行和每一列都是有序的
     * 但整体是无序的
     * 返回最小的k个数
     */
    public static int[] topK(int[][] arr, int k){
        PriorityQueue<Node> heap = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.sum - o2.sum;
            }
        });
        boolean[][] check = new boolean[arr.length][arr[0].length];
        int[] res = new int[k];
        int index = 0;
        heap.add(new Node(0,0,arr[0][0]));
        check[0][0] = true;
        int i = 0;
        int j = 0;
        while(index < k){
            Node cur = heap.poll();
            res[index++] = cur.sum;
            i = cur.ai;
            j = cur.bi;
            if(i + 1 < arr.length && !check[i + 1][j]){
                check[i + 1][j] = true;
                heap.add(new Node(i + 1, j, arr[i + 1][j]));
            }
            if(j + 1 < arr.length && !check[i][j + 1]){
                check[i][j + 1] = true;
                heap.add(new Node(i, j + 1, arr[i][j + 1]));
            }
        }
        return res;
    }
}

前缀树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
import java.util.HashMap;
public class TrieTree {
    public static class Node{
        public int pass;//该节点被通过了多少次
        public int end;//有多少字符串以此节点作为结尾
        public HashMap<Character,Node> next;//key -> 通往某个字符的路  ,  valve -> 此路指向的节点
        public Node(){
            pass = 0;
            end = 0;
            next = new HashMap<>();
        }
    }
    public static class Trie{
        private Node root;
        public Trie(){
            root = new Node();
        }

        public void insert(String s){
            if(s == null){
                return;
            }
            Node node = root;
            node.pass++;
            for(int i = 0; i < s.length(); i++){
                if(!node.next.containsKey(s.charAt(i))){
                    node.next.put(s.charAt(i),new Node());
                }
                node = node.next.get(s.charAt(i));
                node.pass++;
            }
            node.end++;
        }


        /**
         * @param s 要查询的字符串
         * @return 树中加入过多少个word
         */
        public int search(String s){
            if(s == null){
                return 0;
            }
            Node node = root;
            for(int i = 0; i < s.length(); i++){
                if(!node.next.containsKey(s.charAt(i))){
                    return 0;
                }
                node = node.next.get(s.charAt(i));
            }
            return node.end;
        }

        /**
         * @param s 要删除的字符串
         */
        public void delete(String s){
            if(search(s) == 0){
                return;
            }
            Node node = root;
            node.pass--;
            for(int i = 0; i < s.length(); i++){
                if(--node.next.get(s.charAt(i)).pass == 0){
                    node.next.remove(s.charAt(i));
                    return;
                }
                node = node.next.get(s.charAt(i));
            }
            node.end--;
        }

        /**
         * @param pre 前缀
         * @return 以pre为前缀的字符串的个数
         */
        public int prefixNumber(String pre){
            if(pre == null){
                return 0;
            }
            Node node = root;
            for(int i = 0; i < pre.length(); i++){
                if(!node.next.containsKey(pre.charAt(i))){
                    return 0;
                }
                node = node.next.get(pre.charAt(i));
            }
            return node.pass;
        }
    }
}

AC自动机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import java.util.LinkedList;
import java.util.Queue;

public class AC {
    public class Node {
        public int end;
        public Node fail;
        public Node[] nexts;

        public Node(){
            end = 0;
            fail = null;
            nexts = new Node[26];
        }
    }
    public class ACAutomation {
        private Node root;
        public ACAutomation() {
            root = new Node();
        }
        public void insert(String s){
            char[] str = s.toCharArray();
            Node cur = root;
            int index = 0;
            for (char c : str) {
                index = c - 'a';
                if (cur.nexts[index] == null) {
                    Node next = new Node();
                    cur.nexts[index] = next;
                }
                cur = cur.nexts[index];
            }
            cur.end++;
        }
        public void build() {
            Queue<Node> queue = new LinkedList<>();
            queue.add(root);
            Node cur = null;
            Node cfail = null;
            while(!queue.isEmpty()){
                cur = queue.poll();
                for(int i = 0; i < 26; i++){
                    if(cur.nexts[i] != null){
                        cur.nexts[i].fail = root;
                        cfail = cur.fail;
                        while(cfail != null){
                            if(cfail.nexts[i] != null){
                                cur.nexts[i].fail = cfail.nexts[i];
                                break;
                            }
                            cfail  = cfail.fail;
                        }
                        queue.add(cur.nexts[i]);
                    }
                }
            }
        }
    }
}

二叉树

先序中序后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
import java.util.Stack;
public class BinaryTree {
    public static class Node{
        public int value;
        public Node left;
        public Node right;
        public Node(int value){
            this.value = value;
        }
    }

    /**
     * 前序打印
     * 递归
     * @param head 头节点
     */
    public static void pre1(Node head){
        if(head == null){
            return;
        }
        System.out.println(head.value);
        pre1(head.left);
        pre1(head.right);
    }
    /**
     * 前序打印
     * 非递归
     * @param head 头节点
     */
    public static void pre2(Node head){
        if(head == null){
            return;
        }
        Stack<Node> nodes = new Stack<>();
        nodes.push(head);
        /**
         * 先把head入栈然后弹出打印
         * 然后
         * 入栈顺序:右->左->头
         */
        while(!nodes.isEmpty()){
            head = nodes.pop();
            System.out.println(head.value);
            if(head.right != null){
                nodes.push(head.right);
            }
            if(head.left != null){
                nodes.push(head.left);
            }
        }
    }
    /**
     * 中序打印
     * 递归
     * @param head 头节点
     */
    public static void in1(Node head){
        if(head == null){
            return;
        }
        in1(head.left);
        System.out.println(head.value);
        in1(head.right);
    }
    /**
     * 中序打印
     * 非递归
     * @param head 头节点
     */
    public static void in2(Node head){
        if(head == null){
            return;
        }
        Stack<Node> nodes = new Stack<>();
        while(!nodes.isEmpty() || head != null){
            if(head != null){//左边界入栈
                nodes.push(head);
                head = head.left;
            }else{//左边界全部入栈以后弹出一个,来到右子树继续把左边界全部入栈
                head = nodes.pop();
                System.out.println(head.value);
                head = head.right;
            }
        }
    }
    /**
     * 后序打印
     * 递归
     * @param head 头节点
     */
    public static void pos1(Node head){
        if(head == null){
            return;
        }
        pos1(head.left);
        pos1(head.right);
        System.out.println(head.value);
    }
    /**
     * 后序打印
     * 非递归,用俩栈
     * @param head 头节点
     */
    public static void pos2(Node head){
        if(head == null){
            return;
        }
        Stack<Node> nodes = new Stack<>();
        Stack<Node> help = new Stack<>();
        nodes.push(head);
        /**
         * head入nodes栈弹出后入help栈
         * 入nodes栈的顺序:左 -> 右 -> 头
         * 出nodes栈的顺序(即入help栈的顺序):头 -> 右 -> 左
         * 出help栈的顺序:左 -> 右 -> 头
         */
        while(!nodes.isEmpty()){
            head = nodes.pop();
            help.push(head);
            if(head.left != null){
                nodes.push(head.left);
            }
            if(head.right != null){
                nodes.push(head.right);
            }
        }
        //弹出
        while(!help.isEmpty()){
            System.out.println(help.pop().value);
        }
    }
    /**
     * 后序打印
     * 非递归,用一个栈
     * @param head 头节点
     */
    public static void pos3(Node head){
        if(head == null){
            return;
        }
        Stack<Node> nodes = new Stack<>();
        Node cur = null;
        nodes.push(head);
        /**
         * 一开始,左边界全部入栈
         * 弹出最左下角的元素
         * head用来记录上一个弹出的元素,以head为头的子树代表已经全部处理过了
         */
        while(!nodes.isEmpty()){
            cur = nodes.peek();
            if(cur.left != null && cur.left != head && cur.right != head){
                //左右子树都没处理的话去处理左边
                nodes.push(cur.left);
            }else if(cur.right != null && cur.right != head){
                //左边处理了但右边没处理,去处理右边
                nodes.push(cur.right);
            }else{
                //左右子树都处理了,弹出,返回上一层
                System.out.println(nodes.pop().value);
                head = cur;
            }
        }
    }

    /**
     * 递归序
     * 每个节点会到达三次
     * 第一次到达时打印,就是先序
     * 第二次到达时打印,就是中序
     * 第三次到达时打印,就是后序
     * @param head 头节点
     */
    public static void f(Node head){
        if(head == null){
            return;
        }
        System.out.println(head.value);
        f(head.left);
        System.out.println(head.value);
        f(head.right);
        System.out.println(head.value);
    }
}

按层遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//宽度优先遍历
public static void byLayer(Node head){
        Queue<Node> nodes = new LinkedList<>();
        nodes.add(head);
        while(!nodes.isEmpty()){
            head = nodes.poll();
            System.out.println(head.value);
            if(head.left != null){
                nodes.add(head.left);
            }
            if(head.right != null){
                nodes.add(head.right);
            }
        }
    }

最大宽度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class MaxWidth {
    public static class Node{
        public int value;
        public Node left;
        public Node right;
        public Node(int value){
            this.value = value;
        }
    }

    /**
     * 用哈希表
     * + 先实现一个宽度优先遍历
     * + 然后加入以下参数
     * + levelMap
     * + curLevel
     * + curLevelNodes
     * + max
     * + 比较curLevel和当前节点的层号来判断是否来到了新的一层
     * + 如果来到了新的一层就结算上一层的节点数
     * @param head 头节点
     * @return 最大宽度
     */
    public static int maxWidth1(Node head){
        if(head == null){
            return 0;
        }
        Queue<Node> nodes = new LinkedList<>();
        nodes.add(head);
        HashMap<Node,Integer> levelMap = new HashMap<>();
        levelMap.put(head,1);
        int max = 0;
        int curLevel = 1;
        int curLevelNodes = 0;
        while(!nodes.isEmpty()){
            Node cur = nodes.poll();
            int curNodeLevel = levelMap.get(cur);
            if(cur.left != null){
                levelMap.put(cur.left,curNodeLevel + 1);
                nodes.add(cur.left);
            }
            if(cur.right != null){
                levelMap.put(cur.right,curNodeLevel + 1);
                nodes.add(cur.right);
            }
            if(curNodeLevel == curLevel){
                curLevelNodes++;
            }else{
                curLevel++;
                max = Math.max(max,curLevelNodes);
                curLevelNodes = 1;
            }
        }
        return Math.max(max,curLevelNodes);
    }

    /**
     * 不用哈希表
     * + 先实现一个宽度优先遍历
     * + 然后加入以下参数
     * + curEnd
     * + nextEnd
     * + max
     * + curLevelNodes
     * + 每次加入队列时更新nextEnd
     * + 比较当前弹出的节点和curEnd
     * + 如果是curEnd,更新最大值,curLevelNodes归零,curEnd = nextEnd
     * @param head 头节点
     * @return 最大宽度
     */
    public static int maxWidth2(Node head){
        if(head == null){
            return 0;
        }
        Queue<Node> nodes = new LinkedList<>();
        nodes.add(head);
        Node curEnd = head;
        Node nextEnd = null;
        int max = 0;
        int curLevelNodes = 0;
        while(!nodes.isEmpty()){
            Node cur = nodes.poll();
            if(cur.left != null){
                nodes.add(cur.left);
                nextEnd = cur.left;
            }
            if(cur.right != null){
                nodes.add(cur.right);
                nextEnd = cur.right;
            }
            curLevelNodes++;
            if(cur == curEnd){
                max = Math.max(max,curLevelNodes);
                curLevelNodes = 0;
                curEnd = nextEnd;
            }
        }
        return max;
    }
}

序列化和反序列化

“#”代表null节点，”!”代表一个值的结束

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class Serialize {
    public static class Node{
        public int value;
        public Node left;
        public Node right;
        public Node(int value){
            this.value = value;
        }
    }
    /**
     * 先序中序后序序列化
     * @param head 头节点
     * @return 序列化后的字符串
     */
    public static String serialize1(Node head){
        if(head == null){
            return "#!";
        }
        String res = "";
        res += head.value + "!";//先序
        res += serialize1(head.left);
        //res += head.value + "!";//中序
        //中序序列化没有意义,因为中序序列化后没办法反序列化
        res += serialize1(head.right);
        //res += head.value + "!";//后序
        return res;
    }

    /**
     * 层序序列化
     * @param head 头节点
     * @return 序列化后的字符串
     */
    public static String serialize2(Node head){
        if(head == null){
            return "#!";
        }
        Queue<Node> nodes = new LinkedList<>();
        nodes.add(head);
        String res = head.value + "!";
        while(!nodes.isEmpty()){
            head = nodes.poll();
            if(head.left != null){
                res += head.left.value + "!";
                nodes.add(head.left);
            }else{
                res += "#!";
            }
            if(head.right != null){
                res += head.right.value + "!";
                nodes.add(head.right);
            }else{
                res += "#!";
            }
        }
        return res;
    }

    /**
     * 先序反序列化
     * @param tree 序列化的树
     * @return 头节点
     */
    public static Node preDeserialize(String tree){
        String[] values = tree.split("!");
        Queue<String> queue = new LinkedList<>(Arrays.asList(values));
        return preGetNode(queue);
    }
    public static Node preGetNode(Queue<String> queue){
        String value = queue.poll();
        if(value.equals("#")){
            return null;
        }
        Node head = new Node(Integer.parseInt(value));
        head.left = preGetNode(queue);
        head.right = preGetNode(queue);
        return head;
    }

    /**
     * 后序反序列化
     * @param tree 序列化的树
     * @return 头节点
     */
    public static Node posDeserialize(String tree){
        String[] values = tree.split("!");
        Stack<String> stack = new Stack<>();
        for (String value : values) {
            stack.push(value);
        }
        return posGetNode(stack);
    }
    public static Node posGetNode(Stack<String> stack){
        String value = stack.pop();
        if(value.equals("#")){
            return null;
        }
        Node head = new Node(Integer.parseInt(value));
        head.right = posGetNode(stack);
        head.left = posGetNode(stack);
        return head;
    }

    /**
     * 层序反序列化
     * @param tree 序列化的树
     * @return 头节点
     */
    public static Node deserializeByLevel(String tree){
        String[] values = tree.split("!");
        int index = 0;
        Node head = getNode(values[index++]);
        Queue<Node> queue = new LinkedList<>();
        if(head != null){
            queue.add(head);
        }
        Node cur = null;
        while(!queue.isEmpty()){
            cur = queue.poll();
            cur.left = getNode(values[index++]);
            cur.right = getNode(values[index++]);
            if(cur.left != null){
                queue.add(cur.left);
            }
            if(cur.right != null){
                queue.add(cur.right);
            }
        }
        return head;
    }
    public static Node getNode(String value){
        if(value.equals("#")){
            return null;
        }
        return new Node(Integer.parseInt(value));
    }
}

直观打印二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class PrintTree {
    public static class Node{
        public int value;
        public Node left;
        public Node right;
        public Node(int v){
            value = v;
        }
    }
    public static void printTree(Node head){
        System.out.println("Binary Tree");
        printInOrder(head,0,"H",17);
        System.out.println();
    }

    /**
     * @param head 头节点
     * @param height 当前节点的层数
     * @param to 标识符: v代表父节点的右孩子  ^代表父节点的左孩子  H代表头节点
     * @param len 每层的宽度
     */
    public static void printInOrder(Node head, int height, String to, int len){
        if(head == null){
            return;
        }
        printInOrder(head.right, height + 1, "v", len );
        String val = to + head.value + to;
        int lenM = val.length();
        int lenL = (len - lenM) / 2;
        int lenR = len - lenM - lenL;
        val = getSpace(lenL) + val + getSpace(lenR);
        System.out.println(getSpace(height * len) + val);
        printInOrder(head.left,height + 1, "^", len);
    }
    public static String getSpace(int num) {
        StringBuilder res = new StringBuilder("");
        for(int i = 0; i < num; i++){
            res.append(" ");
        }
        return res.toString();
    }
}

后继结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class SuccessorNode {
    public static class Node{
        public int value;
        public Node left;
        public Node right;
        public Node parent;
        public Node(int v){
            value = v;
        }
    }

    /**
     * @param node 任意节点
     * @return 后继结点(中序遍历后当前节点的下一个节点)
     */
    public static Node getSuccessorNode(Node node){
        if(node == null){
            return null;
        }
        if(node.right != null){
            return getLeftMost(node.right);
        }else{
            Node parent = node.parent;
            while(parent != null && parent.right == node){
                node = parent;
                parent = node.parent;
            }
            return parent;
        }
    }
    public static Node getLeftMost(Node node){
        if(node == null){
            return null;
        }
        while(node.left != null){
            node = node.left;
        }
        return node;
    }
}

折纸问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * 请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折一次，压出折痕后展开。
 * 此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。
 * 如果从纸条的下边 向上方连续对折2次，压出折痕后展开，
 * 此时有3条折痕，从上到下依次是下折痕、下折痕、上折痕。
 * 给定一个输入参数N，代表纸条都从下边向上方连续对折N次，
 * 请从上到下打印所有折痕的方向。
 * 		例如：N=1时，打印
 * 		down
 * 		N=2时，打印：
 * 		down
 * 		down
 * 		up
 * 思路:
 *      给折痕标号,如:1 down 代表第1次对折,折出的折痕是下折痕
 *      多折几次会发现新的折痕总会出现在上一次对折时折痕的两侧
 *      且上侧为下折痕,下侧为上折痕
 *      这样就相当于一个二叉树,头节点是down,每个节点的左孩子都是down,右孩子都是up
 *      中序遍历这个二叉树的结果就是从上到下打印了所有折痕
 */
public class PaperFolding {
    /**
     * @param N 对折次数
     */
    public static void printAllFolds(int N){
        printProcess(1,N,true);
    }

    /**
     * 打印
     * @param i 当前层数
     * @param N 对折次数(总层数)
     * @param down true代表下折痕 false代表上折痕
     */
    private static void printProcess(int i, int N, boolean down) {
        if(i == N){
            return;
        }
        printProcess(i + 1, N, true);
        System.out.println(down ? "down" : "up");
        printProcess(i + 1, N, false);
    }
}

Morris

遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
public class Morris {
    static class Node {
        public int val;
        public Node left;
        public Node right;
        public Node(int v){
            val = v;
        }
    }

    /**
     * 1.先看有没有左树
     * 2.有左树的话,找到左树上最右节点
     * 3.如果左树最右节点指向空,让左树最右节点的右指针指向自己,然后当前指针向左移动
     * 4.如果左树最右节点指右指针向自己,改成指向null,然后当前指针向右树移动
     * 5.如果没有左树,直接向右树移动
     * 这种遍历方式,每个有左树的节点会经过两次,没有左树的节点会经过一次
     */
    public static void morris(Node head){
        if(head == null){
            return;
        }
        Node cur = head;
        Node mostRight = null;
        while(cur != null){
            mostRight = cur.left;
            if(mostRight != null){
                while(mostRight.right != null && mostRight.right != cur)
                mostRight = mostRight.right;
                if(mostRight.right == null){
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else{

                    mostRight.right = null;
                }
            }
            cur = cur.right;
        }
    }
    //先序
    public static void morrisPre(Node head){
        if(head == null){
            return;
        }
        Node cur = head;
        Node mostRight = null;
        while(cur != null){
            mostRight = cur.left;
            if(mostRight != null){
                while(mostRight.right != null && mostRight.right != cur)
                    mostRight = mostRight.right;
                if(mostRight.right == null){
                    System.out.println(cur.val);
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else{
                    mostRight.right = null;
                }
            } else{
                System.out.println(cur.val);
            }
            cur = cur.right;
        }
    }
    
    public static void morrisIn(Node head){
        if(head == null){
            return;
        }
        Node cur = head;
        Node mostRight = null;
        while(cur != null){
            mostRight = cur.left;
            if(mostRight != null){
                while(mostRight.right != null && mostRight.right != cur)
                    mostRight = mostRight.right;
                if(mostRight.right == null){
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else{

                    mostRight.right = null;
                }
            }
            System.out.println(cur.val);
            cur = cur.right;
        }
    }
    
    public static void morrisPos(Node head){
        if(head == null){
            return;
        }
        Node cur = head;
        Node mostRight = null;
        while(cur != null){
            mostRight = cur.left;
            if(mostRight != null){
                while(mostRight.right != null && mostRight.right != cur)
                    mostRight = mostRight.right;
                if(mostRight.right == null){
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else{
                    mostRight.right = null;
                    printRight(cur.left);
                }
            }
            cur = cur.right;
        }
        printRight(head);
    }
    //逆序打印以head为头的树的右边界
    public static void printRight(Node head){
        Node last = reverse(head);
        Node cur = last;
        while (cur != null){
            System.out.println(cur.val);
            cur = cur.right;
        }
        reverse(last);
    }
    /**
     * 翻转以head为头的链表
     * @return 翻转后最后一个节点
     */
    public static Node reverse(Node head){
        Node next = null;
        Node pre = null;
        while(head != null){
            next = head.right;
            head.right = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

是否为搜索二叉树BST

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public static boolean isBST(Node head){
        if(head == null){
            return true;
        }
        Node cur = head;
        Node mostRight = null;
        int preVal = Integer.MIN_VALUE;
        while(cur != null){
            mostRight = cur.left;
            if(mostRight != null){
                while(mostRight.right != null && mostRight.right != cur)
                    mostRight = mostRight.right;
                if(mostRight.right == null){
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else{
                    mostRight.right = null;
                }
            }
            if(cur.val <= preVal){
                return false;
            }
            preVal = cur.val;
            cur = cur.right;
        }
        return true;
    }

二叉树的递归套路

可以解决面试中绝大多数的二叉树问题尤其是树型dp问题

本质是利用递归遍历二叉树的便利性

  1. 假设以X节点为头，假设可以向X左树和X右树要任何信息
  2. 在上一步的假设下，讨论以X为头节点的树，得到答案的可能性
  3. 列出所有可能性后，确定到底需要向左树和右树要什么样的信息
  4. 把左树信息和右树信息求全集，就是任何一棵子树都需要返回的信息S
  5. 递归函数都返回S，每一棵子树都这么要求
  6. 写代码，在代码中考虑如何吧左树的信息和右树的信息整合出整棵树的信息

平衡二叉树

在一颗二叉树中每一个子树左树与右树的高度差不超过1

思路:

  • 左树是平衡树
  • 右树是平衡树
  • 左树和右树高度差不超过1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class IsBalanced {
    public static class Info{
        public boolean isBalanced;
        public int height;
        public Info(boolean b,int h){
            isBalanced = b;
            height = h;
        }
    }
    public static class Node{
        public int value;
        public Node left;
        public Node right;
        public Node(int v){
            value = v;
        }
    }
    public static boolean balance(Node head){
        return process(head).isBalanced;
    }
    public static Info process(Node X){
        if(X == null){
            return new Info(true,0);
        }
        Info leftInfo = process(X.left);
        Info rightInfo = process(X.right);
        int height = 1 + Math.max(leftInfo.height, rightInfo.height);
        //左树右树都平衡且高度差不超过1
        boolean balance = leftInfo.isBalanced
                && rightInfo.isBalanced
                && Math.abs(leftInfo.height - rightInfo.height) <= 1;
        return new Info(balance,height);
    }
}

节点最大距离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class MaxDistance {
    public static class Info{
        public int max;
        public int height;
        public  Info(int m,int h){
            max = m;
            height = h;
        }
    }
    public static class Node{
        public int value;
        public Node left;
        public Node right;
        public Node(int v){
            value = v;
        }
    }
    public static int maxDistance(Node head){
        return process(head).max;
    }
    public static Info process(Node X){
        if(X == null){
            return new Info(0,0);
        }
        Info leftInfo = process(X.left);
        Info rightInfo = process(X.right);
        int max = Math.max(Math.max(leftInfo.max, rightInfo.max),
                leftInfo.height + rightInfo.height + 1);
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        return new Info(max,height);
    }
}

最大二叉搜索子树

搜索二叉树BST：没有重复值的二叉树，任意节点的左树上每个节点的值比自己小，右树上每个节点的值比自己大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
public class MaxSubBST {
    public static class Node{
        public int value;
        public Node left;
        public Node right;
        public Node(int v){
            value = v;
        }
    }
    public static class Info{
        public boolean isBST;
        public int maxSubBSTSize;
        public int max;
        public int min;
        public Info(boolean is,int size, int mi,int ma){
            isBST = is;
            maxSubBSTSize = size;
            min = mi;
            max = ma;
        }
    }
    public static Info process(Node X){
        if(X == null){
            return null;
        }
        Info leftInfo = process(X.left);
        Info rightInfo = process(X.right);

        int max = X.value;
        int min = X.value;
        if(leftInfo != null){
            min = Math.min(min, leftInfo.min);
            max = Math.max(max, leftInfo.max);
        }
        if(rightInfo != null){
            min = Math.min(min, rightInfo.min);
            max = Math.max(max, rightInfo.max);
        }

        int maxSubBSTSize = 0;
        if(leftInfo != null){
            maxSubBSTSize = leftInfo.maxSubBSTSize;
        }
        if(rightInfo != null){
            maxSubBSTSize = Math.max(rightInfo.maxSubBSTSize,maxSubBSTSize);
        }

        boolean isBST = false;
        if(
                (leftInfo == null ? true : leftInfo.isBST)
                && (rightInfo == null ? true : rightInfo.isBST)
                && (leftInfo == null ? true : leftInfo.max < X.value)
                && (rightInfo == null ? true : rightInfo.min > X.value)
        ){
            maxSubBSTSize =
                    (leftInfo == null ? 0 : leftInfo.maxSubBSTSize)
                    + (rightInfo == null ? 0 : rightInfo.maxSubBSTSize)
                    + 1;
            isBST = true;
        }
        return new Info(isBST,maxSubBSTSize,min,max);
    }
}

派对的最大快乐值

公司里每个员工对于若干下级和唯一上级，每个员工都有一个快乐值

派对发请柬，被发到的人的下级一定不会来参加派对

求参加派对的员工的快乐值之和的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.ArrayList;
import java.util.List;

public class MaxHappy {
    public static class Employee {
        public int happy;
        public List<Employee> nexts;
        public Employee(int h){
            happy = h;
            nexts = new ArrayList<>();
        }
    }
    public static class Info{
        public int yes;
        public int no;
        public Info(int y, int n){
            yes = y;
            no = n;
        }
    }
    public static int maxHappy(Employee boss){
        Info res = process(boss);
        return Math.max(res.yes,res.no);
    }
    public static Info process(Employee X){
        if(X.nexts.isEmpty()){
            return new Info(X.happy,0);
        }
        int yes = X.happy;
        int no = 0;
        for(Employee next : X.nexts) {
            Info nextInfo = process(next);
            yes += nextInfo.no;
            no += Math.max(nextInfo.yes,nextInfo.no);
        }
        return new Info(yes,no);
    }
}

贪心算法

思路就是每一步都选最优解，整体就是最优解

贪心问题没有固定套路，比较考验数学能力

贪心策略往往是类似于自然智慧的，你只能靠举反例来证明它是错的，但你很难证明它是对的

对于贪心算法的学习主要以增加阅历和经验为主

图

Node

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.ArrayList;

public class Node {
    public int value;
    public int in;
    public int out;
    public ArrayList<Node> nexts;
    public ArrayList<Edge> edges;

    public Node(int v) {
        value = v;
        in = 0;
        out = 0;
        nexts = new ArrayList<>();
        edges = new ArrayList<>();
    }
}

Edge

1
2
3
4
5
6
7
8
9
10
11
public class Edge {
    public int weight;
    public Node from;
    public Node to;

    public Edge(int weight, Node from, Node to) {
        this.weight = weight;
        this.from = from;
        this.to = to;
    }
}

Graph

1
2
3
4
5
6
7
8
9
10
11
import java.util.HashMap;
import java.util.HashSet;

public class Graph {
    public HashMap<Integer, Node> nodes;
    public HashSet<Edge> edges;
    public Graph() {
        nodes = new HashMap<>();
        edges = new HashSet<>();
    }
}

转换器CreateGraph

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class CreateGraph {
    /**
     * 给一个三列的矩阵
     * 每一行代表一条边edge
     * 第一列代表权重
     * 第二列代表from
     * 第三列代表to
     * 建成Graph
     */
    public void createGraph(int[][] arr){
        Graph graph = new Graph();
        for(int i = 0; i < arr.length; i++){
            int weight = arr[i][0];
            Integer from = arr[i][1];
            Integer to = arr[i][2];
            if(!graph.nodes.containsKey(from)){
                graph.nodes.put(from,new Node(from));
            }
            if(!graph.nodes.containsKey(to)){
                graph.nodes.put(to,new Node(to));
            }
            Node fromNode = graph.nodes.get(from);
            Node toNode = graph.nodes.get(to);
            Edge newEdge = new Edge(weight,fromNode,toNode);
            fromNode.nexts.add(toNode);
            fromNode.out++;
            toNode.in++;
            fromNode.edges.add(newEdge);
            graph.edges.add(newEdge);
        }
    }
}

广度优先遍历BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

public class BFS {
    //宽度优先遍历
    public static void bfs (Node node){
        if(node == null){
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        HashSet<Node> set = new HashSet<>();//记录已经被遍历到的节点
        queue.add(node);
        set.add(node);
        while(!queue.isEmpty()){
            Node cur = queue.poll();
            //弹出就打印
            System.out.println(cur.value);//可以进行一系列操作,打印只是举个例子
            for(Node next : node.nexts){
                if(!set.contains(next)){
                    set.add(next);
                    queue.add(next);
                }
            }
        }

    }
}

深度优先遍历DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.HashSet;
import java.util.Stack;

public class DFS {
    //深度优先遍历
    public static void dfs(Node node) {
        if(node == null){
            return;
        }
        Stack<Node> stack = new Stack<>();
        HashSet<Node> set = new HashSet<>();
        stack.add(node);
        set.add(node);
        //加入就打印
        System.out.println(node.value);
        while(!stack.isEmpty()){
            Node cur = stack.pop();
            for(Node next : node.nexts){
                if(!set.contains(next)){
                    stack.push(cur);
                    stack.push(next);
                    set.add(next);
                    System.out.println(next.value);
                    break;
                }
            }
        }
    }
}

拓扑排序

有向无环图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.util.*;

public class TopologySort {
    //拓扑排序
    public static List<Node> topologySort(Graph graph) {
        //key:某一个node
        //value:剩余的入度
        HashMap<Node,Integer> inMap = new HashMap<>();
        //剩余入度为0的node才能进入这个队列
        Queue<Node> zeroInQueue = new LinkedList<>();

        for(Node node : graph.nodes.values()){
            inMap.put(node,node.in);
            if(node.in == 0){
                zeroInQueue.add(node);
            }
        }

        List<Node> result = new ArrayList<>();
        while(!zeroInQueue.isEmpty()){
            Node cur = zeroInQueue.poll();
            result.add(cur);
            for(Node next : cur.nexts){
                inMap.put(next,inMap.get(next) - 1);
                if(inMap.get(next) == 0){
                    zeroInQueue.add(next);
                }
            }
        }
        return result;
    }
}

最小生成树MST

Kruskal算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
import java.util.*;

public class Kruskal {
    //最小生成树MST

    //并查集
    public static class UnionFind {
        public HashMap<Node,Node> fatherMap;
        public HashMap<Node,Integer> sizeMap;
        public UnionFind() {
            fatherMap = new HashMap<>();
            sizeMap = new HashMap<>();
        }
        public void makeSets(Collection<Node> nodes) {
            fatherMap.clear();
            sizeMap.clear();
            for(Node node : nodes){
                fatherMap.put(node,node);
                sizeMap.put(node, 1);
            }
        }
        private Node findFather(Node n){
            Stack<Node> path = new Stack<>();
            while(n != fatherMap.get(n)){
                path.add(n);
                n = fatherMap.get(n);
            }
            while (!path.isEmpty()){
                fatherMap.put(path.pop(),n);
            }
            return n;
        }
        public boolean isSameSet(Node x, Node y){
            return findFather(x) == findFather(y);
        }
        public void union(Node x, Node y){
            if(x == null || y == null){
                return;
            }
            Node xHead = findFather(x);
            Node yHead = findFather(y);
            if(xHead != yHead){
                int xSetSize = sizeMap.get(xHead);
                int ySetSize = sizeMap.get(yHead);
                if(xSetSize >= ySetSize){
                    fatherMap.put(yHead,xHead);
                    sizeMap.put(xHead, xSetSize + ySetSize);
                    sizeMap.remove(yHead);
                }else {
                    fatherMap.put(xHead, yHead);
                    sizeMap.put(yHead, xSetSize + ySetSize);
                    sizeMap.remove(xHead);
                }
            }
        }
    }

    //比较器
    public static class EdgeComparator implements Comparator<Edge> {
        @Override
        public int compare(Edge o1, Edge o2) {
            return o1.weight - o2.weight;
        }
    }

    public static Set<Edge> kruskalMST(Graph graph) {
        UnionFind unionFind = new UnionFind();
        unionFind.makeSets(graph.nodes.values());
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
        priorityQueue.addAll(graph.edges);
        Set<Edge> result = new HashSet<>();
        while(!priorityQueue.isEmpty()){
            Edge edge = priorityQueue.poll();
            if(!unionFind.isSameSet(edge.from, edge.to)){
                result.add(edge);
                unionFind.union(edge.from, edge.to);
            }
        }
        return result;
    }
}

Prim算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.*;
public class Prim {
    //比较器
    public static class EdgeComparator implements Comparator<Edge> {
        @Override
        public int compare(Edge o1, Edge o2) {
            return o1.weight - o2.weight;
        }
    }

    public static Set<Edge> primMST(Graph graph) {
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
        HashSet<Node> nodeSet = new HashSet<>();
        HashSet<Edge> edgeSet = new HashSet<>();
        Set<Edge> result = new HashSet<>();
        for(Node node : graph.nodes.values()){//随便选一个点.防森林
            if (!nodeSet.contains(node)) {
                nodeSet.add(node);
                for (Edge edge : node.edges) {//加入每条边
                    if(!edgeSet.contains(edge)) {
                        edgeSet.add(edge);
                        priorityQueue.add(edge);
                    }
                }
                while(!priorityQueue.isEmpty()){
                    Edge edge = priorityQueue.poll();
                    Node toNode = edge.to;
                    if(!nodeSet.contains(toNode)){
                        nodeSet.add(toNode);
                        result.add(edge);
                        for (Edge nextEdge : toNode.edges) {
                            if(!edgeSet.contains(nextEdge)){
                                edgeSet.add(nextEdge);
                                priorityQueue.add(nextEdge);
                            }
                        }
                    }
                }
            }
        }
        return result;
    }
}

Dijkstra

dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

public class Dijkstra {
    public static HashMap<Node,Integer> dijkstra1(Node from) {
        HashMap<Node,Integer> distanceMap = new HashMap<>();
        distanceMap.put(from,0);
        HashSet<Node> selectedNodes = new HashSet<>();
        Node minNode = getMinDistanceAndUnselectedNode(distanceMap,selectedNodes);
        while(minNode != null) {
            int distance = distanceMap.get(minNode);
            for(Edge edge : minNode.edges){
                Node toNode = edge.to;
                if(!distanceMap.containsKey(toNode)){
                    distanceMap.put(toNode,distance + edge.weight);
                }else{
                    distanceMap.put(edge.to,Math.min(distanceMap.get(toNode),distance));
                }
            }
            selectedNodes.add(minNode);
            minNode = getMinDistanceAndUnselectedNode(distanceMap,selectedNodes);
        }
        return distanceMap;
    }

    private static Node getMinDistanceAndUnselectedNode(HashMap<Node, Integer> distanceMap, HashSet<Node> selectedNodes) {
        Node minNode = null;
        int minDistance = Integer.MAX_VALUE;

        for(Map.Entry<Node,Integer> entry : distanceMap.entrySet()){
            Node node = entry.getKey();
            int distance = entry.getValue();
            if(!selectedNodes.contains(node) && distance < minDistance) {
                minNode = node;
                minDistance = distance;
            }
        }
        return minNode;
    }
}

dijkstraPlus

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
import java.util.HashMap;

public class DijkstraPlus {
    public static class NodeRecord {
        public Node node;
        public int distance;
        public NodeRecord(Node node ,int distance){
            this.node = node;
            this.distance = distance;
        }
    }
    public static class NodeHeap {
        private Node[] nodes;
        private HashMap<Node,Integer> heapIndexMap;
        private HashMap<Node,Integer> distanceMap;
        private int size;

        public NodeHeap(int size) {
            nodes = new Node[size];
            heapIndexMap = new HashMap<>();
            distanceMap = new HashMap<>();
            size = 0;
        }
        public boolean isEmpty() {
            return size == 0;
        }

        private boolean isEntered(Node node) {
            return heapIndexMap.containsKey(node);
        }
        private boolean inHeap(Node node){
            return isEntered(node) && heapIndexMap.get(node) != -1;
        }
        private void swap(int index1,int index2){
            heapIndexMap.put(nodes[index1],index2);
            heapIndexMap.put(nodes[index2],index1);
            Node tmp = nodes[index1];
            nodes[index1] = nodes[index2];
            nodes[index2] = tmp;
        }
        private void insertHeapify(Node node, int index) {
            while(distanceMap.get(nodes[index]) < distanceMap.get(nodes[(index - 1) / 2])){
                swap(index,(index-1)/2);
                index = (index - 1)/2;
            }
        }
        private void heapify(int index, int size){
            int left = index * 2 + 1;
            while(left < size) {
                int smallest = left + 1 < size && distanceMap.get(nodes[left + 1]) < distanceMap.get(nodes[left])
                        ? left + 1
                        : left;
                smallest = distanceMap.get(nodes[smallest])
                        < distanceMap.get(nodes[index]) ? smallest : index;
                if(smallest == index) {
                    break;
                }
                swap(smallest,index);
                index = smallest;
                left = index * 2 + 1;
            }
        }
        public void addOrUpdateOrIgnore(Node node,int distance) {
            if(inHeap(node)){
                distanceMap.put(node, Math.min(distanceMap.get(node),distance));
                insertHeapify(node, heapIndexMap.get(node));
            }
            if(!isEntered(node)){
                nodes[size] = node;
                heapIndexMap.put(node,size);
                distanceMap.put(node,distance);
                insertHeapify(node,size++);
            }
        }
        public NodeRecord pop() {
            NodeRecord nodeRecord = new NodeRecord(nodes[0],distanceMap.get(nodes[0]));
            swap(0,size -1);
            heapIndexMap.put(nodes[size - 1], -1);
            distanceMap.remove(nodes[size - 1]);
            nodes[size - 1] = null;
            heapify(0, --size);
            return nodeRecord;
        }

    }
    public static HashMap<Node,Integer> dijkstra2(Node head,int size){
        NodeHeap nodeHeap = new NodeHeap(size);
        nodeHeap.addOrUpdateOrIgnore(head,0);
        HashMap<Node,Integer> result = new HashMap<>();
        while(!nodeHeap.isEmpty()){
            NodeRecord record = nodeHeap.pop();
            Node cur = record.node;
            int distance = record.distance;
            for(Edge edge : cur.edges) {
                nodeHeap.addOrUpdateOrIgnore(edge.to, edge.weight + distance);
            }
            result.put(cur,distance);
        }
        return result;
    }
}

其他

打表技巧

强迫症买苹果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class MinBags {
    /**
     * 小虎去买苹果，商店只提供两种类型的塑料袋，每种类型都有任意数量。
     * 1）能装下6个苹果的袋子
     * 2）能装下8个苹果的袋子
     * 小虎可以自由使用两种袋子来装苹果，但是小虎有强迫症，
     * 他要求自己使用的袋子数量必须最少，且使用的每个袋子必须装满，否则就不买了
     *
     * 给定一个正整数N，返回至少使用多少袋子。
     * 如果N无法让每个袋子装满，返回-1
     */

    //暴力方法
    public static int minBags(int N){
        int times = N / 8;
        while(times >= 0){
            if((N - times * 8) % 6 == 0){
                return times + (N - times * 8) / 6;
            }
            times--;
        }
        return -1;
    }
    
    //根据暴力方法打表找规律发现的O(1)的方法
    public static int minBagsAwesome(int N){
        if((N & 1) != 0){//奇数返回-1
            return -1;
        }
        if(N < 18){
            //打表发现小于18时，0返回0；6，8返回1；12，14，16返回2；其他都是-1；
            return N == 0 ? 0 :
                    (   N == 6
                     || N == 8)? 1 :
                            (   N == 12
                             || N == 14
                             || N == 16) ? 2 : -1;
        }
        //大于等于18时的规律
        return (N - 18) / 8 + 3;
    }
    public static void main(String[] args) {
        //打印0到100的结果找规律
        for( int i = 0; i <= 100; i++){
            System.out.println( i + " : " + minBags(i) );
        }
    }
}

谁会赢

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public class Graze {
    /**
     * 给定一个正整数N，表示N分青草统一放在仓库里
     * 有一只牛和一只羊，牛先吃，羊后吃，回合制吃草
     * 每次吃草的量必须是4的某次方
     * 谁先把草吃完，谁获胜
     * 假设牛羊都绝顶聪明，都想赢
     * 根据唯一的参数N，返回谁会赢
     */
    /**
     * 暴力方法
     * 用递归模拟所有可能性
     * @param N 草的数量
     * @return 本回合的动物会输还是会赢
     */
    public static boolean winner1(int N){
        if(N <=5){//小于等于5的所有情况
            return N != 2 && N != 5;
        }
        int base = 1;//吃草的份数
        while(base <= N){
            if(!winner1(N - base)){//if(羊输了)
                return true;
            }
            if(base > N/4){//防止溢出
                break;
            }
            base *= 4;
        }
        //上面递归全部完成后,羊一次都没输
        return false;
    }

    /**
     * 根据打表找到规律
     * @param N 草的数量
     * @return true代表牛赢,false代表牛输了
     */
    public static boolean winner2(int N){
        return N % 5 != 2 && N % 5 != 0;
    }
    public static void main(String[] args) {
        for(int i = 1; i <= 50; i ++){
            System.out.println(i + " : " + winner2(i));
        }
    }
}

连续正数和的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class ContinuousPositiveSum {
    /**
     * 定义一种数：可以表示成若干（数量>1）连续正数和的数
     * 给定一个参数N，返回是不是可以表示成若干连续正数和的数
     */
    public static boolean ifContinuousPositiveSum1(int n){
        for(int i = 1; i < n; i++){//从1开始累加
            int sum = 0;
            for(int j = i;sum < n; j ++){
                sum += j;
                if(sum == n){
                    return true;
                }
            }
        }
        return false;
    }
    //打表找规律发现只要n不是2的某次幂就可以
    public static boolean ifContinuousPositiveSum2(int n){
        return n != 1 && n % 2 != 0;
        //装逼写法
        //(n & (n - 1)) == 0 就代表n是2的某次方
        //return (n & (n - 1)) != 0;
    }
    public static void main(String[] args) {
        for(int i = 1; i <= 50; i ++){
            System.out.println(i + " : " + ifContinuousPositiveSum1(i));
        }
    }
}

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import java.util.HashMap;
import java.util.List;
import java.util.Stack;

public class DisjointSet {
    /**
     * 1. 有若干个样本a、b、c、d……类型假设是V
     * 2. 在并查集中一开始认为每个样本都在单独的集合里
     * 3. 用户可以在任何时候调用如下两个方法：
     *      boolean isSameSet(V x, V y):查询样本x和y是否属于一个集合
     *      void union(V x, V y):把x和y各自所在集合的所有样本合并成一个集合
     * 4. isSameSet和union方法的代价越低越好
     */
    public static class Node<V> {
        V value;
        public  Node(V v){
            value = v;
        }
    }
    public static class UnionSet<V> {
        public HashMap<V, Node<V>> nodes;//存放所有样本及其值
        public HashMap<Node<V>, Node<V>> parents;//存放每个样本及其父(每个集合的代表节点)
        public HashMap<Node<V>, Integer> sizeMap;//存放每个集合的代表节点和样本数
        public UnionSet(List<V> values){
            for(V value : values){
                Node<V> node = new Node<>(value);
                nodes.put(value, node);
                parents.put(node, node);
                sizeMap.put(node, 1);
            }
        }
        public Node<V> findFather(Node<V> cur) {
            Stack<Node<V>> path = new Stack<>();
            while(cur != parents.get(cur)) {
                path.push(cur);
                cur = parents.get(cur);
            }
            while(!path.isEmpty()){
                parents.put(path.pop(),cur);
            }
            return cur;
        }
        public boolean isSameSet(V x, V y) {
            if(!nodes.containsKey(x) || !nodes.containsKey(y)){
                return false;
            }
            return findFather(nodes.get(x)) == findFather(nodes.get(y));
        }
        public void union(V x, V y) {
            if(!nodes.containsKey(x) || !nodes.containsKey(y)){
                return;
            }
            Node<V> xHead = findFather(nodes.get(x));
            Node<V> yHead = findFather(nodes.get(y));
            if(xHead != yHead){
                int xSetSize = sizeMap.get(xHead);
                int ySetSize = sizeMap.get(yHead);
                if(xSetSize >= ySetSize){
                    parents.put(yHead,xHead);
                    sizeMap.put(xHead, xSetSize + ySetSize);
                    sizeMap.remove(yHead);
                }else{
                    parents.put(xHead,yHead);
                    sizeMap.put(yHead, xSetSize + ySetSize);
                    sizeMap.remove(xHead);
                }
            }
        }
    }
}

调整概率

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class Adjust {
    /**
     * 用Math.random()实现在[0, 1)区间
     * 出现[0,0.6]的概率为0.6的k次方
     */
    public static double random(int k){
        double max = 0;
        while(k > 0){
            double a = Math.random();
            if(max < a) {
                max = a;
            }
            k--;
        }
        return max;
    }
    public static void main(String[] args){
        int testTime = 1000000;
        double x = 0.6;
        int count = 0;
        int k = 2;
        for(int i = 0; i < testTime; i++){
            if(random(k) < x){
                count++;
            }
        }
        System.out.println((double)count / (double) testTime);
    }
}

丑数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
public class UglyNumber {
    /**
     * 丑数 I
     * 丑数 就是只包含质因数 2、3 和 5 的正整数。
     * 给你一个整数 n ，请你判断 n 是否为 丑数 。
     * 习惯上将1视作第一个丑数。
     * 力扣263
     */
    public boolean isUgly(int n) {
        if(n <= 0){
            return false;
        }
        while(n != 1){
            if(n / 5 * 5 == n){
                n /= 5;
            } else if(n / 3 * 3 == n){
                n /= 3;
            } else if(n / 2 * 2 == n){
                n >>= 1;
            } else {
                break;
            }
        }
        return n == 1;
    }

    /**
     * 丑数II
     * 给你一个整数 n ，请你找出并返回第 n 个 丑数 。
     * 丑数 就是只包含质因数 2、3 和/或 5 的正整数。
     * 1 通常被视为丑数。
     * 力扣264
     */
    public int nthUglyNumber(int n) {
        int[] ans = new int[n];
        ans[0] = 1;
        int i2 = 0;
        int i3 = 0;
        int i5 = 0;
        for(int i = 1; i < n; i++){
            ans[i] = Math.min(ans[i2] * 2, Math.min(ans[i3] * 3, ans[i5] * 5));
            if(ans[i] % 2 == 0){
                i2++;
            }
            if(ans[i] % 3 == 0){
                i3++;
            }
            if(ans[i] % 5 == 0){
                i5++;
            }
        }
        return ans[n - 1];
    }

    /**
     * 丑数III
     * 给你四个整数：n 、a 、b 、c ，请你设计一个算法来找出第 n 个丑数。
     * 丑数是可以被 a 或 b 或 c 整除的 正整数 。
     * 力扣1201
     */
    public int nthUglyNumber(int n, int a, int b, int c) {
        long ans = 0;
        long l = 0, r = (long) Math.min(a, Math.min(b, c)) * n;
        long ab = this.lcm(a, b);
        long ac = this.lcm(a, c);
        long bc = this.lcm(b, c);
        long abc = this.lcm(b, ac);
        while (l <= r) {
            long m = l + ((r - l) >> 1);//中间数
            //中间数包含N个丑数
            //(1)m/a表示m中有几个a的倍数
            //(2)m/ab表示m中有几个a和b的公倍数
            //(3)m/abc表示m中有几个a,b和c的公倍数
            //先把所有(1)加起来,因为有公倍数,所以会重复
            //再减去所有的(2)
            //减多了,再加上(3)
            long N = m / a + m / b + m / c - m / ab - m / ac - m / bc + m / abc;
            if (N < n) {
                l = m + 1;
                ans = l;
            } else {
                r = m - 1;
            }
        }
        return (int) ans;
    }
    //最大公约数
    private long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    //最小公倍数
    private long lcm(long a, long b) {
        return a * b / gcd(a, b);
    }


    /**
     * 超级丑数
     * 超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。
     * 给你一个整数 n 和一个整数数组 primes ，返回第 n 个 超级丑数 。
     * 题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。
     * 1是第一个超级丑数
     * 力扣313
     */
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] p = new int[primes.length];   // 对应primes[i]的指针位置
        int[] ans = new int[n];
        ans[0] = 1;
        int curr = 1;   // 当前计算第curr+1个丑数
        while (curr < n){
            //================求第cur个丑数======================
            int next = Integer.MAX_VALUE;
            int nextIdx = 0;
            for (int i=0; i<primes.length; ++i){
                int tmp = primes[i]*ans[p[i]];
                if (tmp > ans[curr-1] && tmp < next){
                    next = tmp;
                    nextIdx = i;
                }
            }
            //==================================================
            ans[curr] = next;
            ++curr;
            for (int i=0; i<primes.length; ++i){    // 如果满足条件，对应指针+1
                if (next == primes[i]*ans[p[i]]) ++p[i];
            }
        }
        return ans[n-1];
    }
}

跳表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
//力扣1206
class Skiplist {
    static final int MAX_LEVEL = 32;
    static final double P_FACTOR = 0.25;
    private SkiplistNode head;
    private int level;
    private Random random;

    public Skiplist() {
        this.head = new SkiplistNode(-1, MAX_LEVEL);
        this.level = 0;
        this.random = new Random();
    }

    public boolean search(int target) {
        SkiplistNode curr = this.head;
        for (int i = level - 1; i >= 0; i--) {
            /* 找到第 i 层小于且最接近 target 的元素*/
            while (curr.forward[i] != null && curr.forward[i].val < target) {
                curr = curr.forward[i];
            }
        }
        curr = curr.forward[0];
        /* 检测当前元素的值是否等于 target */
        if (curr != null && curr.val == target) {
            return true;
        } 
        return false;
    }

    public void add(int num) {
        SkiplistNode[] update = new SkiplistNode[MAX_LEVEL];
        Arrays.fill(update, head);
        SkiplistNode curr = this.head;
        for (int i = level - 1; i >= 0; i--) {
            /* 找到第 i 层小于且最接近 num 的元素*/
            while (curr.forward[i] != null && curr.forward[i].val < num) {
                curr = curr.forward[i];
            }
            update[i] = curr;
        }
        int lv = randomLevel();
        level = Math.max(level, lv);
        SkiplistNode newNode = new SkiplistNode(num, lv);
        for (int i = 0; i < lv; i++) {
            /* 对第 i 层的状态进行更新，将当前元素的 forward 指向新的节点 */
            newNode.forward[i] = update[i].forward[i];
            update[i].forward[i] = newNode;
        }
    }

    public boolean erase(int num) {
        SkiplistNode[] update = new SkiplistNode[MAX_LEVEL];
        SkiplistNode curr = this.head;
        for (int i = level - 1; i >= 0; i--) {
            /* 找到第 i 层小于且最接近 num 的元素*/
            while (curr.forward[i] != null && curr.forward[i].val < num) {
                curr = curr.forward[i];
            }
            update[i] = curr;
        }
        curr = curr.forward[0];
        /* 如果值不存在则返回 false */
        if (curr == null || curr.val != num) {
            return false;
        }
        for (int i = 0; i < level; i++) {
            if (update[i].forward[i] != curr) {
                break;
            }
            /* 对第 i 层的状态进行更新，将 forward 指向被删除节点的下一跳 */
            update[i].forward[i] = curr.forward[i];
        }
        /* 更新当前的 level */
        while (level > 1 && head.forward[level - 1] == null) {
            level--;
        }
        return true;
    }

    private int randomLevel() {
        int lv = 1;
        /* 随机生成 lv */
        while (random.nextDouble() < P_FACTOR && lv < MAX_LEVEL) {
            lv++;
        }
        return lv;
    }
}

class SkiplistNode {
    int val;
    SkiplistNode[] forward;

    public SkiplistNode(int val, int maxLevel) {
        this.val = val;
        this.forward = new SkiplistNode[maxLevel];
    }
}


/**
 * Your Skiplist object will be instantiated and called as such:
 * Skiplist obj = new Skiplist();
 * boolean param_1 = obj.search(target);
 * obj.add(num);
 * boolean param_3 = obj.erase(num);
 */