算法基础——左神算法

第一节 认识复杂度

1、时间复杂度

常数时间操作是指与数据量无关，总时间固定的操作。

时间复杂度表示算法流程中常数操作数量的指标，通常用O(f(N))表示。

评价算法好坏首先要看时间复杂度，然后再分析不同数据样本下的实际运行时间。

2、异或运算

2.1 基础知识

异或可以看成相同为1，不同为0；也可以看作无进位相加，有奇数个1则结果为1，有偶数个1则结果为0

1. 异或满足交换律和结合律：a^b=b^a (a^b)^c=a^(b^c)
2. 任何数与0异或不变：a^0=a
3. 任何数异或自己为零：a^a=0

举个例子，用异或运算交换两数的值

int a=甲;

int b=乙；

方法：

a=a^b     a=甲^乙 b=乙

b=a^b     a=甲^乙 b=甲^乙^乙=>甲

a=a^b     a=甲^乙^甲=>0^乙=>乙  b=甲

注意：用这种方式的前提是a和b指向不同的内存地址，否则异或会清零，比如我们在数组中使用时，注意i和j不能相同

2.2 例题

在一个数组arr[]中，出现了以下两种情况，如何快速求解（规定时间复杂度为O(N)，空间复杂度为O(1)）

1️⃣一个数组中，只有一种数出现了奇数次，其余数出现了偶数次，怎么找到该数？

2️⃣一个数组中，有两种数出现了奇数次，其余数出现了偶数次，怎么找到这两个数？

1️⃣声明一个变量eor初始化为0，然后依次遍历数组并于eor异或，最后得到的数即为所求数。为什么？因为我们之前提到异或满足交换律和结合律，遍历数组依次异或相当于与组中所有的数进行了异或，然后可调整顺序，将相同的数调整到一起异或为0，又因为相同的数为偶数个，所以除奇数次以外的数完全抵消了，最后相当于0与奇数次的数异或得到奇数次的数

核心代码：

public static void printOddTimesNum1(int[] arr) {
    int eor = 0;
    for (int cur : arr)
        eor = eor ^ cur;
    System.out.println(eor);
}

2️⃣ 对于第二问，我们可以声明两个变量来解决，第一个变量eor1遍历数组依次异或，根据交换律结合律。出现偶数次的数两两抵消，最后只会留下出现奇数次的数进行异或，假设这两个数为a和b，所以得到eor=a^b；第二个变量我们声明为eor2，由于a和b是不同的，所以a与b异或的结果eor!=0，因此eor中必有一位为1，显然该位为1是因为a、b中该位的值不同，我们假设该位为第i位，然后我们可以根据第i位是否为1将整个数组分为两部分，这样我们就将ab分开了，如下图所示：

然后我们用eor2只遍历数组中第i位为1的数进行异或，即上图中的左半部分，这样就会得到eor2=a（或者只遍历数组中第i位为0的数进行异或，这样会得到eor2=b）

经过上述的异或计算，我们得到了a异或b的值和其中一个值，然后将eor1和eor2进行异或就能得到另一个值：

eor1 = a ^ b
eor2 = a	//或 eor2 = b
eor1 ^ eor2 = a^(a^b) = b

核心代码：

public static void printOddTimes2Num2(int[] arr) {
    int eor1 = 0;
    int eor2 = 0;
    for (int i = 0; i < arr.length; i++) {
        eor1 ^= arr[i]; //得到eor1=a^b
    }
    int rightOne = eor1 & (~eor1 + 1);//提取出eor1最右边的1
    for (int cur : arr) {
        if ((cur & rightOne) == 1)
            eor2 ^= cur; //得到eor2=a或b
    }
    System.out.println("两数分别为:" + eor2 + "," + (eor1 ^ eor2));
}

其中rightOne = eor1 & (~eor1 + 1)是提取出a^b中最右边的那个一，这是常规操作，如下案例所示帮助理解：

eor1		1 0 1 0 1 1 1 1 0 0
~eor1		0 1 0 1 0 0 0 1 1 1
~eor+1		0 1 0 1 0 0 0 1 0 0
--------------------------------------
rightOne	0 0 0 0 0 0 0 1 0 0

3、剖析递归行为和递归行为时间复杂度的估算

用递归函数求解无序数组的最大值

核心代码：

public static void GetMax(int[] arr) {
    public static int getMax(int arr[]) {
        return process(arr, 0, arr.length - 1);
    }
    //在arr[L..R]范围上求最大值
    public static int process(int arr[], int L, int R) {
        if (L == R) {
            return arr[L];
        }
        int mid = L + ((R - L) >> 1); //中点
        int leftMax = process(arr, L, mid);
        int rigthMax = process(arr, mid + 1, R);
        return Math.max(leftMax, rightMax);
    }
}

Master公式的使用：T(N)=a*T(N/b)+O(N^d)

注：T(N)母问题的规模 a调用次数 T(N/b)子问题规模 O(N^d)除去子问题以后剩余调用次数

① log(b,a)>d --> 复杂度O(N^log(b,a)

② log(b,a)=d --> 复杂度O(N^d*logN)

③ log(b,a)<d --> 复杂度O(N^d)

第二节 常见排序算法

1、选择排序

核心思想：

• 在一组n个数中，第一轮从左往右在[0,n-1]范围内找出最小放在开始位置；

• 第二轮从左往右在[1,n-1]范围内找出最小放在第二的位置上；

• 以此类推，直到全部数组的数按顺序排列。

• 时间复杂度：O(n^2) 空间复杂度O(1)

核心代码：

public static void selectionSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }    // i 是寻找最小值的范围的左边界，因为每轮确定一个最小，所以左边界不断向后移
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        // i - N-1 范围找最小值的下标
        for (int j = i + 1; j < arr.length; j++) {
            minIndex = arr[j] < arr[minIndex] ? j : minIndex;
        }
        // 把最小的换到前面去
        swap(arr, i, minIndex);
    }
    //列表元素交换
 public static void swap(int arr[], int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}

2、冒泡排序

核心思想：

• 从数组中第一个数开始，每一个数都和后面的数比较，大的数往后换
• 每一趟都可以确定一个最大值（第二次冒泡的范围从 [0，n-1] 变成 [0，n-2] ）
• 以此类推，直到排序完成
• 时间复杂度是一个等差数列，所以是 O(n^2)
• 空间复杂度 O(1)

核心代码：

public static void bubbleSort(int[] arry) {
    if (arr == null || arr.length < 2) {
        return;       // 因为每轮确定一个最大值，所以 end 不断提前
    }
    for (int end = arr.length - 1; end > 0; end--) {
        // i - end 范围上选出一个最大值
        for (int i = 0; i < end; i++) {
            if (arr[i] > arr[i + 1]) {
                swap(arr, i, i + 1);
            }
        }

3、插入排序

核心思想:

• 数组的前部有一个初始大小为1的有序域，不断扩大，每次增大1
• 新进来的数与有序域内从后往前每个数依次比较，小的话就插入
• 类似于扑克牌整牌，每次抽牌后从后往前滑，遇到合适的位置就放进去
• 最好时间复杂度能达到 O(N)，即数组有序的情况下
• 最差时间复杂度 O(N^2)
• 空间复杂度 O(1)

核心代码：

public static void insertionSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
// i 是有序域右边界，不断扩大
    for (int i = 1; i < arr.length; i++) {
        // 从有序域右边界往左依次与右边界比较，选出最小作为新的右边界
        for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
            swap(arr, j, j + 1);
        }
    }
}

4、二分法

1️⃣在一个有序数组中，找某个数是否存在

2️⃣在一个有序数组中，找到>=某个数最左侧的位置

3️⃣ 在一个无序数组，任何相邻的两个数不相等，局部最小值问题：第一个元素只需与右相邻元素比较，最后一个元素只需与左相邻元素比较，中间要与两边比较;

核心思想：

1️⃣先找到数组中点记为M，如果num<M,则在目标数可能在M左边；如果num>M,则在目标数可能在M右边；如果num=M,则在目标数为M，存在。以此类推时间复杂度为Ο(log2n)

2️⃣

3️⃣ 先判断第一个是否为局部最小，是则return，否则再判断最后一个;若都不是，则中间必存在局部最小，先看中间数M是不是，不是则往比M小的相邻元素那边找，必能找到;

5、归并排序

核心思想：

• 整体就是一个简单递归，左边排好序，右边排好序，让其整体有序
• 让其整体有序的过程用了外排序的方法
• 利用master公式来求解时间复杂度
• 时间复杂度O(nlogn),额外空间复杂度O(n)

核心代码：

public class MergeSort {
    public static void mergeSort(int[] arr){
        if(arr == null || arr.length < 2) {
            return;
        }
        divide(arr,0,arr.length-1);
    }
 
    //分治  --> 采用递归的方式
    public static void divide(int[] arr,int L,int R){
        if(L == R){
            return;
        }
        int mid = L + ((R - L) >> 1);
        divide(arr,L,mid); //左侧递归
        divide(arr,mid+1,R); //右侧递归
        merge(arr,L,mid,R);
    }
 
    //将排好序的[L,M]和[M+1,R]合并成一个[L,R]的有序  --->  归并
    public static void merge(int[] arr,int L,int M,int R){
        //需要开辟一个新的空间用于暂时存放合并的数组，长度为R-L+1
        int[] temp = new int[R - L + 1];
        //需要指针分别指向三个数组的索引
        int i = 0;
        int L1 = L;//[L,M]数组的指针
        int R1 = M + 1;//[M+1,R]数组的指针
        //合并
        while (L1 <= M && R1 <= R){
            temp[i++] = arr[L1] < arr[R1] ? arr[L1++] : arr[R1++];//相等则先拷贝右侧的数据
        }//表明有一侧已经排完，还有一侧没有排完
        while (L1 <= M){ //[M+1,R]已经全部排完，只要把[L,M]剩余的依次放入就行
            temp[i++] = arr[L1++];
        }
        while(R1 <= R){  //[L,M]已经全部排完，只要把[M+1,R]剩余的依次放入就行
            temp[i++] = arr[R1++];
        }
        for(i = 0;i < temp.length;i++){//数组原来排序的范围arr[L,R],赋值的时候要注意不能从0开始
            arr[L+i] = temp[i];
        }
    }
}

小和问题

问题描述：

小和问题（在一个数组中，每一个数左边比当前数小的数累加起来，叫做数组的小和），求一个数组的小和。 --> 在归并排序的思想上进行添加修改

例子：[1,3,4,2,5]1左边比1小的数，没有；3左边比3小的数，1；4左边比4小的数，1，3；2左边比2小的数，1；5左边比5小的数，1，3，4，2；所以小和为：1+1+3+1+1+3+4+2=16。

核心代码：

public class XiaoHe {
    /**
     * 小和问题（在一个数组中，每一个数左边比当前数小的数累加起来，叫做数组的小和），求一个数组的小和。
     * 例子：[1,3,4,2,5]1左边比1小的数，没有；3左边比3小的数，1；4左边比4小的数，1，3；2左边比2小的数，1；
     * 5左边比5小的数，1，3，4，2；所以小和为：1+1+3+1+1+3+4+2=16。
     */
 
    //通过归并排序计算，在合并过程中比较计算 --> 时间复杂度O(nlogn)
    public static int smallSumSoulation2(int[] arr){
        if(arr == null || arr.length < 2) {
            return 0;
        }
        return divide(arr,0,arr.length-1);
    }
 
    //排序的过程，也要求小和
    public static int divide(int[] arr,int L,int R){
        if(L == R){
            return 0;
        }
        int mid = L + ((R - L) >> 1);
        return divide(arr,L,mid) + divide(arr,mid+1,R) + merge(arr,L,mid,R);
    }
 
    public static int merge(int[] arr,int L,int M,int R){
        int[] temp = new int[R - L + 1];
        int i = 0;
        int L1 = L;//[L,M]数组的指针
        int R1 = M + 1;//[M+1,R]数组的指针
        int result = 0;//小和
        while (L1 <= M && R1 <= R){ //均没有越界
            //相等则先拷贝右侧的数据,并且小和不加
            result += arr[L1] < arr[R1] ? (R - R1 + 1) * arr[L1] : 0;
            temp[i++] = arr[L1] < arr[R1] ? arr[L1++] : arr[R1++];
        }
        while (L1 <= M){
            temp[i++] = arr[L1++];
        }
        while(R1 <= R){
            temp[i++] = arr[R1++];
        }
        for(i = 0;i < temp.length;i++){
            arr[L+i] = temp[i];
        }
        return result;
    }
}

逆序对问题

问题描述：

在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，请打印所有逆序对

核心代码：

public class InversePairs {
    public static void main(String[] args) {
        int[] nums = {4, 3, 5, 0, 6};
        System.out.println(mergeSort(nums, 0, nums.length - 1));
    }    public static int mergeSort(int[] arr, int l, int r) {
        if (l == r) {
            return 0;
        }
        int mid = l + ( ( r - l ) >> 1 );
        return mergeSort(arr, l, mid) + mergeSort(arr, mid + 1, r) + merge(arr, l, mid,
                r);
    }    public static int merge(int[] arr, int l, int m, int r) {
        int[] help = new int[ r - l + 1];
        int res = 0;
        int i = 0;
        int index1 = l;
        int index2 = m + 1;
        while (index1 <= m &&
                index2 <= r) {
            // 此时左半部分右半部分都已排好序，若 arr[index1] > arr[index2]
            // index2 - (m + 1) + 1 代表右边有多少个数比 arr[index1] 小
            // 累加 index2 - m ，计算逆序对数量
            res += arr[index1] > arr[index2] ? index2 - m : 0;
            help[i++] = arr[index1] < arr[index2] ? arr[index1++] : arr[index2++];
        }
        while (index1 <= m) {
            help[i++] = arr[index1++];
        }
        while (index2 <= m) {
            help[i++] = arr[index2++];
        }
        for (i = 0; i < help.length; i++) {
            arr[l + i] = help[i];
        }
        return res;
    }
}

6、快速排序

荷兰国旗问题

问题描述：

• 荷兰国旗问题

• 给定一个数组arr，和一个数num，请把小于等于num的数放在数组的

• 左边，大于num的数放在数组的右边。

• 要求额外空间复杂度O(1)，时间复杂度O(N)

//printArray函数为打印未排序和排序后的数组
import static class_01.BubbleSort.printArray;

public class Flag {
    public static void flag(int[] arr, int num) {
        int less = -1;
        int more = arr.length;
        int cur = 0;
        while (cur < more) {
            if (arr[cur] < num) {
                swap(arr, cur++, ++less);
            } else if (arr[cur] > num) {
                swap(arr, cur, --more);
            } else {
                cur++;
            }
        }
    }

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

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

}

经典快排1.0

• 经典快排一次只搞定一个数，每次将初始的右侧数作为基准放在中间，<=的放左边，>的放右边；这样会导致左边会包含等于基准值的若干个数。接着返回基准值的左边部分和右边部分，再对左右部分进行上述操作，最终对数组完成排序。经典快排可能导致子区域划分极不平均。
• 当数据为{1,2，3, 4，5}时，每次将最后一个数作为基准，所需时间复杂度：O（N*N）

改进后的快排

• 进后的快排一次搞定一部分数（=x的那部分），总体来说，经典快排每次递归调用只有一个数不动，其他的需要进行二次甚至多次递归；而改进后的则是=x的一部分数全都不动，只需递归<或者>x的数即可。
• 为了避免经典快排可能导致子区域划分极不平均，改进后的快排则是随机抽取数组中的一个数作为基准值对数组进行排序。
• 时间复杂度O(N*logN)，空间复杂度O(logN);

核心代码：

import static class_01.BubbleSort.printArray;

public class QuickSort {
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    public static void quickSort(int[] arr, int L, int R) {
        if (L < R) {
            //先随机取出一个数放到最后
            swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
            int[] p = partition(arr, L, R);
            quickSort(arr, L, p[0] - 1);
            quickSort(arr, p[1] + 1, R);
        }
    }

    public static int[] partition(int[] arr, int l, int r) {
        int less = l - 1;
        int more = r;
        while (l < more) {
            if (arr[l] < arr[r]) {
                swap(arr, ++less, l++);
            } else if (arr[l] > arr[r]) {
                swap(arr, --more, l);
            } else {
                l++;
            }
        }
        swap(arr, more, r);
        return new int[] { less + 1, more };
    }

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

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

7、堆排序

堆在逻辑结构上是一颗完全二叉树

算法核心：

• 首先将数组进行heapInsert操作，将被数组变成一个大根堆

• 然后从数组中取出最大的那个数，与大根堆最后一个数做交换，出去最大的那个数，剩余元素进行heapify操作，是其剩余部分也转化成大根堆

• 依此执行上述步骤，直到取出所有元素时停止（heapSize等于零）

• 时间复杂度：O(N*logN)，不管是heapInsert操作还是heapify操作，保持堆结构不变最大需要调整二叉树的深度次，堆的深度LogN，从头到尾要依此获取大根堆的最大值，剩余部分heapify，因此时间复杂度数学上求长期期望得到为O(N*logN)

核心代码：

private static void heapSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    // 首先将数组变成大根堆
    // 方法一，O(N*logN)
    for (int i = 0; i < arr.length; i++) { // O(N)
        heapInsert(arr, i); // O(logN)
    }
    // 方法二，自底向上，逐步让数组变成大根堆O(N)
    // for (int i = arr.length - 1; i >= 0; i--) {
    //     heapify(arr, i, arr.length);
    // }

    int heapSize = arr.length;
    while (heapSize > 0) { // O(N)
        swap(arr, 0, --heapSize); // O(1)
        heapify(arr, 0, heapSize); // O(logN)
    }
}

// heapInsert
private static void heapInsert(int[] arr, int index) {
    // 当前节点和父节点进行比较，如果大于父节点，则进行交换，当前节点来到父节点，重复操作，直到于根节点比较完成才结束
    while (arr[index] > arr[(index - 1) / 2]) {
        swap(arr, index, (index - 1) / 2);
        index = (index - 1) / 2;
    }
}

// heapify
private static void heapify(int[] arr, int index, int heapSize) {
    // 判断是否有孩子，如果有判断此节点是否小于孩子节点，小于侧进行交换，当前节点来到较大的孩子节点位置，重复操作，直到此节点没有孩子节点或者比孩子节点数值大结束
    int left = index * 2 + 1;
    while (left < heapSize) {
        int maxIndex = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
        if (arr[index] >= arr[maxIndex]) {
            break;
        } else {
            swap(arr, index, maxIndex);
            index = maxIndex;
            left = index * 2 + 1;
        }
    }
}

8、计数排序

• 是一类不基于比较的排序
• 创建一个包含所有情况的一个数组
• 遍历给定的整个数组，在创建数组中找到其对应的位置，并且对其进行计数
• 等待数组遍历结束，将创建的数组从左到右遍历（不为空的进行输出），得到排序结果
• 时间复杂度：O(N) 额外空间复杂度：O(K)

9、基数排序（桶排序）

算法核心：

• 给定一个待排序的数组

• 首先找出数组中最大的那个数，并判断该数一共有几位，将不足此位数的其他元素，前面补0

• 准备十个桶，依此代表0~9

• 然后从将数组中的元素依此遍历，按照个位数字依此进桶，让后按顺序出桶（同一个桶里，先进的先出）

• 重复上述操作，依此比较十位、百位…直到最高位

• 最后出桶结束，数组就已经排好序了

核心代码：

// 思路
// 1.获取此数组中的最大数，并求出其位数（进桶出桶次数）
// 2.遍历最大位数次数（代表进行了位数次入桶和出桶）
// 3.使用特殊方式进行进桶和出桶操作

// 基数排序
public static void radixSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    radixSort(arr, 0, arr.length - 1, maxBits(arr));
}

// 求一个数组（十进制数）中最大数的位数
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 begin, int end, int digit) {
    final int radix = 10;
    int i = 0, j = 0;
    int[] count = new int[radix]; // 此数组用于记录各元素小于等于指定位上的数出现的次数，例如：当前是所处位数为十位，count[5]代表十位上小于等于6的元素一共出现了几次
    int[] bucket = new int[end - begin + 1]; // 辅助数组

    // 完成最大位数次入桶和出桶操作
    for (int d = 1; d <= digit; d++) {
        // 初始化count数组，计数都设为0
        for (i = 0; i < radix; i++) {
            count[i] = 0;
        }
        // （1）统计指定位上为i的元素出现的次数
        for (i = begin; i <= end; i++) {
            j = getDigit(arr[i], d);
            count[j]++;
        }
        // （2）优化count数组，表示为指定位上小于等于i的元素出现的次数
        for (i = 1; i < radix; i++) {
            count[i] = count[i] + count[i - 1];
        }
        // （3）数组各元素完成一次进桶
        for (i = end; i >= begin; i--) {
            j = getDigit(arr[i], d);
            bucket[count[j] - 1] = arr[i];
            count[j]--;
        }
        // （4）数组各元素完成一次进桶
        for (i = begin, j = 0; i <= end; i++, j++) {
            arr[i] = bucket[j];
        }
    }
}

// 获取指定位上的数
public static int getDigit(int x, int d) {
    return ((x / ((int) Math.pow(10, d - 1))) % 10);
}

10、排序算法的稳定性及其汇总

同样值的个体之间，如果不因为排序而改变相对次序，就是这个排序是有稳定性的；否则就没有。

不具备稳定性的排序：

选择排序、快速排序、堆排序

具备稳定性的排序：

冒泡排序、插入排序、归并排序、一切桶排序思想下的排序

目前没有找到时间复杂度O(N*logN)，额外空间复杂度O(1)，又稳定的排序。

算法汇总：

	时间复杂度	空间复杂度	稳定性
选择排序	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)	否

第三节 链表

1、哈希表的简单介绍

1）哈希表在使用层面上可以理解为一种集合结构

2）如果只有key，没有伴随数据value，可以使用HashSet结构(C++中叫UnOrderedSet)

3）如果既有key，又有伴随数据value，可以使用HashMap结构(C++中叫UnOrderedMap)

4）有无伴随数据，是HashMap和HashSet唯一的区别，底层的实际结构是一回事

5）使用哈希表增(put)、删(remove)、改(put)和查(get)的操作，可以认为时间复杂度为O(1)，但是常数时间比较大

6）放入哈希表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小

7）放入哈希表的东西，如果不是基础类型，内部按引用传递，内存占用是这个东西内存地址的大小

2、有序表的简单介绍

1）有序表在使用层面上可以理解为一种集合结构

2）如果只有key，没有伴随数据value，可以使用TreeSet结构(C++中叫OrderedSet)

3）如果既有key，又有伴随数据value，可以使用TreeMap结构(C++中叫OrderedMap)

4）有无伴随数据，是TreeSet和TreeMap唯一的区别，底层的实际结构是一回事

5）有序表和哈希表的区别是，有序表把key按照顺序组织起来，而哈希表完全不组织

5）红黑树、AVL树、size-balance-tree和跳表等都属于有序表结构，只是底层具体实现不同

6）放入有序表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小

7）放入有序表的东西，如果不是基础类型，必须提供比较器，内部按引用传递，内存占用是这个东西内存地址的大小

8）不管是什么底层具体实现，只要是有序表，都有以下固定的基本功能和固定的时间复杂度
有序表的固定操作

1）void put(K key, V value)：将一个（key，value）记录加入到表中，或者将key的记录更新成value。

2）V get(K key)：根据给定的key，查询value并返回。

3）void remove(K key)：移除key的记录。

4）boolean containsKey(K key)：询问是否有关于key的记录。

5）K firstKey()：返回所有键值的排序结果中，最左（最小）的那个。

6）K lastKey()：返回所有键值的排序结果中，最右（最大）的那个。

7）K floorKey(K key)：如果表中存入过key，返回key；否则返回所有键值的排序结果中， key的前一个。 返回<=key 的最大值

8）K ceilingKey(K key)：如果表中存入过key，返回key；否则返回所有键值的排序结果中，key的后一个。 返回>=key的最小值

以上所有操作时间复杂度都是O(logN)，N为有序表含有的记录数

3、链表

3.1 单链表

class Node<V>{ 
	V value; 
	Node next; 
}

由以上结构的节点依次连接起来所形成的链叫单链表结构。

3.2 双链表

由以上结构的节点依次连接起来所形成的链叫双链表结构。

单链表和双链表结构只需要给定一个头部节点head，就可以找到剩下的所有的节点。

class Node<V>{ 
	V value; 
	Node next; 
	Node last; 
}

4、反转单向和双向链表

问题描述：

分别实现反转单向链表和反转双向链表的函数， 如果链表长度为N，时间复杂度要求为O(N)，额外空间复杂度要求为O(1)

核心代码：

    //单向链表节点
   public static class Node {
      public int value;
      public Node next;

      public Node(int data) {
         this.value = data;
      }
   }

   public static Node myReverseList(Node head) {
      Node p = null;
      while(head != null) {
         Node t = head.next;
         head.next = p;
         p = head;
         head = t;
      }
      return p;
   }
	//双向链表节点
   public static class DoubleNode {
      public int value;
      public DoubleNode last;
      public DoubleNode next;

      public DoubleNode(int data) {
         this.value = data;
      }
   }

   public static DoubleNode myReverseList(DoubleNode head) {
      DoubleNode p = null;
      DoubleNode newHead = null;
      
//    while(head != null) {
//       DoubleNode tmp = head.next;
//       head.next = p;
//       head.last = tmp;
//       p = head;
//       head = tmp;
//    }
//    
//    return p;

      while(head != null) {
         DoubleNode t = head.next;
         head.next = p;
         p = head;
         head = t;
      }
      newHead = p;
      while(p != null) {
         DoubleNode t = p.last;
         p.last = head;
         head = p;
         p = t;
      }

      return newHead;
   }

5、打印两个有序链表的公共部分

问题描述：

给定两个有序链表的头指针head1和head2，打印两个链表的公共部分。如果两个链表的长度之和为N，时间复杂度要求为O(N)，额外空间复杂度要求为O(1)

核心代码：

public static class Node {
   public int value;
   public Node next;
   public Node(int data) {
      this.value = data;
   }
}

public static void myPrintCommonPart(Node head1, Node head2) {
   //有序链表，遍历，谁小谁往后走，
   //相等输出，然后一起走
   System.out.print("Common Part: ");
   for (; head1 != null && head2 != null ; ) {
      if (head1.value > head2.value) {
         head2 = head2.next;
      }else if (head1.value < head2.value){
         head1 = head1.next;
      }else {
         System.out.print(head1.value+"\t");
         head1 = head1.next;
         head2 = head2.next;
      }
   }
   System.out.println();
}

6、判断一个链表是否为回文结构

问题描述：

给定一个单链表的头节点head，请判断该链表是否为回文结构。1->2->1，返回true； 1->2->2->1，返回true；15->6->15，返回true； 1->2->3，返回false。如果链表长度为N，时间复杂度达到O(N)，额外空间复杂度达到O(1)。

核心代码：

public static boolean myIsPalindrome1(Node head) {
   //存到栈中，再读出来
   Stack<Node> nodes = new Stack<Node>();
   Node p = head;
   while(p != null) {
      nodes.push(p);
      p = p.next;
   }
   while(head.value == nodes.pop().value){
      if (head.next == null)
         return true;
      head = head.next;
   }
   return false;
}
// need n extra space
public static boolean isPalindrome1(Node head) {
   Stack<Node> stack = new Stack<Node>();
   Node cur = head;
   while (cur != null) {
      stack.push(cur);
      cur = cur.next;
   }
   while (head != null) {
      if (head.value != stack.pop().value) {
         return false;
      }
      head = head.next;
   }
   return true;
}

public static boolean myIsPalindrome2(Node head) {
   if (head == null || head.next == null) {
      return true;
   }
   //把一半存到栈中，再遍历后一半与栈.pop 作比较
   Stack<Node> nodes = new Stack<Node>();
   Node p1 = head;
   Node p2 = head;
   while(p2.next != null && p2.next.next != null) {
      p1 = p1.next;
      p2 = p2.next.next;
   }

   while(head != p1.next){
      nodes.push(head);
      head = head.next;
   }
   if (p2.next != null)   //当p2不是尾节点时，让p1后移一下，也就是总结点数是偶数的情况
      p1 = p1.next;
   //否则就不需要后移
   while(p1 != null) {
      if (p1.value != nodes.pop().value)
         return false;
      p1 = p1.next;
   }
   return true;
}
// need n/2 extra space
public static boolean isPalindrome2(Node head) {
   if (head == null || head.next == null) {
      return true;
   }
   Node right = head.next;
   Node cur = head;
   while (cur.next != null && cur.next.next != null) {
      right = right.next;
      cur = cur.next.next;
   }
   Stack<Node> stack = new Stack<Node>();
   //把后一半存到栈结构中
   while (right != null) {
      stack.push(right);
      right = right.next;
   }
   //用栈是否空作为条件，不需要分情况
   while (!stack.isEmpty()) {
      if (head.value != stack.pop().value) {
         return false;
      }
      head = head.next;
   }
   return true;
}

public static boolean myIsPalindrome3(Node head) {
   if (head == null || head.next == null) {
      return true;
   }
   Node p1 = head;
   Node p2 = head;
   while(p2.next != null && p2.next.next != null) {
      p1 = p1.next;
      p2 = p2.next.next;
   }
   //p2到了为尾，p1到了中间
   p2 = p1.next;
   Node p3 = null;
   while(p2 != null) {
      Node t = null;
      t = p2.next;
      p2.next = p3;
      p3 = p2;
      p2 = t;
   }
   p2 = p3;
   //p3 是后一段逆序的头节点
   boolean isPalindrome = true;
   while(p3!=null) {
      if (p3.value != head.value) {
         isPalindrome = false;
         break;
      }
      p3 = p3.next;
      head = head.next;
   }
   //要还原链表
   p3 = null;
   while(p2 != null) {
      Node t = null;
      t = p2.next;
      p2.next = p3;
      p3 = p2;
      p2 = t;
   }
   //p3 后一段的头
   p1.next = p3;
   return isPalindrome;
}

// need O(1) extra space
public static boolean isPalindrome3(Node head) {
   if (head == null || head.next == null) {
      return true;
   }
   Node n1 = head;
   Node n2 = head;
   while (n2.next != null && n2.next.next != null) { // find mid node
      n1 = n1.next; // n1 -> mid
      n2 = n2.next.next; // n2 -> end
   }
   n2 = n1.next; // n2 -> right part first node
   n1.next = null; // mid.next -> null
   Node n3 = null;
   while (n2 != null) { // right part convert
      n3 = n2.next; // n3 -> save next node
      n2.next = n1; // next of right node convert
      n1 = n2; // n1 move
      n2 = n3; // n2 move
   }
   n3 = n1; // n3 -> save last node
   n2 = head;// n2 -> left first node
   boolean res = true;
   while (n1 != null && n2 != null) { // check palindrome
      if (n1.value != n2.value) {
         res = false;
         break;
      }
      n1 = n1.next; // left to mid
      n2 = n2.next; // right to mid
   }
   n1 = n3.next;
   n3.next = null;
   while (n1 != null) { // recover list
      n2 = n1.next;
      n1.next = n3;
      n3 = n1;
      n1 = n2;
   }
   return res;
}

7、两个单链表相交的一系列问题

问题描述：

给定两个可能有环也可能无环的单链表，头节点head1和head2。请实现一个函数，如果两个链表相交，请返回相交的 第一个节点。如果不相交，返回null。如果两个链表长度之和为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)。

核心代码：

//分为都有环和都无环两种情况
public static Node myGetIntersectNode(Node head1, Node head2) {
   if (head1 == null || head2 == null)
      return null;
   Node loop1 = myGetLoopNode(head1);
   Node loop2 = myGetLoopNode(head2);

   if (loop1 == null && loop2 == null) {
      return myNoLoop(head1, head2);
   }else if (loop1 != null && loop2 !=null){
      return myBothLoop(head1, loop1, head2, loop2);
   }
   return null;

}
//找入环节点
public static Node myGetLoopNode(Node head) {
   if (head == null || head.next == null || head.next.next == null)
      return null;
   Node slow = head;
   Node fast = head.next;
   while (fast != slow && fast != null) {
      slow = slow.next;
      fast = fast.next == null ? null : fast.next.next;
   }
   if (fast == null)
      return null;
   fast = null;
   while (fast!=slow){
      fast = fast == null ? head : fast.next;
      slow = slow.next;
   }
   return fast;
}
//都无环的情况
public static Node myNoLoop(Node head1, Node head2) {
   Node p1 = head1;
   Node p2 = head2;
   int s1 = 0;
   int s2 = 0;
   int ds = 0;
   while(p1.next != null) {
      p1 = p1.next;
      s1++;
   }
   while(p2.next != null) {
      p2 = p2.next;
      s2++;
   }
   if (p1 != p2)  // 尾节点不一样，直接返回null
      return null;
   ds = Math.abs(s1 - s2);
   p1 = head1;
   p2 = head2;
   if (s1 >= s2){
      while(ds > 0){
         p1 = p1.next;
         ds--;
      }
   }else {
      while(ds > 0){
         p2 = p2.next;
         ds--;
      }
   }
   while (p1 != p2){
      p1 = p1.next;
      p2 = p2.next;
   }
   return p1;
}
//都有环的情况
public static Node myBothLoop(Node head1, Node loop1, Node head2, Node loop2) {
   if (loop1 == loop2) {
      Node p1 = head1;
      Node p2 = head2;
      int s1 = 0;
      int s2 = 0;
      int ds = 0;
      while (p1 != loop1) {
         p1 = p1.next;
         s1++;
      }
      while (p2 != loop1) {
         p2 = p2.next;
         s2++;
      }
      ds = Math.abs(s1 - s2);
      p1 = head1;
      p2 = head2;
      if (s1 >= s2) {
         while (ds > 0) {
            p1 = p1.next;
            ds--;
         }
      } else {
         while (ds > 0) {
            p2 = p2.next;
            ds--;
         }
      }
      while (p1 != p2) {
         p1 = p1.next;
         p2 = p2.next;
      }
      return p1;
   }else {
      Node p1 = loop1;
      while (p1 != loop2){
         p1 = p1.next;
         if (p1 == loop1)
            return null;
      }
      return loop1;
   }

}

第四节 二叉树

1、二叉树结构

class Node<V>{ 
 V value; 
 Node left; 
 Node right; 
}

2、递归实现先、中、后序遍历

public static class Node {
   public int value;
   public Node left;
   public Node right;

   public Node(int data) {
      this.value = data;
   }
}
/**
 *              1
 *        2           3
 *     4     5     6     7
 * 递归序：    1->2->4->4->4->2->5->5->5->2->1->3->6->6->6->3->7->7->7->3->1
 * @param head
 */
public static void myPreOrderRecur(Node head) {
   if (head == null) {
      return;
   }
   System.out.print(head.value + "\t");
   myPreOrderRecur(head.left);
   myPreOrderRecur(head.right);
}
public static void myInOrderRecur(Node head) {
   if (head == null) {
      return;
   }
   myPreOrderRecur(head.left);
   System.out.print(head.value + "\t");
   myPreOrderRecur(head.right);
}
public static void myPosOrderRecur(Node head) {
   if (head == null) {
      return;
   }
   myPreOrderRecur(head.left);
   myPreOrderRecur(head.right);
   System.out.print(head.value + "\t");
}

3、非递归实现先序遍历

算法核心：

• 首先申请一个新的栈，记为stack；
• 将头结点head压入stack中；
• 每次从stack中弹出栈顶节点，记为cur，然后打印cur值，如果cur右孩子不为空，则将右孩子压入栈中；如果cur的左孩子不为空，将其压入stack中；
• 重复步骤3，直到stack为空.

核心代码：

public static void myPreOrderUnRecur(Node head) {
   if (head == null) {
      return;
   }
   Stack<Node> stack = new Stack<>();
   stack.push(head);
   while(!stack.isEmpty()) {
      Node cur = stack.pop();
      System.out.print(cur.value);
      //先压右孩子，再压左孩子--->出的顺序就是 先左->后右
      if (cur.right != null) {
         stack.push(cur.right);
      }
      if (cur.left != null) {
         stack.push(cur.left);
      }
   }
   System.out.println();
}

4、非递归实现中序遍历

算法核心：

• 申请一个新栈，记为stack，申请一个变量cur，初始时令cur为头节点；

• 先把cur节点压入栈中，对以cur节点为头的整棵子树来说，依次把整棵树的左子树压入栈中，即不断令cur=cur.left，然后重复步骤2；

• 不断重复步骤2，直到发现cur为空，此时从stack中弹出一个节点记为node，打印node的值，并让cur = node.right，然后继续重复步骤2；

• 当stack为空并且cur为空时结束。

核心代码：

public static void myInOrderUnRecur(Node head) {
   if (head == null) {
      return;
   }
   Stack<Node> stack = new Stack<>();
   Node cur = head;
   while(!stack.isEmpty() || cur != null) {
      while (cur != null) {
         stack.push(cur);
         cur = cur.left;
      }
      cur = stack.pop();
      System.out.print(cur.value + "\t");
      cur = cur.right;
   }
   System.out.println();
}

5、非递归实现后序遍历

算法核心：

• 申请两个栈stack1，stack2，然后将头结点压入stack1中；

• 从stack1中弹出的节点记为cur，然后先把cur的左孩子压入stack1中，再把cur的右孩子压入stack1中；

• 在整个过程中，每一个从stack1中弹出的节点都放在第二个栈stack2中；

• 不断重复步骤2和步骤3，直到stack1为空，过程停止；

• 从stack2中依次弹出节点并打印，打印的顺序就是后序遍历的顺序；

核心代码：

public static void myPosOrderUnRecurTwoStack(Node head) {
   if (head == null) {
      return;
   }
   Stack<Node> stack1 = new Stack<>();
   Stack<Node> stack2 = new Stack<>();
   stack1.push(head);
   while(!stack1.isEmpty()) {
      Node cur = stack1.pop();
      stack2.push(cur);
      if (cur.left != null) {
         stack1.push(cur.left);
      }
      if (cur.right != null) {
         stack1.push(cur.right);
      }
   }
   while (!stack2.isEmpty()) {
      System.out.print(stack2.pop().value + "\t");
   }
   System.out.println();
}

6、层序遍历

算法核心：

• 首先申请一个新的队列，记为queue；
• 将头结点head压入queue中；
• 每次从queue中出队，记为node，然后打印node值，如果node左孩子不为空，则将左孩子入队；如果node的右孩子不为空，则将右孩子入队；
• 重复步骤3，直到queue为空。

核心代码：

public static void LevelOrder(Node head) {
   if (head == null)
      return;
   Queue<Node> queue = new LinkedList<Node>();
   queue.add(head);
   while (!queue.isEmpty()) {
      head = queue.poll();
      System.out.print(head.value + "\t");
      if (head.left != null) {
         queue.add(head.left);
      }
      if (head.right != null) {
         queue.add(head.right);
      }
   }
   System.out.println();
}

7、统计一棵二叉树的最大宽度

核心代码：

//使用hashmap的方法
public static int getMaxWidthWithMap(Node head) {
   if (head == null) {
      return 0;
   }
   int curWidth = 0;
   int maxWidth = 0;
   int curLevel = 1;
   HashMap<Node, Integer> levelMap = new HashMap<>();
   Queue<Node> queue = new LinkedList<Node>();
   queue.add(head);
   levelMap.put(head, 1);
   while (!queue.isEmpty()) {
      head = queue.poll();
      if (head.left != null) {
         queue.add(head.left);
         levelMap.put( head.left, levelMap.get(head) + 1);
      }
      if (head.right != null) {
         queue.add(head.right);
         levelMap.put( head.right, levelMap.get(head) + 1);
      }
      if (levelMap.get(head) > curLevel) {   //结算上一层的宽度
         maxWidth = Math.max(maxWidth, curWidth);
         curWidth = 1;
         curLevel = levelMap.get(head);
      }else {
         curWidth++;
      }
   }
   //最后要再结算一次，（最后一层）
   maxWidth = Math.max(maxWidth, curWidth);
   return maxWidth;
}

8、二叉树的相关概念及其实现判断

    如何判断一颗二叉树是否是搜索二叉树？

    如何判断一颗二叉树是完全二叉树？

    如何判断一颗二叉树是否是满二叉树？

    如何判断一颗二叉树是否是平衡二叉树？（二叉树题目套路）

1️⃣

//递归方式中序遍历实现
public static int preValue = Integer.MIN_VALUE;
public static boolean myCheckBSTRecur(Node head) {
   if (head == null) {
      return true;
   }
   if (!myCheckBSTRecur(head.left)) {
      return false;
   }
   if (preValue >= head.value) {
      return false;
   }else {
      preValue = head.value;
   }
   return myCheckBSTRecur(head.right);
}

//非递归中序遍历实现
public static boolean checkBSTUnRecur(Node head) {
   if (head == null) {
      return true;
   }
   int preValue = Integer.MIN_VALUE;
   Stack<Node> stack = new Stack<Node>();
   while (!stack.isEmpty() || head != null) {
      if (head != null) {
         stack.push(head);
         head = head.left;
      } else {
         head = stack.pop();
         if (head.value <= preValue) {
            return false;
         }else {
            preValue = head.value;
         }
         head = head.right;
      }
   }
   return true;
}

    //使用递归套路解决
   public static class ReturnData{
      public boolean isBST;
      public int max;
      public int min;

      public ReturnData(boolean isBST, int max, int min) {
         this.isBST = isBST;
         this.max = max;
         this.min = min;
      }
   }
   public static ReturnData process(Node head) {
      if (head == null) {
         return null;
      }
      ReturnData leftData = process(head.left);
      ReturnData rightData = process(head.right);
      //先令min 和max 都等于自己
      //==========这部分可以优化去掉============
      int min = head.value;
      int max = head.value;
      if (leftData != null) {
         min = Math.min(min, leftData.min);
         max = Math.max(max, leftData.max);
      }
      if (rightData != null) {
         min = Math.min(min, rightData.min);
         max = Math.max(max, rightData.max);
      }
      //=====================================
      boolean isBST = true;  //初始默认它是搜索二叉树，出现不满足的情况就置为false
      if (leftData != null && (!leftData.isBST || leftData.max > head.value) ) {
         isBST = false;
      }
      if (rightData != null && (!rightData.isBST || rightData.min < head.value) ) {
         isBST = false;
      }
      //另一种判断方式，初始为false
      //只有当left.max < value < right.min 时，才置为 true
//    boolean isBST = false;
//    if (
//          (leftData!=null ? (leftData.isBST && leftData.max < x.value) : true)
//                &&
//                (rightData!=null ? (rightData.isBST && rightData.min > x.value) : true)
//    ) {
//       isBST = true;
//    }
      //如果当前树是搜索二叉树的话，当前树的最大值就是右最大值，最小值就是左最小值
      //如果不是的话，isBST就是false，最大最小值也就无所谓了
      return new ReturnData(isBST,rightData.max,leftData.min);
   }

2️⃣

   	//判断是否是完全二叉树
	public static boolean myIsCBT(Node head) {
		if (head == null) {
			return true;
		}
		Queue<Node> queue = new LinkedList<>();
		queue.add(head);
		boolean beginLeaf = false;
		while(!queue.isEmpty()) {
			head = queue.poll();
			if (head.right != null && head.left == null) {    //有右孩子，无左孩子--->一定不是
				return false;
			}
			if (beginLeaf && head.left != null) {    //叶子节点已经开始，它的左孩子必须是空
				return false;
			}
			if (head.left != null) {
				queue.add(head.left);
			}
			if (head.right != null) {
				queue.add(head.right);
			}else {	//右孩子为空，说明叶子节点开始了
				beginLeaf = true;
			}
		}
		return true;
	}
  

3️⃣

 //是否是满二叉树
   public static boolean isFT(Node head) {
      if (head == null) {
         return true;
      }
      ReturnType data = process(head);
      if (data.nodeNums == (1 << data.height ) - 1 )
         return true;
      return false;
      //==========process2==========
//    return  process2(head) != null;
   }
   public static class ReturnType {
      public int nodeNums;
      public int height;

      public ReturnType(int nodeNums, int height) {
         this.nodeNums = nodeNums;
         this.height = height;
      }
   }
   public static ReturnType process(Node head) {
      if (head == null) {
         return new ReturnType(0,0);
      }
      ReturnType leftData = process(head.left);
      ReturnType rightData = process(head.right);
      return new ReturnType(leftData.nodeNums + rightData.nodeNums + 1,
            Math.max(leftData.height, rightData.height) + 1);
   }	
   public static ReturnType process2(Node head) {
      if (head == null) {
         return new ReturnType(0,0);
      }
      ReturnType leftData = process(head.left);
      ReturnType rightData = process(head.right);
      if (leftData == null || rightData == null) {
         return null;
      }
      if (leftData.height != rightData.height || leftData.nodeNums != rightData.nodeNums){
         return null;
      }
      return new ReturnType(leftData.nodeNums + rightData.nodeNums + 1,
            Math.max(leftData.height, rightData.height) + 1);
   }

4️⃣

//判断是否是平衡二叉树
public static boolean isBalanced(Node head) {
   return process(head).isBalanced;
}
public static class ReturnType {
   public boolean isBalanced;	//是否平衡
   public int height;	//高度

   public ReturnType(boolean isB, int hei) {
      isBalanced = isB;
      height = hei;
   }
}
public static ReturnType myProcess(Node head) {
   if (head == null) {
      return new ReturnType(true, 0);
   }
   ReturnType leftData = process(head.left);
   ReturnType rightData = process(head.right);

   boolean isBalanced = true;
   int height = 0;
   if (!leftData.isBalanced || !rightData.isBalanced || Math.abs(leftData.height - rightData.height) > 1) {
      isBalanced = false;
   }
   height = Math.max(leftData.height, rightData.height);

   return new ReturnType(isBalanced,height);
}
public static ReturnType process(Node x) {
   if (x == null) {
      return new ReturnType(true, 0);
   }
   ReturnType leftData = process(x.left);
   ReturnType rightData = process(x.right);
    
   int height = Math.max(leftData.height, rightData.height);
   boolean isBalanced = leftData.isBalanced && rightData.isBalanced
         && Math.abs(leftData.height - rightData.height) < 2;
   
    return new ReturnType(isBalanced, height);
}

9、给定两个二叉树的节点node1和node2，找到他们的最低公共祖先节点

//递归方式找两个节点的最低公共祖先，
//利用左右子树返回的信息判断o1，o2是分散在两棵树上，还是在其中一棵树上
public static Node myLowestAncestor(Node head, Node o1, Node o2) {
   if (head == null || head == o1 || head == o2) {
      return head;
   }
   Node left = myLowestAncestor(head.left, o1, o2);
   Node right = myLowestAncestor(head.right, o1, o2);
   if (left != null && right != null) {
      return head;
   }
   return left == null ? right : left;
}

10、在二叉树中找到一个节点的后继节点

题目描述：

现在有一种新的二叉树节点类型如下:

public class Node { 
 public int value; 
 public Node left; 
 public Node right; 
 public Node parent;

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

该结构比普通二叉树节点结构多了一个指向父节点的parent指针。

假设有一棵Node类型的节点组成的二叉树，树中每个节点的parent指针都正确地指向自己的父节点，头节点的parent指向null。

只给一个在二叉树中的某个节点node，请实现返回node的后继节点的函数。

在二叉树的中序遍历的序列中， node的下一个节点叫作node的后继节点。

    public static Node myGetSuccessorNode(Node node) {
      if (node == null) {
         return node;
      }
      //情况1：有右树，它的后继就是右树的最左节点
      if (node.right != null) {
         return getLeftMost(node.right);
      } else {
      //情况2：没有右树，他的后继就是自己作为左子树最右节点的头节点
         while (node.parent != null && node != node.parent.left){
            node = node.parent;
         }
         return node.parent;
//       Node parent = node.parent;
//       while (parent != null && node != parent.left) {
//          node = parent;
//          parent = node.parent;
//       }
//       return parent;
      }
   }

	public static Node getLeftMost(Node node) {
		if (node == null) {
			return node;
		}
		while (node.left != null) {
			node = node.left;
		}
		return node;
	}

11、二叉树的序列化和反序列化

就是内存里的一棵树如何变成字符串形式，又如何从字符串形式变成内存里的树

如何判断一颗二叉树是不是另一棵二叉树的子树？

//前序序列化
public static String serialByPre(Node head) {
   if (head == null) {
      return "#!";
   }
   String res = head.value + "!";
   res += serialByPre(head.left);
   res += serialByPre(head.right);
   return res;
}
//前序反序列化
public static Node reconByPreString(String preStr) {
   String[] values = preStr.split("!");
   Queue<String> queue = new LinkedList<String>();
   for (int i = 0; i != values.length; i++) {
      queue.offer(values[i]);
   }
   return reconPreOrder(queue);
}
public static Node reconPreOrder(Queue<String> queue) {
   String value = queue.poll();
   if (value.equals("#")) {
      return null;
   }
   Node head = new Node(Integer.valueOf(value));
   head.left = reconPreOrder(queue);
   head.right = reconPreOrder(queue);
   return head;
}

//中序序列化
public static String serialByIn(Node head) {
   if (head == null) {
      return "#!";
   }
   String res = "";
   res += serialByIn(head.left);
   res += head.value + "!";
   res += serialByIn(head.right);
   return res;
}
//无法恢复，递归过程丢失根节点信息
public static Node reconInOrder(Queue<String> queue) {
   return null;
}
//后序序列化
public static String serialByPos(Node head) {
   if (head == null) {
      return "#!";
   }
   String res = "";
   res += serialByPos(head.left);
   res += serialByPos(head.right);
   res += head.value + "!";
   return res;
}
//后序反序列化
public static Node reconByPosString(String preStr) {
	String[] values = preStr.split("!");
	Queue<String> queue = new LinkedList<String>();
    //逆序存到队列中，队首元素就是根节点的值
	for (int i = values.length - 1; i != -1; i--) {
		queue.offer(values[i]);
	}
	return reconPosOrder(queue);
}
public static Node reconPosOrder(Queue<String> queue) {
	String value = queue.poll();
	if (value.equals("#")) {
		return null;
	}
	Node head = new Node(Integer.valueOf(value));
	head.right = reconPosOrder(queue);
	head.left = reconPosOrder(queue);
	return head;
}

//层序序列化
public static String mySerialByLevel(Node head) {
   if (head == null) {
      return "#!";
   }
   String res = head.value + "!";
   Queue<Node> queue = new LinkedList<>();
   queue.add(head);
   while(!queue.isEmpty()) {
      head = queue.poll();
      if (head.left != null) {
         res += head.left.value + "!";
         queue.add(head.left);
      } else {
         res += "#!";   
      }
      if (head.right != null) {
         res += head.right.value + "!";
         queue.add(head.right);
      } else {
         res += "#!";
      }
   }
   return res;
}
//层序反序列化
public static Node myReconByLevelString(String levelStr) {
   String[] values = levelStr.split("!");
   int index = 0;
   if (values[index].equals("#")){
      return null;
   }
   Queue<Node> queue = new LinkedList<Node>();
   Node head = new Node(Integer.valueOf(values[index]));
   queue.add(head);
   while(!queue.isEmpty()) {
      Node cur = queue.poll();
      cur.left = values[++index].equals("#") ? null : new Node(Integer.valueOf(values[index]));
      cur.right = values[++index].equals("#") ? null : new Node(Integer.valueOf(values[index]));
      if (cur.left != null) {
         queue.add(cur.left);
      }
      if (cur.right != null) {
         queue.add(cur.right);
      }
   }
   return head;
}

12、折纸问题

问题描述：

请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。

此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。

如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。

给定一个输入参数N，代表纸条都从下边向上方连续对折N次。

请从上到下打印所有折痕的方向。

例如:N=1时，打印: down N=2时，打印: down down up

public static void printAllFolds(int N) {
   printProcess(1, N, true);
}
public static void myPrintAllFolds(int N) {
   myPrintProcess(1, N, true);
}
//i记录当前深度
//N记录对折次数，也就是二叉树的最大深度
//down用来记录当前节点的值，在递归过程就可以实现输出，无需先构建二叉树，再进行中序遍历
public static void myPrintProcess(int i, int N, boolean down) {
   if (i > N){
      return;
   }
   myPrintProcess(i + 1, N, true);
   System.out.println(down ? "凹" : "凸");
   myPrintProcess(i + 1, N, false);
}
public 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);
}

第五节 图

1、 图的表达、存储和生成方式

图分为有向图和无向图，无向图可以用有向图来表示。

图中点的存储方式

/** * in  入度：代表几条边进入该点 * out 出度：代表几条边从该点出发 **/public
class Node {
    public int value;
    public int in;
    public int out;
    public ArrayList<Node> nexts;
    public ArrayList<Edge> edges;
    public Node(int value) {
        this.value = value;
        in = 0;
        out = 0;
        nexts = new ArrayList<>();
        edges = new ArrayList<>();
    }
}

图中边的存储方式

/** * weight 边的权重 * from   边出发的边 * to     边到达的点 **/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;
    }
}

图的存储方式

/** * nodes 点集，Integer 是点中封装的数据项 * edges 边集 */public
class Graph {
    public HashMap<Integer, Node> nodes;
    public HashSet<Edge> edges;
    public Graph() {
        nodes = new HashMap<>();
        edges = new HashSet<>();
    }
}

图的生成方式

/** * 创建点集 * 创建边 * 建立点到点的关系 * 更改点的入度、出度 * 建立点和边的关系 * 创建边集 */
public
class GraphGenerator {
    public static Graph createGraph(Integer[][] matrix) {
        Graph graph = new Graph();
        for (int i = 0; i < matrix.length; i++) {
            Integer weight = matrix[i][0];
            Integer from = matrix[i][1];
            Integer to =
                matrix[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);

            // 更新点的 nexts 集，并更新出入度
            fromNode.nexts.add(toNode);
            fromNode.out++;
            toNode.in++;
            // 更新点的 edges 集，并更新图的 edges 集
            fromNode.edges.add(newEdge);
            graph.edges.add(newEdge);
        }
        return graph;
    }
}

2、图的宽度优先遍历

算法核心：

• 利用队列实现
• 从源结点开始依次按照宽度进队列，然后弹出
• 每弹出一个点，把该节点所有没有进过队列的邻接点放入队列
• 直到队列变空

/** * HashSet 用来注册进过队列的点，防止点重复进入队列 */
public class Code_01_BFS {
    public static void bfs(Node node) {
        if (node == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        HashSet<Node> map = new HashSet<>();
        queue.add(node);
        map.add(node);
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            System.out.println(cur.value);
            for (Node next : cur.nexts) {
                if (!map.contains(next)) {
                    map.add(next);
                    queue.add(next);
                }
            }
        }
    }
}

3、图的深度优先遍历

算法核心：

• 利用栈实现
• 从源节点开始把节点按照深度放入栈，然后弹出
• 每弹出一个点，把该节点下一个没有进过栈的邻接点放入栈
• 直到栈变空

/** * HashSet 用来注册进入栈的节点 * 源节点入栈并打印，源节点弹出 * 遍历源节点的所有邻接点 * 找到其中没入过栈的节点 x，将源节点和 x 压回栈中并打印 x */public
class Code_02_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 : cur.nexts) {
                if (!set.contains(next)) {
                    stack.push(cur);
                    stack.push(next);
                    set.add(next);
                    System.out.println(next.value);
                    break;
                }
            }
        }
    }
}

4、拓扑排序

适用范围：

• 有向图
• 有入度为 0 的节点
• 没有环
• 应用：编译过程等

/**  * 通过不断的删除入度为 0 的节点来完成拓扑排序   * 每次删除都会出现新的入度为 0 的节点   * inmap 存储节点入度和节点     * zeroInQueue 表示入度为 0 的节点队列      */
public static List<Node> sortedTopology(Graph graph) {
    HashMap<Node, Integer> inMap = new HashMap<>();
    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;
}

5、最小生成树的两种算法

kruskal算法和prim算法（无向图）

kp算法都是针对无向图的最小生成树，首先，最小生成树的概念：

首先给定一个无向图

在这个无向图中：1、保证边的连通性 2、连通之后边的权值是最小的

生成的图我们叫做最小生成树，上图的最小生成树如下图所示：

kruskal算法

k算法从边的角度出发，把所有边排序，从最小边开始考虑。只需思考一件事：把最小权值的边加上有没有形成环？ （使用并查集） 看这条边的from和to是否在一个集合中，如果没有就把点加进去。

public static class UnionFind{
        private HashMap<Node, Node> fatherMap;
        private HashMap<Node, Integer> rankMap;

        public UnionFind(){
            fatherMap = new HashMap<>();
            rankMap = new HashMap<>();
        }


        public void makeSets(Collection<Node> nodes){
            fatherMap.clear();
            rankMap.clear();
            for(Node node: nodes){
                fatherMap.put(node, node);
                rankMap.put(node, 1);
            }
        }

        private Node findFather(Node node){
            Node father = fatherMap.get(node);
            if(father != node){
                father = findFather(father);
            }
            fatherMap.put(node, father);
            return father;
        }



        public void union(Node a, Node b){
            if(a == null || b == null){
                return;
            }
            Node aFather = findFather(a);
            Node bFather = findFather(b);
            if(aFather != bFather){
                int aFrank = rankMap.get(aFather);
                int bFrank = rankMap.get(bFather);
                if(aFrank <= bFrank){
                    fatherMap.put(aFather, bFather);
                    rankMap.put(bFather, aFrank + bFrank);
                }else{
                    fatherMap.put(bFather, aFather);
                    rankMap.put(aFather, aFrank + bFrank);
                }
            }
        }
        public boolean isSameSet(Node a, Node b){
            return findFather(a) == findFather(b);
        }

        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());
            for(Edge edge : graph.edges){
                priorityQueue.add(edge);
            }
            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算法

p算法从点的角度出发。举例如下图：

从哪个点出发都可以，不影响最终结果。

假设从A出发，我们用下划线表示选中的点和边，用对号表示已经解锁的边。

把A加入，6、1、5三条边被解锁，选择最小权值的边1，把C点加入，（使用过的点不能重复考虑），解锁5、6、4、5四条边，继续选择最小的。边的左右两侧在集合里的点不要。

使用哈希表就可以， 不用并查集的原因是因为k算法从边出发，可能会出现连边后把两片图都连通的可能，所以需要并查集。

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> set = new HashSet<>();
        Set<Edge> result = new HashSet<>();
        for (Node node : graph.nodes.values()) {
            //上行for循环处理的是森林问题，如果给的图没说是否是连通的，可能会出现森林问题
            if (!set.contains(node)) {
                set.add(node);
                for (Edge edge : node.edges) {
                    priorityQueue.add(edge);
                }
                while (!priorityQueue.isEmpty()) {
                    Edge edge = priorityQueue.poll();
                    Node toNode = edge.to;
                    if (!set.contains(toNode)) {
                        set.add(toNode);
                        result.add(edge);
                        for (Edge nextEdge : toNode.edges) {
                            priorityQueue.add(nextEdge);
                        }
                    }
                }
            }
        }
        return result;
    }

第六节 前缀树

1、前缀树概述

​ 经典的前缀树字符是放在路上的，下面有一个不空的节点（节点上没有数据），说明这条路存在。已经存在的路径可以复用，不存在的需要新建。实际使用时，点上有数据：pass：这个节点通过多少次，当前节点及以上作为前缀的次数；end：这个节点作为多少字符串的结尾节点，已当前路径为字符串的数量；nexts：存储当前节点的子节点，不为空则说明该子节点存在。根节点的pass：加入了多少字符串，有多少字符串以空串作为前缀。

​ 一个字符串类型的数组arr1,另一个字符串类型的数组arr2。arr2中有哪些字符，是arr1中
出现的？请打印。arr2中有哪些字符，是作为arr1中某个字符串前缀出现的？请打现。a5r2
中有哪些字符，是作为arr1中某个字符串前缀出现的？请打印arr2中出现次数最大的前缀。

生成一颗前缀树核心算法：

• 在前缀树中添加一个字符串：insert
• 查询word之前加入过的次数：search
• 所有加入的字符串中，有多少是以pre作为前缀的：prefixNumber
  代码实现：
• 删除word：delete。需要先检查word是否加入过，加入过再删除
  C++注意析构问题

核心代码：

class TrieNode {
public:
	int pass;
	int end;
	//如果字符数量过多可以用unordered_map<char,TrieNode>nexts表示路
	//map<char,TrieNode>nexts
	vector<TrieNode*>nexts;

	TrieNode() {
		this->pass = 0;
		this->end = 0;

		//nexts[0]==nullptr:没有走向'a'的路
		//nexts[0]!=nullptr:有走向'a'的路
		//...
		//nexts[25]!=nullptr:有走向'z'的路
		this->nexts = vector<TrieNode*>(26,nullptr);
	}
};

class Trie {
private:
	TrieNode* root;
public:
	Trie() {
		this->root = new TrieNode;
	}

	//在前缀树中添加一个字符串
	void insert(string word) {
		if (word.length() == 0) {
			return;
		}
		TrieNode* node = root;
		node->pass++;
		for (char c : word) {
			if (node->nexts[c - 'a'] == nullptr) {
				node->nexts[c - 'a'] = new TrieNode;
			}
			node = node->nexts[c - 'a'];
			node->pass++;
		}
		node->end++;
	}


	//查询word之前加入过的次数
	int search(string word) {
		if (word.length() == 0) {
			return 0;
		}
		TrieNode* node = root;
		for (char c : word) {
			if (node->nexts[c - 'a'] == nullptr) {
				return 0;
			}
			node = node->nexts[c - 'a'];
		}
		return node->end;
	}

	//所有加入的字符串中，有多少是以pre作为前缀的
	int prefixNumber(string pre) {
		if (pre.length() == 0) {
			return 0;
		}
		TrieNode* node = root;
		for (char c : pre) {
			if (node->nexts[c - 'a'] == nullptr) {
				return 0;
			}
			node = node->nexts[c - 'a'];
		}
		return node->pass;
	}


	//删除word
	void deleteWord(string word) {
		if (search(word) != 0) {//需要先检查word是否加入过，加入过再删除
			TrieNode* node = root;
			node->pass--;
			int index = -1;//记录pass为0的字符在字符串中的位置
			TrieNode* pre = nullptr;//记录最后一个pass不为0的节点，目的是找到pass为0的节点，将其置空
			stack<TrieNode*>sk;//记录需要析构的节点
			for (int i = 0; i < word.length(); i++) {
				node->nexts[word[i] - 'a']->pass--;
				if (node->nexts[word[i] - 'a']->pass == 0) {//当某个节点的pass减减之后为0了，说明后续节点（delete）都要删掉
					pre = pre == nullptr ? node : pre;
					index = index == -1 ? i : index;
					sk.push(node->nexts[word[i] - 'a']);
				}
				node = node->nexts[word[i] - 'a'];
			}
			node->end--;
			pre->nexts[word[index] - 'a'] = nullptr;
			while (!sk.empty()) {
				delete sk.top();
				sk.pop();
			}
		}
	}
};

第七节 贪心算法

​ 在某一个标准下，优先考虑最满足标准的样本，最后考虑最不满足标准的样本，最终得到
一个答案的算法，叫作贪心算法。也就是说，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解。
局部最优—》整体最优

堆和排序是贪心算法最常用的两个技巧。

1、会议室场次问题

一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。给你每一个项目开始的时间和结束的时间（给你一个数组，里面是一个个具体的项目)，你来安排宣讲的日程，要求会议室进行的宣讲的场次最多。返回这个最多的宣讲场次。

算法核心：

按照会议结束时间早为贪心策略。

核心代码：

bool cmp(vector<int>& arr1, vector<int>& arr2) {
	return arr1[1] < arr2[1];//<:从小到大；>:从大到小
}

int bestArrange(vector<vector<int>>program, int timePoint) {
	sort(program.begin(),program.end(),cmp);
	int res = 0;
	for (int i = 0; i < program.size(); i++) {
		if (program[i][0] >= timePoint) {
			res++;
			timePoint = program[i][1];
		}
	}
	return res;
}

2、切分金条

问题描述：

一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为20的金条，不管切成长度多大的两半都要花费20个铜板。一群人想整分整块金条，怎么分最省铜板？

例如给定数组{10,20,30}，代表一共三个人，整块金条长度为10+20+30=60 金条要分成10,20,30三个部分

如果， 先把长 度60的金条分成10和50，花费60再把长度50的金条分成20和30， 花费50 一共花费110铜板

但是如果先把长度60的金条分成30和30，花费60 再把长度30 金条分成10和20，花费30 一共花费90铜板

输入一个数组，返回分割的最小代价。

算法核心：

贪心策略是哈夫曼编码

核心代码：

public class LessMoney {
      public static int lessMoney(int[] arr) {
          // PriorityQueue => min heap(default) 
          PriorityQueue<Integer> pQ = new PriorityQueue();
          // init the heap
          for (int i = 0; i < arr.length; i++) {
              pQ.add(arr[i]);
          }
          int sum = 0;
         int cur = 0;
         // cal the sum
         while (pQ.size() > 1) {
             cur = pQ.poll() + pQ.poll();
             sum += cur;
             pQ.add(cur);
         }
         return sum;
     }
         
     public static void main(String[] args) {
         // solution:
         int[] arr = { 10, 20, 30 };
         System.out.println(lessMoney(arr));
         
         int[] arr2 = { 6, 7, 8, 9 };
         System.out.println(lessMoney(arr2));
     }
 }

3、成本效益问题

问题描述：

输入：

• 参数1，正数数组costs costs[i]表示i号项目的花费
• 参数2，正数数组profits profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
• 参数3，正数k k表示你不能并行、只能串行的最多 做k个项目 => 最多能做的项目数
• 参数4，正数m m表示你初始的资金

说明：你每做完一个项目，马上获得的收益，可以支持你去做下一个项目(一次只能做一个项目)
输出： 你最后获得的最大钱数

算法核心：

首先按照花费排序将所有项目放入一个小根堆中；然后从小根堆中弹出项目花费小于等于当前资金的项目放入按照利润排序的大根堆中；从大根堆中弹出一个项目，做该项目，更新资金；然后在从小根堆中弹出项目花费小于等于当前资金的项目放入按照利润排序的大根堆中，周而复始，直到项目大根堆为空/做完k个项目

核心代码：

  int maxCapital(int k, int w, vector<vector<int>>costsAndProfits) {
	priority_queue<vector<int>, vector<vector<int>>, cmp1>minCost;
	priority_queue<vector<int>, vector<vector<int>>, cmp2>maxProf;
	for (int i = 0; i < costsAndProfits.size(); i++) {
		minCost.push(costsAndProfits[i]);
	}

	while (k > 0 && (!maxProf.empty() || (!minCost.empty() && minCost.top()[0] <= w))) {
		while (!minCost.empty()&&minCost.top()[0] <= w) {
			maxProf.push(minCost.top());
			minCost.pop();
		}
		w += maxProf.top()[1];
		maxProf.pop();
		k--;
	}
	return w;
}

---

左神算法，又称左程云算法，是一种数据结构和算法的学习方法，它将算法的学习分为三个阶段：理论基础、算法实现和应用场景。这种学习方法被证明可以提高学习效率和深入理解算法。左程云是这种算法学习方法的创始人。

学习算法的过程中，我们经常会发现自己无从下手，或者是对于算法的理解停留在表面，难以深入掌握。而左神算法正是为了解决这个问题而提出来的，它提倡先从理论基础入手，深入理解算法的原理，再去实现算法，最后在不同的应用场景中进行实战练习。这样不仅能更好地掌握算法，还能更好地应用到实际工作中。

左神算法还有很多独特的思想，比如说“不要花时间去记忆，要花时间去理解”，这句话告诉我们，学习算法不应该只是为了记忆，而应该更多地去理解算法的原理。还有“不要花时间去优化常数，要花时间去优化时间复杂度”这句话，告诉我们在编程中应该重视时间复杂度，而不是过于关注常数。这些思想都让我们更好地理解算法，更好地应用到实际工作中。

总之，左神算法是一种非常有效的学习算法的方法，它让我们更好地掌握算法，更好地应用到实际编程中。在这里，我要衷心地感谢左程云先生为我们提供了这样一种有效的学习算法的方法，让我们能够更好地掌握算法，更好地应用于现实编程中。