基础算法

评估算法优劣的核心指标是什么？
时间复杂度（流程决定）
额外空间复杂度（流程决定）
常数项时间（实现细节决定）

时间复杂度

如何确定算法流程的时间复杂度？
当完成了表达式的建立，只要把最高阶项留下即可。低阶项都去掉，高阶项的系数也去掉。

记为：O(忽略掉系数的高阶项)

时间复杂度的意义在于：

当我们要处理的样本量很大很大时，我们会发现低阶项是什么不是最重要的；每一项的系数是什么，不是最重要的。真正重要的就是最高阶项是什么。

这就是时间复杂度的意义，它是衡量算法流程的复杂程度的一种指标，该指标只与数据量有关，与过程之外的优化无关。

选择排序

过程：
arr[0～N-1]范围上，找到最小值所在的位置，然后把最小值交换到0位置。
arr[1～N-1]范围上，找到最小值所在的位置，然后把最小值交换到1位置。
arr[2～N-1]范围上，找到最小值所在的位置，然后把最小值交换到2位置。
…
arr[N-1～N-1]范围上，找到最小值位置，然后把最小值交换到N-1位置。

估算：
很明显，如果arr长度为N，每一步常数操作的数量，如等差数列一般
所以，总的常数操作数量 = a*(N^2) + b*N + c (a、b、c都是常数)

所以选择排序的时间复杂度为O(N^2)。

//核心思想：
//i ~ N-1 中最小的值放在 i 上
for (int i = 0; i < arr.length - 1; i++) { // i ~ N-1
    // 最小值在哪个位置上  i～n-1
    int minIndex = i;
    for (int j = i + 1; j < arr.length; j++) { 
        // i ~ N-1 上找最小值的下标 
        minIndex = arr[j] < arr[minIndex] ? j : minIndex;
    }
    //交换
    swap(arr, i, minIndex);
}

冒泡排序

过程：
在arr[0～N-1]范围上：
arr[0]和arr[1]，谁大谁来到1位置；arr[1]和arr[2]，谁大谁来到2位置…arr[N-2]和arr[N-1]，谁大谁来到N-1位置

在arr[0～N-2]范围上，重复上面的过程，但最后一步是arr[N-3]和arr[N-2]，谁大谁来到N-2位置
在arr[0～N-3]范围上，重复上面的过程，但最后一步是arr[N-4]和arr[N-3]，谁大谁来到N-3位置
…
最后在arr[0～1]范围上，重复上面的过程，但最后一步是arr[0]和arr[1]，谁大谁来到1位置


估算：
很明显，如果arr长度为N，每一步常数操作的数量，依然如等差数列一般
所以，总的常数操作数量 = a*(N^2) + b*N + c (a、b、c都是常数)

所以冒泡排序的时间复杂度为O(N^2)。

// 0 ~ N-1
// 0 ~ N-2
// 0 ~ N-3
for (int e = arr.length - 1; e > 0; e--) { // 0 ~ e
    for (int i = 0; i < e; i++) {
        //重点在于i 和 i+1 比较交换
        if (arr[i] > arr[i + 1]) {
            swap(arr, i, i + 1);
        }
    }
}

插入排序

过程：
想让arr[0~0]上有序，这个范围只有一个数，当然是有序的。
想让arr[0~1]上有序，所以从arr[1]开始往前看，如果arr[1]<arr[0]，就交换。否则什么也不做。
…
想让arr[0~i]上有序，所以从arr[i]开始往前看，arr[i]这个数不停向左移动，一直移动到左边的数字不再比自己大，停止移动。
最后一步，想让arr[0~N-1]上有序， arr[N-1]这个数不停向左移动，一直移动到左边的数字不再比自己大，停止移动。

估算时发现这个算法流程的复杂程度，会因为数据状况的不同而不同。

// 0~0 有序的
// 0~i 想有序
for (int i = 1; i < arr.length; i++) { // 0 ~ i 做到有序
    for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
        swap(arr, j, j + 1);
    }
}

如果某个算法流程的复杂程度会根据数据状况的不同而不同，那么你必须要按照最差情况来估计。

很明显，在最差情况下，如果arr长度为N，插入排序的每一步常数操作的数量，还是如等差数列一般

所以，总的常数操作数量 = a*(N^2) + b*N + c (a、b、c都是常数)

所以插入排序排序的时间复杂度为O(N^2)。

额外空间复杂度

你要实现一个算法流程，在实现算法流程的过程中，你需要开辟一些空间来支持你的算法流程。

作为输入参数的空间，不算额外空间。
作为输出结果的空间，也不算额外空间。

因为这些都是必要的、和现实目标有关的。所以都不算。

但除此之外，你的流程如果还需要开辟空间才能让你的流程继续下去。这部分空间就是额外空间。

如果你的流程只需要开辟有限几个变量，额外空间复杂度就是O(1)。

我们会发现，时间复杂度这个指标，是忽略低阶项和所有常数系数的。

难道同样时间复杂度的流程，在实际运行时候就一样的好吗？

当然不是。

时间复杂度只是一个很重要的指标而已。如果两个时间复杂度一样的算法，你还要去在时间上拼优劣，就进入到拼常数时间的阶段，简称拼常数项。

算法流程的常数项

放弃理论分析，生成随机数据直接测。

为什么不去理论分析？

不是不能纯分析，而是没必要。因为不同常数时间的操作，虽然都是固定时间，但还是有快慢之分的。

比如，位运算的常数时间原小于算术运算的常数时间，这两个运算的常数时间又远小于数组寻址的时间。

所以如果纯理论分析，往往会需要非常多的分析过程。都已经到了具体细节的程度，莫不如交给实验数据好了。

二分法

//在一个有序数组中，找某个数是否存在 
public static boolean exist(int[] sortedArr, int num) {
    if (sortedArr == null || sortedArr.length == 0) {
        return false;
    }
    int L = 0;
    int R = sortedArr.length - 1;
    int mid = 0;
    // L..R
    while (L < R) {
        mid = L + ((R - L) >> 1); // mid = (L + R) / 2
        if (sortedArr[mid] == num) {
            return true;
        } else if (sortedArr[mid] > num) {
            R = mid - 1;
        } else {
            L = mid + 1;
        }
    }
    return sortedArr[L] == num;
}

//在一个有序数组中，找>=value最左侧的位置 
public static int nearestIndex(int[] arr, int value) {
    int L = 0;
    int R = arr.length - 1;
    int index = -1; // 记录最左的对号
    while (L <= R) {
        int mid = L + ((R - L) >> 1);
        if (arr[mid] >= value) {
            index = mid;
            R = mid - 1;
        } else {
            L = mid + 1;
        }
    }
    return index;
}

//局部最小值问题(等于找数据的曲线变化转折点，数值连续下降再上升，就算是一个局部最小值)
public static int getLessIndex(int[] arr) {
    if (arr == null || arr.length == 0) {
        return -1; // no exist
    }
    if (arr.length == 1 || arr[0] < arr[1]) {
        return 0;
    }
    if (arr[arr.length - 1] < arr[arr.length - 2]) {
        return arr.length - 1;
    }
    int left = 1;
    int right = arr.length - 2;
    int mid = 0;
    while (left < right) {
        mid = (left + right) / 2;
        if (arr[mid] > arr[mid - 1]) {
            right = mid - 1;
        } else if (arr[mid] > arr[mid + 1]) {
            left = mid + 1;
        } else {
            return mid;
        }
    }
    return left;
}

异或运算

//如何不用额外变量交换两个数
a = a ^ b
b = a ^ b
a = a ^ b

//注意：a 和 b 不能指向同一个地址空间，否则怎么交换都是0
// 比如i和j是一个位置的话，会出错
public static void swap(int[] arr, int i, int j) {
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}

//一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数 
public static void printOddTimesNum1(int[] arr) {
    int eor = 0;
    for (int i = 0; i < arr.length; i++) {
        eor ^= arr[i];
    }
    System.out.println(eor);
}

//怎么把一个int类型的数，提取出最右侧的1来
n & (~n + 1);
// n 	: 001100100
// ~n	: 110011011
// ~n+1	: 110011100
//		: 000000100

//一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种数
public static void printOddTimesNum2(int[] arr) {
    int eor = 0;
    for (int i = 0; i < arr.length; i++) {
        eor ^= arr[i];
    }
    // eor = a ^ b
    // eor != 0
    // eor必然有一个位置上是1（必然这两个数在这位上一个是0一个是1）
    // 0110010000
    // 0000010000
    int rightOne = eor & (~eor + 1); // 提取出最右的1
    int onlyOne = 0; // eor'
    for (int i = 0 ; i < arr.length;i++) {
        //  arr[1] =  111100011110000
        // rightOne=  000000000010000
        //只异或最右边有1的值，偶数的过滤完，剩下奇数的那个数
        if ((arr[i] & rightOne) != 0) {
            onlyOne ^= arr[i];
        }
    }
    System.out.println(onlyOne + " " + (eor ^ onlyOne));
}

//提取整数n转换成二进制之后，他的中1的数量
public static int bit1counts(int N) {
    int count = 0;
    while(n != 0) {
        int rightOne = n & (~n + 1);
        count++;
        n = n ^ rightOne;
    }
}

栈和队列

//用数组实现队列
public static class MyQueue {
    private int[] arr;
    private int pushi;
    private int polli;
    private int size;
    private final int limit;

    public MyQueue(int limit) {
        arr = new int[limit];
        pushi = 0;
        polli = 0;
        size = 0;
        this.limit = limit;
    }

    public void push(int value) {
        if (size == limit) {
            throw new RuntimeException("栈满了，不能再加了");
        }
        size++;
        arr[pushi] = value;
        pushi = nextIndex(pushi);
    }

    public int pop() {
        if (size == 0) {
            throw new RuntimeException("栈空了，不能再拿了");
        }
        size--;
        int ans = arr[polli];
        polli = nextIndex(polli);
        return ans;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    // 如果现在的下标是i，返回下一个位置
    private int nextIndex(int i) {
        return i < limit - 1 ? i + 1 : 0;
    }

}

1
2
3

实现一个特殊的栈，在基本功能的基础上，再实现返回栈中最小元素的功能
pop、push、getMin操作的时间复杂度都是 O(1)。 
设计的栈类型可以使用现成的栈结构。

1
2
3

思想：用两个Stack，一个存储数据，一个存储最小值
解法一：小于等于栈顶元素时才push，等于栈顶元素时才pop
解法二：push的时候压入min和push之中的最小值，弹出则都弹出

//开多个栈，push的时候压入min和push之中的最小值，弹出则都弹出
public static class MyStack2 {
    private Stack<Integer> stackData;
    private Stack<Integer> stackMin;

    public MyStack2() {
        this.stackData = new Stack<Integer>();
        this.stackMin = new Stack<Integer>();
    }

    public void push(int newNum) {
        if (this.stackMin.isEmpty()) {
            this.stackMin.push(newNum);
        } else if (newNum < this.getmin()) {
            this.stackMin.push(newNum);
        } else {
            int newMin = this.stackMin.peek();
            this.stackMin.push(newMin);
        }
        this.stackData.push(newNum);
    }

    public int pop() {
        if (this.stackData.isEmpty()) {
            throw new RuntimeException("Your stack is empty.");
        }
        this.stackMin.pop();
        return this.stackData.pop();
    }

    public int getmin() {
        if (this.stackMin.isEmpty()) {
            throw new RuntimeException("Your stack is empty.");
        }
        return this.stackMin.peek();
    }
}

//如何用栈结构实现队列结构
//两个栈，一个push、一个pop，把push推到pop栈再弹出pop栈顶
public static class TwoStacksQueue {
    public Stack<Integer> stackPush;
    public Stack<Integer> stackPop;

    public TwoStacksQueue() {
        stackPush = new Stack<Integer>();
        stackPop = new Stack<Integer>();
    }
  //只要pop空了再移过去,每次移过去要移动所有push栈的数据
    // push栈向pop栈倒入数据
    private void pushToPop() {
        if (stackPop.empty()) {
            while (!stackPush.empty()) {
                stackPop.push(stackPush.pop());
            }
        }
    }

    public void add(int pushInt) {
        stackPush.push(pushInt);
        pushToPop();
    }

    public int poll() {
        if (stackPop.empty() && stackPush.empty()) {
            throw new RuntimeException("Queue is empty!");
        }
        pushToPop();
        return stackPop.pop();
    }

    public int peek() {
        if (stackPop.empty() && stackPush.empty()) {
            throw new RuntimeException("Queue is empty!");
        }
        pushToPop();
        return stackPop.peek();
    }
}

//如何用队列结构实现栈结构
//两个队列，一个存，取，当取的时候把存的队列都塞到取的队列中，一直塞到存的队列剩下一个，把那个数据返回，并且设置取队列等于存队列，存队列等于取队列
public static class TwoQueueStack<T> {
    public Queue<T> queue;
    public Queue<T> help;

    public TwoQueueStack() {
        queue = new LinkedList<>();
        help = new LinkedList<>();
    }

    public void push(T value) {
        queue.offer(value);
    }

    public T poll() {
        while (queue.size() > 1) {
            help.offer(queue.poll());
        }
        T ans = queue.poll();
        Queue<T> tmp = queue;
        queue = help;
        help = tmp;
        return ans;
    }

    public T peek() {
        while (queue.size() > 1) {
            help.offer(queue.poll());
        }
        T ans = queue.poll();
        help.offer(ans);
        Queue<T> tmp = queue;
        queue = help;
        help = tmp;
        return ans;
    }

    public boolean isEmpty() {
        return queue.isEmpty();
    }

}

递归

递归公式
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)

// arr[L..R]范围上求最大值  L ... R   N
public static int process(int[] arr, int L, int R) {
    if (L == R) { // arr[L..R]范围上只有一个数，直接返回，base case
        return arr[L];
    }
    int mid = L + ((R - L) >> 1); // 中点   	1
    int leftMax = process(arr, L, mid);
    int rightMax = process(arr, mid + 1, R);
    return Math.max(leftMax, rightMax);
}

//时间复杂度:
//T（N） = 2 * T（N/2） + O(N^0)
//log(2,2) = 1 > 0，复杂度为O(N)

哈希表

1)哈希表在使用层面上可以理解为一种集合结构
2)如果只有key，没有伴随数据value，可以使用HashSet结构
3)如果既有key，又有伴随数据value，可以使用HashMap结构
4)有无伴随数据，是HashMap和HashSet唯一的区别，实际结构是一回事 
5)使用哈希表增(put)、删(remove)、改(put)和查(get)的操作，可以认为时间复杂度为 O(1)，但是常数时间比较大 
6)放入哈希表的东西，如果是基础类型，内部按值传递，内存占用是这个东西的大小 
7)放入哈希表的东西，如果不是基础类型，内部按引用传递，内存占用是8字节

哈希表在使用时，增删改查时间复杂度都是O(1)
有序表在使用时，比哈希表功能多，时间复杂度都是O(logN)

归并排序

1）整体是递归，左边排好序+右边排好序+merge让整体有序
2）让其整体有序的过程里用了排外序方法
3）利用master公式来求解时间复杂度
4）当然可以用非递归实现

// arr[L...R]范围上，变成有序的
//二分，开辟新数组，遍历二分的左右数组比较大小塞进去，然后拷贝回去
//O(N * log N)
//选择排序O(N^2)大量在浪费比较行为
public static void process(int[] arr, int L, int R) {
    if (L == R) { // base case
        return;
    }
    int mid = L + ((R - L) >> 1);
    process(arr, L, mid);
    process(arr, mid + 1, R);
    merge(arr, L, mid, R);
}

public static void merge(int[] arr, int L, int M, int R) {
    int[] help = new int[R - L + 1];
    int i = 0;
    int p1 = L;
    int p2 = M + 1;
    //下标遍历两个数组，赋值新数组
    while (p1 <= M && p2 <= R) {
        help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
    }
    // 要么p1越界了，要么p2越界了
    while (p1 <= M) {
        help[i++] = arr[p1++];
    }
    while (p2 <= R) {
        help[i++] = arr[p2++];
    }
    for (i = 0; i < help.length; i++) {
        arr[L + i] = help[i];
    }
}

// 非递归方法实现
//通过把相邻的MergeSize个数据有序，分段，每次合并两段，再重复
//O(N * log N)
public static void mergeSort2(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    int N = arr.length;
    int mergeSize = 1;// 当前有序的，左组长度
    while (mergeSize < N) { // log N
        //当前组的下标
        int L = 0;
        // 0.... 
        while (L < N) {
            // L...M  左组（mergeSize）
            int M = L + mergeSize - 1;
            if (M >= N) {
                break;
            }
            //  L...M   M+1...R(mergeSize)
            int R = Math.min(M + mergeSize, N - 1);
            merge(arr, L, M, R);
            L = R + 1;
        }
        //防止双倍数组长度逸出int最大值
        if (mergeSize > N / 2) {
            break;
        }
        //双倍扩大
        mergeSize <<= 1;
    }
}

// arr[L..R]既要排好序，也要求小和返回
//在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。
public static int process(int[] arr, int l, int r) {
    if (l == r) {
        return 0;
    }
    // l < r
    int mid = l + ((r - l) >> 1);
    //左组 和右组 迭代过程中产生的小和 + 自己调用merge产生的小和
    return 
        process(arr, l, mid) 
        + 
        process(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 i = 0;
    int p1 = L;
    int p2 = m + 1;
    int res = 0;
    while (p1 <= m && p2 <= r) {
        //右边的比左边的大时，计算右边还剩下多少个数 * 左边的值，累加到res上
        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;
}

快速排序

//把所有非0的数放左边
//设定一个index，遇到非0的都和index交换，index++
int index = -1;
for(int i = 0;i < arr.length; i++) {
    if (arr[i] > 0) {
        swap(arr, i, ++index);
    }
}

1
2
3

荷兰国旗问题
给定一个数组arr，和一个整数num。请把小于num的数放在数组的左边，等于num的数放在中间，大于num的数放在数组的右边。
返回等于num的下标

// arr[L..R]上，以arr[R]位置的数做划分值
// <= X > X
// <= X X
public static int partition(int[] arr, int L, int R) {
    if (L > R) {
        return -1;
    }
    if (L == R) {
        return L;
    }
    int lessEqual = L - 1;
    int index = L;
    while (index < R) {
        //由于这里用了<=，所以有多个num时，会返回最右边的下标
        if (arr[index] <= arr[R]) {
            swap(arr, index, ++lessEqual);
        }
        index++;
    }
    swap(arr, ++lessEqual, R);
    return lessEqual;
}

快速排序1.0

在arr[L..R]范围上，进行快速排序的过程：
1）用arr[R]对该范围做partition，<= arr[R]的数在左部分并且保证arr[R]最后来到左部分的最后一个位置，记为M； <= arr[R]的数在右部分（arr[M+1..R]）
2）对arr[L..M-1]进行快速排序(递归)
3）对arr[M+1..R]进行快速排序(递归)
因为每一次partition都会搞定一个数的位置且不会再变动，所以排序能完成

时间复杂度O(N^2)

//V1.0
public static void process1(int[] arr, int L, int R) {
    if (L >= R) {
        return;
    }
    // L..R partition arr[R]  [   <=arr[R]   arr[R]    >arr[R]  ]
    int M = partition(arr, L, R);
    process1(arr, L, M - 1);
    process1(arr, M + 1, R);
}

快速排序2.0

在arr[L..R]范围上，进行快速排序的过程：
1）用arr[R]对该范围做partition，< arr[R]的数在左部分，== arr[R]的数中间，>arr[R]的数在右部分。假设== arr[R]的数所在范围是[a,b]
2）对arr[L..a-1]进行快速排序(递归)
3）对arr[b+1..R]进行快速排序(递归)
因为每一次partition都会搞定一批数的位置且不会再变动，所以排序能完成

时间复杂度O(N^2)

//V2.0
public static void process2(int[] arr, int L, int R) {
    if (L >= R) {
        return;
    }
    //返回arr[R]的下标范围
    int[] equalArea = netherlandsFlag(arr, L, R);
    process2(arr, L, equalArea[0] - 1);
    process2(arr, equalArea[1] + 1, R);
}

// arr[L...R] 玩荷兰国旗问题的划分，以arr[R]做为num的值
public static int[] netherlandsFlag(int[] arr, int L, int R) {
    //  <arr[R]  ==arr[R]  > arr[R]
    //返回 中间等于 arr[R]的区间
    int less = L - 1; // < 区 右边界
    int more = R;     // > 区 左边界 最右边的R不动
    int index = L;
    //遍历的区间在于  [L--- R-1]
    while (index < more) {
        if (arr[index] == arr[R]) {
            index++;
        } else if (arr[index] < arr[R]) {
            swap(arr, index++, ++less);
        } else { // >
            swap(arr, index, --more);
        }
    }
    //最后再把index=R的数据插到more的左侧
    // L...Less less+1...more-1  more...R-1 R
    // L...Less less+1........more more+1...R
    swap(arr, more, R);
    return new int[] { less + 1, more };
}

快速排序3.0(随机快排+荷兰国旗技巧优化)

在arr[L..R]范围上，进行快速排序的过程：
1）在这个范围上，随机选一个数记为num，
1）用num对该范围做partition，< num的数在左部分，== num的数中间，>num的数在右部分。假设== num的数所在范围是[a,b]
2）对arr[L..a-1]进行快速排序(递归)
3）对arr[b+1..R]进行快速排序(递归)
因为每一次partition都会搞定一批数的位置且不会再变动，所以排序能完成

//V3.0
public static void process3(int[] arr, int L, int R) {
    if (L >= R) {
        return;
    }
    swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
    int[] equalArea = netherlandsFlag(arr, L, R);
    process3(arr, L, equalArea[0] - 1);
    process3(arr, equalArea[1] + 1, R);
}

public static int[] netherlandsFlag(int[] arr, int L, int R) {
    if (L > R) {
        return new int[] { -1, -1 };
    }
    if (L == R) {
        return new int[] { L, R };
    }
    int less = L - 1; // < 区 右边界
    int more = R;     // > 区 左边界
    int index = L;
    while (index < more) {
        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 new int[] { less + 1, more };
}

1）通过分析知道，划分值越靠近中间，性能越好；越靠近两边，性能越差
2）随机选一个数进行划分的目的就是让好情况和差情况都变成概率事件
3）把每一种情况都列出来，会有每种情况下的时间复杂度，但概率都是1/N
4）那么所有情况都考虑，时间复杂度就是这种概率模型下的长期期望！

时间复杂度O(N*logN)，额外空间复杂度O(logN)都是这么来的。

堆结构

1）堆结构就是用数组实现的完全二叉树结构
2）完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
3）完全二叉树中如果每棵子树的最小值都在顶部就是小根堆
4）堆结构的heapInsert与heapify操作
5）堆结构的增大和减少 
6）优先级队列结构，就是堆结构

N个元素，树的高度： logN


父节点:(index - 1)/2
左子节点：2 * index + 1
右子节点： 2 * index + 2
注：有些算法不算第0个下标的数据，而是从1开始，因为计算节点将变成：
父节点：index/2   (index >> 1)
左子节点： 2 * index  (index << 1)
右子节点： 2 * index + 1 ((index << 1) | 1)

//把第0个位置当做根节点，1~2位置当做根节点的左右节点
public static class MyMaxHeap {
    private int[] heap;
    private final int limit;
    //当前heap中保持着大根堆结构的数量
    private int heapSize;
    public void push(int value) {
        if (heapSize == limit) {
            throw new RuntimeException("heap is full");
        }
        heap[heapSize] = value;
        // value  heapSize
        heapInsert(heap, heapSize++);
    }

    // 用户此时，让你返回最大值，并且在大根堆中，把最大值删掉
    // 剩下的数，依然保持大根堆组织
    public int pop() {
        int ans = heap[0];
        //最后的heapSize和根节点交换
        swap(heap, 0, --heapSize);
        heapify(heap, 0, heapSize);
        return ans;
    }

    private void heapInsert(int[] arr, int index) {
        // arr[index]
        // arr[index] 不比 arr[index父]大了 ， 停
        // index = 0;
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }
  
    // 从index位置，往下看，不断的下沉，
  // 停：我的孩子都不再比我大；已经没孩子了
    // arr[index]位置的数，能否往下移动
    public static void heapify(int[] arr, int index, int heapSize) {
        int left = index * 2 + 1; // 左孩子的下标
        while (left < heapSize) { // 下方还有孩子的时候
            // 两个孩子中，谁的值大，把下标给largest
            // 1）只有左孩子，left -> largest
            // 2) 同时有左孩子和右孩子，右孩子的值<= 左孩子的值，left -> largest
            // 3) 同时有左孩子和右孩子并且右孩子的值> 左孩子的值， right -> largest
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            // 父和较大的孩子之间，谁的值大，把下标给largest
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }
}

堆排序
1，先让整个数组都变成大根堆结构，建立堆的过程: 
    1)从上到下的方法，时间复杂度为O(N*logN) 
    2)从下到上的方法，时间复杂度为O(N) 
2，把堆的最大值和堆末尾的值交换，然后减少堆的大小之后，再去调整堆，一直周而复始，时间复杂度为O(N*logN) 
3，堆的大小减小成0之后，排序完成

// 堆排序额外空间复杂度O(1)
// 堆排序的逻辑：先排一次大根堆，第0个位置肯定是最大的  O(N*logN)
// 把第0个位置和大根堆最后一个数交换，大根堆范围缩小1 O(N*logN)
// 接着循环一直排大根堆，直到heapSize等于0

//第一次创建大根堆的逻辑可以优化成O(N)，要逆序从最后一个往上比较，父节点小的调用heapify下沉

public 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;
    swap(arr, 0, --heapSize);
    // O(N*logN)
    while (heapSize > 0) { // O(N)
        heapify(arr, 0, heapSize); // O(logN)
        swap(arr, 0, --heapSize); // O(1)
    }
}

1
2
3

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

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

//时间复杂度O(N * logK)
//在K个范围排序小根堆，然后弹出根节点，再加入下一个结点
public static void sortedArrDistanceLessK(int[] arr, int k) {
    if (k == 0) {
        return;
    }
    // 默认小根堆
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    int index = 0;
    // 0...K-1
    for (; index <= Math.min(arr.length - 1, k - 1); index++) {
        heap.add(arr[index]);
    }
    int i = 0;
    for (; index < arr.length; i++, index++) {
        heap.add(arr[index]);
        arr[i] = heap.poll();
    }
    //当小根堆无法继续扩容时，以此弹出小根堆中最小的值
    while (!heap.isEmpty()) {
        arr[i++] = heap.poll();
    }
}

前缀树

1）单个字符串中，字符从前到后的加到一棵多叉树上
2）字符放在路上，节点上有专属的数据项（常见的是pass和end值）
3）所有样本都这样添加，如果没有路就新建，如有路就复用
4）沿途节点的pass值增加1，每个字符串结束时来到的节点end值增加1

可以完成前缀相关的查询

例子：
设计一种结构。用户可以：
1）void insert(String str)            添加某个字符串，可以重复添加，每次算1个
2）int search(String str)             查询某个字符串在结构中还有几个
3)  void delete(String str)           删掉某个字符串，可以重复删除，每次算1个
4）int prefixNumber(String str)  查询有多少个字符串，是以str做前缀的

//通过链表记录链路，index记录字母
public static class Node1 {
    public int pass;
    public int end;
    public Node1[] nexts;

    public Node1() {
        pass = 0;
        end = 0;
        nexts = new Node1[26];
    }
}

public static class Trie1 {
    private Node1 root;

    public Trie1() {
        root = new Node1();
    }

    public void insert(String word) {
        if (word == null) {
            return;
        }
        char[] chs = word.toCharArray();
        Node1 node = root;
        node.pass++;
        int index = 0;
        for (int i = 0; i < chs.length; i++) { // 从左往右遍历字符
            index = chs[i] - 'a'; // 由字符，对应成走向哪条路
            if (node.nexts[index] == null) {
                node.nexts[index] = new Node1();
            }
            node = node.nexts[index];
            node.pass++;
        }
        node.end++;
    }

    public void delete(String word) {
        if (search(word) != 0) {
            char[] chs = word.toCharArray();
            Node1 node = root;
            node.pass--;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = chs[i] - 'a';
                if (--node.nexts[index].pass == 0) {
                    node.nexts[index] = null;
                    return;
                }
                node = node.nexts[index];
            }
            node.end--;
        }
    }

    // word这个单词之前加入过几次
    public int search(String word) {
        if (word == null) {
            return 0;
        }
        char[] chs = word.toCharArray();
        Node1 node = root;
        int index = 0;
        for (int i = 0; i < chs.length; i++) {
            index = chs[i] - 'a';
            if (node.nexts[index] == null) {
                return 0;
            }
            node = node.nexts[index];
        }
        return node.end;
    }

    // 所有加入的字符串中，有几个是以pre这个字符串作为前缀的
    public int prefixNumber(String pre) {
        if (pre == null) {
            return 0;
        }
        char[] chs = pre.toCharArray();
        Node1 node = root;
        int index = 0;
        for (int i = 0; i < chs.length; i++) {
            index = chs[i] - 'a';
            if (node.nexts[index] == null) {
                return 0;
            }
            node = node.nexts[index];
        }
        return node.pass;
    }
}

桶排序

桶排序思想下的排序：计数排序 & 基数排序 

1)桶排序思想下的排序都是不基于比较的排序

2)时间复杂度为O(N)，额外空间负载度O(M)

3)应用范围有限，需要样本的数据状况满足桶的划分 

一般来讲，计数排序要求，样本是整数，且范围比较窄
一般来讲，基数排序要求，样本是10进制的正整数
一旦要求稍有升级，改写代价增加是显而易见的

计数排序:
如年龄0~200，设定一个下标为0~200的数组，遍历并数组中的值++，适用范围有限且和样本数据强关联
基数排序：
建立十个桶队列，低位数据补齐至和高位相同位数，如 100,001
按照个十百位顺序入队列，再依次取出十个桶队列的所有元素，最后有序

//排序非负数的十进制
// only for no-negative value
public static void radixSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    radixSort(arr, 0, arr.length - 1, maxbits(arr));
}

//获取最大值的位数 如 100 ---> 3位
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;
}

// arr[l..r]排序  ,  digit
// l..r    3 56 17 100    3
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];
    //d表示当前要取出的位数下标，1表示个位，2表示十位
    for (int d = 1; d <= digit; d++) { // 有多少位就进出几次
        // 10个空间
        // count[0] 当前位(d位)是0的数字有多少个
        // count[1] 当前位(d位)是(0和1)的数字有多少个
        // count[2] 当前位(d位)是(0、1和2)的数字有多少个
        // count[i] 当前位(d位)是(0~i)的数字有多少个
        int[] count = new int[radix]; // count[0..9]
        //这时候的count[]存储的个位数等于当前下标的数量
        for (i = L; i <= R; i++) {
            // 103  d=1   3
            // 209  d=1   9
            j = getDigit(arr[i], d);
            count[j]++;
        }
        //count做累加和，i - 1的数据做累加，count[]存储的是个位数小于等于当前下标的数量
        for (i = 1; i < radix; i++) {
            count[i] = count[i] + count[i - 1];
        }
        //倒序遍历数组，把数据放在第count[j]个位置上，j--
        //通过这种方式实现队列排序
        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];
        }
    }
}

public static int getDigit(int x, int d) {
    return ((x / ((int) Math.pow(10, d - 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）基于比较的排序，时间复杂度的极限是O(N*logN)
4）时间复杂度O(N*logN)、额外空间复杂度低于O(N)、且稳定的基于比较的排序是不存在的。
5）为了绝对的速度选快排、为了省空间选堆排、为了稳定性选归并

链表

快慢指针：快指针走的步数是慢指针的两倍
1）输入链表头节点，奇数长度返回中点，偶数长度返回上中点
2）输入链表头节点，奇数长度返回中点，偶数长度返回下中点
3）输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
4）输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个

public static class Node {
    public int value;
    public Node next;

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

// head 头
//1）输入链表头节点，奇数长度返回中点，偶数长度返回上中点
public static Node midOrUpMidNode(Node head) {
    if (head == null || head.next == null || head.next.next == null) {
        return head;
    }
    // 链表有3个点或以上
    Node slow = head.next;
    Node fast = head.next.next;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

//2）输入链表头节点，奇数长度返回中点，偶数长度返回下中点
public static Node midOrDownMidNode(Node head) {
    if (head == null || head.next == null) {
      return head;
    }
    Node slow = head.next;
    Node fast = head.next;
    while (fast.next != null && fast.next.next != null) {
      slow = slow.next;
      fast = fast.next.next;
    }
    return slow;
  }

//3）输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
public static Node midOrUpMidPreNode(Node head) {
    if (head == null || head.next == null || head.next.next == null) {
      return null;
    }
    Node slow = head;
    Node fast = head.next.next;
    while (fast.next != null && fast.next.next != null) {
      slow = slow.next;
      fast = fast.next.next;
    }
    return slow;
  }

//4）输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个
public static Node midOrDownMidPreNode(Node head) {
    if (head == null || head.next == null) {
      return null;
    }
    if (head.next.next == null) {
      return head;
    }
    Node slow = head;
    Node fast = head.next;
    while (fast.next != null && fast.next.next != null) {
      slow = slow.next;
      fast = fast.next.next;
    }
    return slow;
  }

给定一个单链表的头节点head，请判断该链表是否为回文结构。 
笔试做法：
1.创建栈，全都丢到栈里，弹出来和原来的链表做比较，空间复杂度O（N）
2.快慢指针找到中点，中点后的链表压入栈中，空间复杂度O（N/2）
面试做法：
快慢指针找到中点，reverse中点后的链表，然后头尾两个指针遍历比较，最后要还原reverse的链表

// need n extra space
//时间复杂度O（N），空间复杂度O（N）
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;
}

// 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
    }
    // n1 中点


    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;
}

将单向链表按某值划分成左边小、中间相等、右边大的形式

1）把链表放入数组里，在数组上做partition（笔试用）

2）分成小、中、大三部分，再把各个部分之间串起来（面试用）

//用6个指针，生成三条链表，最后连起来
public static Node listPartition2(Node head, int pivot) {
    Node sH = null; // small head
    Node sT = null; // small tail
    Node eH = null; // equal head
    Node eT = null; // equal tail
    Node mH = null; // big head
    Node mT = null; // big tail
    Node next = null; // save next node
    // every node distributed to three lists
    while (head != null) {
        next = head.next;
        head.next = null;
        if (head.value < pivot) {
            if (sH == null) {
                sH = head;
                sT = head;
            } else {
                sT.next = head;
                sT = head;
            }
        } else if (head.value == pivot) {
            if (eH == null) {
                eH = head;
                eT = head;
            } else {
                eT.next = head;
                eT = head;
            }
        } else {
            if (mH == null) {
                mH = head;
                mT = head;
            } else {
                mT.next = head;
                mT = head;
            }
        }
        head = next;
    }
    // 小于区域的尾巴，连等于区域的头，等于区域的尾巴连大于区域的头
    if (sT != null) { // 如果有小于区域
        sT.next = eH;
        eT = eT == null ? sT : eT; // 下一步，谁去连大于区域的头，谁就变成eT
    }
    // 上面的if，不管跑了没有，et
    // all reconnect
    if (eT != null) { // 如果小于区域和等于区域，不是都没有
        eT.next = mH;
    }
    return sH != null ? sH : (eH != null ? eH : mH);
}

一种特殊的单链表节点类描述如下 
class Node { 
int value; 
Node next; 
Node rand; 
Node(int val) { value = val; } 
} 
rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，也可能指向null。
给定一个由Node节点类型组成的无环单链表的头节点 head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。 
【要求】
时间复杂度O(N)，额外空间复杂度O(1)

//hash表做法  空间复杂度O（N）
public static Node copyListWithRand1(Node head) {
    HashMap<Node, Node> map = new HashMap<Node, Node>();
    Node cur = head;
    while (cur != null) {
        map.put(cur, new Node(cur.value));
        cur = cur.next;
    }
    cur = head;
    while (cur != null) {
        // cur 老
        // map.get(cur) 新
        map.get(cur).next = map.get(cur.next);
        map.get(cur).rand = map.get(cur.rand);
        cur = cur.next;
    }
    return map.get(head);
}

//拷贝链表结点，并插入到链表中，然后按对获取结点，设置rand值，再分离next指针，返回链表
public static Node copyListWithRand2(Node head) {
    if (head == null) {
        return null;
    }
    Node cur = head;
    Node next = null;
    // copy node and link to every node
    // 1 -> 2
    // 1 -> 1' -> 2
    while (cur != null) {
        // cur 老 next 老的下一个
        next = cur.next;
        cur.next = new Node(cur.value);
        cur.next.next = next;
        cur = next;
    }
    cur = head;
    Node curCopy = null;
    // set copy node rand
    // 1 -> 1' -> 2 -> 2'
    while (cur != null) {
        // cur 老
        // cur.next 新 copy
        next = cur.next.next;
        curCopy = cur.next;
        curCopy.rand = cur.rand != null ? cur.rand.next : null;
        cur = next;
    }
    // head head.next
    Node res = head.next;
    cur = head;
    // split
    while (cur != null) {
        next = cur.next.next;
        curCopy = cur.next;
        cur.next = next;
        curCopy.next = next != null ? next.next : null;
        cur = next;
    }
    return res;
}

1
2
3

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

// 找到链表第一个入环节点，如果无环，返回null
//当有环时，快指针和慢指针相遇后，慢指针接着往下走，快指针回到头结点，每次走一步，他们再次相遇的点就是第一个入环节点
public static Node getLoopNode(Node head) {
    if (head == null || head.next == null || head.next.next == null) {
        return null;
    }
    // n1 慢  n2 快
    Node n1 = head.next; // n1 -> slow
    Node n2 = head.next.next; // n2 -> fast
    while (n1 != n2) {
        if (n2.next == null || n2.next.next == null) {
            return null;
        }
        n2 = n2.next.next;
        n1 = n1.next;
    }
    n2 = head; // n2 -> walk again from head
    while (n1 != n2) {
        n1 = n1.next;
        n2 = n2.next;
    }
    return n1;
}

// 如果两个链表都无环，返回第一个相交节点，如果不想交，返回null
//记录链表长度，如果最后一个结点不同，则不相交
//相交的话，减去长链表的和短链表的差值，同长之后一起遍历，判断结点是否相同
public static Node noLoop(Node head1, Node head2) {
    if (head1 == null || head2 == null) {
        return null;
    }
    Node cur1 = head1;
    Node cur2 = head2;
    int n = 0;
    while (cur1.next != null) {
        n++;
        cur1 = cur1.next;
    }
    while (cur2.next != null) {
        n--;
        cur2 = cur2.next;
    }
    if (cur1 != cur2) {
        return null;
    }
    // n  :  链表1长度减去链表2长度的值
    cur1 = n > 0 ? head1 : head2; // 谁长，谁的头变成cur1
    cur2 = cur1 == head1 ? head2 : head1; // 谁短，谁的头变成cur2
    //长链表先走差值步
    n = Math.abs(n);
    while (n != 0) {
        n--;
        cur1 = cur1.next;
    }
    while (cur1 != cur2) {
        cur1 = cur1.next;
        cur2 = cur2.next;
    }
    return cur1;
}

// 两个有环链表，返回第一个相交节点，如果不想交返回null
//两个有环链表的三种情况：
//1.相交于入环节点或环外，loop1 == loop2，和环没有任何关系或者入环节点相交，直接当做无环相交
//2.不相交
//3.环内相交，loop走一圈，如果遇到了loop2，则环内相交，否则不相交
public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
    Node cur1 = null;
    Node cur2 = null;
    //相交入环节点或环外
    if (loop1 == loop2) {
        cur1 = head1;
        cur2 = head2;
        int n = 0;
        while (cur1 != loop1) {
            n++;
            cur1 = cur1.next;
        }
        while (cur2 != loop2) {
            n--;
            cur2 = cur2.next;
        }
        cur1 = n > 0 ? head1 : head2;
        cur2 = cur1 == head1 ? head2 : head1;
        n = Math.abs(n);
        while (n != 0) {
            n--;
            cur1 = cur1.next;
        }
        while (cur1 != cur2) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    } else {
        cur1 = loop1.next;
        while (cur1 != loop1) {
            //
            if (cur1 == loop2) {
                return loop1;
            }
            cur1 = cur1.next;
        }
        return null;
    }
}

二叉树

先序：任何子树的处理顺序都是，先头节点、再左子树、然后右子树

中序：任何子树的处理顺序都是，先左子树、再头节点、然后右子树

后序：任何子树的处理顺序都是，先左子树、再右子树、然后头节点

1）理解递归序

2）先序、中序、后序都可以在递归序的基础上加工出来

3）第一次到达一个节点就打印就是先序、第二次打印即中序、第三次即后序

// 实际上就是递归序
// 先序打印所有节点
public static void pre(Node head) {
    if (head == null) {
        return;
    }
    System.out.println(head.value);
    pre(head.left);
    pre(head.right);
}

// 中序打印所有节点
public static void in(Node head) {
    if (head == null) {
        return;
    }
    in(head.left);
    System.out.println(head.value);
    in(head.right);
}

// 后序打印所有节点
public static void pos(Node head) {
    if (head == null) {
        return;
    }
    pos(head.left);
    pos(head.right);
    System.out.println(head.value);
}

//用非递归的方式实现
//先序
//头结点压入栈，然后对栈实现pop弹出并打印，然后依次压入弹出的右、左结点
//入栈顺序：头-右-左 出栈顺序：头-左-右
public static void pre(Node head) {
    System.out.print("pre-order: ");
    if (head != null) {
        Stack<Node> stack = new Stack<Node>();
        stack.add(head);
        while (!stack.isEmpty()) {
            head = stack.pop();
            System.out.print(head.value + " ");
            if (head.right != null) {
                stack.push(head.right);
            }
            if (head.left != null) {
                stack.push(head.left);
            }
        }
    }
    System.out.println();
}

//非递归的中序遍历
//压入每个结点的左结点，压完时弹出栈，并打印，然后压入它的右结点，继续遍历右结点的左树
//入栈顺序：头-左-左 出栈顺序：左-左-头
public static void in(Node head) {
    System.out.print("in-order: ");
    if (head != null) {
        Stack<Node> stack = new Stack<Node>();
        while (!stack.isEmpty() || head != null) {
            if (head != null) {
                stack.push(head);
                head = head.left;
            } else {
                head = stack.pop();
                System.out.print(head.value + " ");
                head = head.right;
            }
        }
    }
    System.out.println();
}

//非递归的后序遍历
//头结点压入栈，然后对栈实现pop弹出并打印，然后依次压入弹出的左、右结点（如果是这种情况，则会出现后序遍历的相反输出操作）
//所以只需要弄两个栈，一个栈弹出的内容压到第二个栈中，最后输出第二个栈的内容
//入栈顺序 头-左-右 出栈顺序：头-右-左 ->入第二个栈后顺序：左右头
public static void pos1(Node head) {
    System.out.print("pos-order: ");
    if (head != null) {
        Stack<Node> s1 = new Stack<Node>();
        Stack<Node> s2 = new Stack<Node>();
        s1.push(head);
        while (!s1.isEmpty()) {
            head = s1.pop();
            s2.push(head);
            if (head.left != null) {
                s1.push(head.left);
            }
            if (head.right != null) {
                s1.push(head.right);
            }
        }
        while (!s2.isEmpty()) {
            System.out.print(s2.pop().value + " ");
        }
    }
    System.out.println();
}

//只用一个栈实现非递归的后序遍历
public static void pos2(Node h) {
    System.out.print("pos-order: ");
    if (h != null) {
        Stack<Node> stack = new Stack<Node>();
        //h用于记录上一个打印的节点
        stack.push(h);
        Node c = null;
        while (!stack.isEmpty()) {
            c = stack.peek();
            //如果h不是c的左右节点，代表c的左右节点没处理过，那么先压入左树处理
            if (c.left != null && h != c.left && h != c.right) {
                stack.push(c.left);
            //如果h处于c的左节点，并且c的右节点不为空，压入右树处理
            } else if (c.right != null && h != c.right) {
                stack.push(c.right);
            } else {
                //c的左右节点已经处理过了，打印c节点
                System.out.print(stack.pop().value + " ");
                h = c;
            }
        }
    }
    System.out.println();
}

//实现二叉树的按层遍历
public static void level(Node head) {
    if (head == null) {
        return;
    }
    Queue<Node> queue = new LinkedList<>();
    queue.add(head);
    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        System.out.println(cur.value);
        if (cur.left != null) {
            queue.add(cur.left);
        }
        if (cur.right != null) {
            queue.add(cur.right);
        }
    }
}

//求二叉树最宽的层有多少个节点
//思路：map中存储<Node,层数>,用一个变量来存储当前的层数，当队列中取出来的节点层数与当前层数不同时，则代表上一层遍历结束，计算上一层的层数
//宽度都是需要进入下一层时才开始计算，所以最后一层要单独计算
public static int maxWidthUseMap(Node head) {
    if (head == null) {
        return 0;
    }
    Queue<Node> queue = new LinkedList<>();
    queue.add(head);
    // key 在 哪一层，value
    HashMap<Node, Integer> levelMap = new HashMap<>();
    levelMap.put(head, 1);
    int curLevel = 1; // 当前你正在统计哪一层的宽度
    int curLevelNodes = 0; // 当前层curLevel层，宽度目前是多少
    int max = 0;
    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        int curNodeLevel = levelMap.get(cur);
        if (cur.left != null) {
            levelMap.put(cur.left, curNodeLevel + 1);
            queue.add(cur.left);
        }
        if (cur.right != null) {
            levelMap.put(cur.right, curNodeLevel + 1);
            queue.add(cur.right);
        }
        if (curNodeLevel == curLevel) {
            curLevelNodes++;
        } else {
            max = Math.max(max, curLevelNodes);
            curLevel++;
            curLevelNodes = 1;
        }
    }
    max = Math.max(max, curLevelNodes);
    return max;
}

//不使用hashMap计算二叉树最大宽度
//遍历，并且记录每次遍历的最右边的子节点，它就是下一层的最右边的节点，每次遍历一层，比较对象是否相等，相等则到达当前层最右边位置
public static int maxWidthNoMap(Node head) {
    if (head == null) {
        return 0;
    }
    Queue<Node> queue = new LinkedList<>();
    queue.add(head);
    Node curEnd = head; // 当前层，最右节点是谁
    Node nextEnd = null; // 下一层，最右节点是谁
    int max = 0;
    int curLevelNodes = 0; // 当前层的节点数
    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        if (cur.left != null) {
            queue.add(cur.left);
            nextEnd = cur.left;
        }
        if (cur.right != null) {
            queue.add(cur.right);
            nextEnd = cur.right;
        }
        curLevelNodes++;
        if (cur == curEnd) {
            max = Math.max(max, curLevelNodes);
            curLevelNodes = 0;
            curEnd = nextEnd;
        }
    }
    return max;
}

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

1）可以用先序或者中序或者后序或者按层遍历，来实现二叉树的序列化

2）用了什么方式序列化，就用什么样的方式反序列化

//先序-序列化  不要忽略空，每个节点都有左右两个NULL值
public static void pres(Node head, Queue<String> ans) {
    if (head == null) {
        ans.add(null);
    } else {
        ans.add(String.valueOf(head.value));
        pres(head.left, ans);
        pres(head.right, ans);
    }
}

//先序--反序列化
public static Node preb(Queue<String> prelist) {
    String value = prelist.poll();
    if (value == null) {
        return null;
    }
    Node head = new Node(Integer.valueOf(value));
    head.left = preb(prelist);
    head.right = preb(prelist);
    return head;
}

//按层遍历序列化
public static Queue<String> levelSerial(Node head) {
    Queue<String> ans = new LinkedList<>();
    if (head == null) {
        ans.add(null);
    } else {
        //加入队列时序列化
        ans.add(String.valueOf(head.value));
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(head);
        while (!queue.isEmpty()) {
            head = queue.poll();
            if (head.left != null) {
                ans.add(String.valueOf(head.left.value));
                queue.add(head.left);
            } else {
                //左节点等于空，加序列化，不加队列
                ans.add(null);
            }
            if (head.right != null) {
                ans.add(String.valueOf(head.right.value));
                queue.add(head.right);
            } else {
                //右节点等于空，加序列化，不加队列
                ans.add(null);
            }
        }
    }
    return ans;
}

二叉树结构如下定义：
Class Node {
  V value;
  Node left;
  Node right;
  Node parent;
}
给你二叉树中的某个节点，返回该节点的中序遍历的后继节点
     1
  2     3
4  5  6   7
中序遍历：4->2->5->1->6->3->7
4的后继节点是2

public static Node getSuccessorNode(Node node) {
    if (node == null) {
        return node;
    }
    if (node.right != null) {
        //如果有右树，找到它右树的最左节点
        return getLeftMost(node.right);
    } else { // 无右子树，循环找到node节点是父...节点的左侧时，返回
        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 node;
    }
    while (node.left != null) {
      node = node.left;
    }
    return node;
  }

请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。
此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。 
如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。 
给定一个输入参数N，代表纸条都从下边向上方连续对折N次。 请从上到下打印所有折痕的方向。 
例如:N=1时，打印: down N=2时，打印: down down up 

思路：等于一个二叉树，头结点down、左树全是down、右树全是up

// 递归过程，来到了某一个节点，
// i是节点的层数，N一共的层数，down == true  凹    down == false 凸
//printProcess(1, N, true);
public static void printProcess(int i, int N, boolean down) {
    //通过层数进行递归
    if (i > N) {
        return;
    }
    printProcess(i + 1, N, true);
    //递归的中序遍历
    System.out.println(down ? "凹 " : "凸 ");
    printProcess(i + 1, N, false);
}

二叉树的递归套路

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

1	给定一棵二叉树的头节点head，返回这颗二叉树是不是平衡二叉树

/*
思路：
  1.左/右树是否平衡
  2.左/右树的高度是否超过1
*/
// 左、右要求一样，Info 信息返回的结构体
public static class Info {
    public boolean isBalaced;
    public int height;

    public Info(boolean b, int h) {
        isBalaced = b;
        height = h;
    }
}

//判断是否是一颗平衡二叉树
//左树平衡、右树平衡、左右树高度相差不超过1
public static Info process2(Node X) {
    if (X == null) {
        return new Info(true, 0);
    }
    Info leftInfo = process2(X.left);
    Info rightInfo = process2(X.right);
    int height = Math.max(leftInfo.height, rightInfo.height) + 1;
    boolean isBalanced = true;
    if (!leftInfo.isBalaced || !rightInfo.isBalaced || Math.abs(leftInfo.height - rightInfo.height) > 1) {
        isBalanced = false;
    }
    return new Info(isBalanced, height);
}

1	给定一棵二叉树的头节点head，任何两个节点之间都存在距离,返回整棵二叉树的最大距离

/*
  思路：
  1.与X无关：
      左树/右树的最大距离
  2.与X有关：
      左树的高度 + 右树的高度 + 1
  3.从左/右树要得到的信息：
      左/右树的高度、最大距离。
*/
public static class Info {
    public int maxDistance;
    public int height;

    public Info(int dis, int h) {
        maxDistance = dis;
        height = h;
    }
}

//当前树的最大高度 = Max(左树,右树)高度 + 1
//当前树最大距离 = Max ( Max(左树,右树)距离, 左树高度+右树高度+1)
public static Info process(Node X) {
    if (X == null) {
        return new Info(0, 0);
    }
    Info leftInfo = process(X.left);
    Info rightInfo = process(X.right);
    //左右树最大高度+1
    int height = Math.max(leftInfo.height, rightInfo.height) + 1;
    //左右数高度+1 || 左树最大距离 || 右树最大距离  三者求max
    int maxDistance = Math.max(
        Math.max(leftInfo.maxDistance, rightInfo.maxDistance),
        leftInfo.height + rightInfo.height + 1);
    return new Info(maxDistance, height);
}

1 2	给定一棵二叉树的头节点head，返回这颗二叉树中最大的二叉搜索子树的节点数量

/*
 思路：
   1.与X无关：
     1.1 左/右树是否是二叉搜索树
     1.2 左/右树的子树有多少个二叉搜索树节点
   2.与X相关：
     2.1 左树的最大值是否小于X
     2.2 右树的最小值是否大于X
*/
public static class Info {
    public boolean isAllBST;
    //最大的搜索二叉树节点数量
    public int maxSubBSTSize;
    public int min;
    public int max;

    public Info(boolean is, int size, int mi, int ma) {
        isAllBST = 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 min = X.value;
    int max = X.value;
  
    //如果左树不为空
    if(leftInfo != null) {
        //取X和左树的min、max的最大值，最小值
        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(maxSubBSTSize, rightInfo.maxSubBSTSize);
    }
    boolean isAllBST = false;

  //结点也是搜索二叉树的一部分
    if(
        // 左树整体需要是搜索二叉树
        (  leftInfo == null ? true : leftInfo.isAllBST    )
        &&
        (  rightInfo == null ? true : rightInfo.isAllBST    )
        &&
        // 左树最大值<x
        (leftInfo == null ? true : leftInfo.max < X.value)
        &&
        (rightInfo == null ? true : rightInfo.min > X.value)
    ) {
    //取左树的max + 右树的max + 1
        maxSubBSTSize = 
            (leftInfo == null ? 0 : leftInfo.maxSubBSTSize)
            +
            (rightInfo == null ? 0 : rightInfo.maxSubBSTSize)
            +
            1;
        //设置该节点及子树都是搜索二叉树
        isAllBST = true;
    }

派对的最大快乐值
这个公司现在要办party，你可以决定哪些员工来，哪些员工不来，规则：
1.如果某个员工来了，那么这个员工的所有直接下级都不能来
2.派对的整体快乐值是所有到场员工快乐值的累加
3.你的目标是让派对的整体快乐值尽量大
给定一棵多叉树的头节点boss，请返回派对的最大快乐值。

/*
思路：
1.X不发请柬：
  1.1 X/happy = 0
  1.2 累加各个max(下层员工来的maxHappy, 不来的maxHappy)
2.X发请柬：
  2.1 X的快乐值 x.happy
  2.2 每个直接下层员工不来，累加他们的最大快乐值
*/

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 Info process2(Employee x) 
    //基层员工，最底层，没有下级节点
    if (x.nexts.isEmpty()) {
        return new Info(x.happy, 0);
    }
  //X来的当前快乐值
    int yes = x.happy;
  //不来为0
    int no = 0;
    for (Employee next : x.nexts) {
        Info nextInfo = process2(next);
        //当X来，则累加它子树不来的max最大快乐值
        yes += nextInfo.no;
        //当X不来，则累加子树Max(来/不来)的最大快乐值
        no += Math.max(nextInfo.yes, nextInfo.no);
    }
    return new Info(yes, no);
}

给定一棵二叉树的头节点head，返回这颗二叉树中最大的二叉搜索子树的头节点

思路：
1.与X无关：
  1.1 Max（左树的答案，右树的答案）
  1.2 左右树最搜索二叉树头结点
  1.3 搜索二叉树的结点数量
2.与X有关：
  2.1 左树的Max<X<右树的Min
  2.2 左右树的Max、Min

// 每一棵子树
public static class Info {
    //最大搜二叉树结点
    public Node maxSubBSTHead;
    //结点数量
    public int maxSubBSTSize;
    public int min;
    public int max;

    public Info(Node h, int size, int mi, int ma) {
        maxSubBSTHead = h;
        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 min = X.value;
    int max = X.value;
    Node maxSubBSTHead = null;
    int maxSubBSTSize = 0;
    if (leftInfo != null) {
        min = Math.min(min, leftInfo.min);
        max = Math.max(max, leftInfo.max);
        maxSubBSTHead = leftInfo.maxSubBSTHead;
        maxSubBSTSize = leftInfo.maxSubBSTSize;
    }
    if (rightInfo != null) {
        min = Math.min(min, rightInfo.min);
        max = Math.max(max, rightInfo.max);
        if (rightInfo.maxSubBSTSize > maxSubBSTSize) {
            maxSubBSTHead = rightInfo.maxSubBSTHead;
            maxSubBSTSize = rightInfo.maxSubBSTSize;
        }
    }
    //左树整体是否是搜索二叉树
    if ((leftInfo == null ? true : (leftInfo.maxSubBSTHead == X.left && leftInfo.max < X.value))
        && (rightInfo == null ? true : (rightInfo.maxSubBSTHead == X.right && rightInfo.min > X.value))) {
        maxSubBSTHead = X;
        maxSubBSTSize = (leftInfo == null ? 0 : leftInfo.maxSubBSTSize)
            + (rightInfo == null ? 0 : rightInfo.maxSubBSTSize) + 1;
    }
    return new Info(maxSubBSTHead, maxSubBSTSize, min, max);
}

给定一棵二叉树的头节点head，返回这颗二叉树中是不是完全二叉树

思路：
1.X是否是满二叉树
  1.1 左树的高度=右树的高度，并且都是满二叉树
2.X的最后一层没有越过左树
  2.1 左树是完全二叉树，右树是满二叉树，并且左树高度比右树高度大1
3.X的最后一层刚好填满左树
  3.1 左/右树都是满二叉树，并且左树高度比右树高度大1
4.X的最后一层越过左树，来到右树
  4.1 左树是完全二叉树，右树是满二叉树，并且左树高度比右树高度大1

// 对每一棵子树，是否是满二叉树、是否是完全二叉树、高度
public static class Info {
    //是否是满二叉树
    public boolean isFull;
    //是否是完全二叉树
    public boolean isCBT;
    //高度
    public int height;

    public Info(boolean full, boolean cbt, int h) {
        isFull = full;
        isCBT = cbt;
        height = h;
    }
}

public static Info process(Node X) {
    if (X == null) {
        //空树-满二叉树-完全二叉树-高度0
        return new Info(true, true, 0);
    }
    Info leftInfo = process(X.left);
    Info rightInfo = process(X.right);
  
    
    int height = Math.max(leftInfo.height, rightInfo.height) + 1;

  //左树满、右树满、并且高度相同
    boolean isFull = leftInfo.isFull 
        && 
        rightInfo.isFull 
        && leftInfo.height == rightInfo.height;


    boolean isCBT = false;
    if (isFull) {
        isCBT = true;
    } else { // 以x为头整棵树，不满
        //左右树都是完全二叉树才进行判断逻辑
        if (leftInfo.isCBT && rightInfo.isCBT) {
            //左树是完全二叉树、右树是满的、并且高度大1
            if (leftInfo.isCBT 
                && rightInfo.isFull 
                && leftInfo.height == rightInfo.height + 1) {
                isCBT = true;
            }
            //左树是满的、右树也是满的，并且高度大1
            if (leftInfo.isFull 
                && 
                rightInfo.isFull 
                && leftInfo.height == rightInfo.height + 1) {
                isCBT = true;
            }
            //左树是满的，右树是完全二叉树，并且高度相同
            if (leftInfo.isFull 
                && rightInfo.isCBT && leftInfo.height == rightInfo.height) {
                isCBT = true;
            }
        }
    }
    return new Info(isFull, isCBT, height);
}

贪心算法

1）最自然智慧的算法

2）用一种局部最功利的标准，总是做出在当前看来是最好的选择

3）难点在于证明局部最功利的标准可以得到全局最优解

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

1
2
3

给定一个由字符串组成的数组strs，
必须把所有的字符串拼接起来，
返回所有可能的拼接结果中，字典序最小的结果

//暴力递归
// strs里放着所有的字符串
// 已经使用过的字符串的下标，在use里登记了，不要再使用了
// 之前使用过的字符串，拼接成了-> path
// 用all收集所有可能的拼接结果
public static void process(String[] strs, HashSet<Integer> use, String path, ArrayList<String> all) {
    //递归到底，所有index都是用了，统计答案
    if (use.size() == strs.length) {
        all.add(path);
    } else {
        //循环递归 每个str都当做第一个index递归一次，然后统计完还原现场
        for (int i = 0; i < strs.length; i++) {
            if (!use.contains(i)) {
                //深度优先遍历，加完使用完还原现场删掉它
                use.add(i);
                process(strs, use, path + strs[i], all);
                use.remove(i);
            }
        }
    }
}

//贪心算法
//把每个字母看做是K进制的数字，进行比较，通过证明得到以下比较
public static class MyComparator implements Comparator<String> {
    @Override
    public int compare(String a, String b) {
        return (a + b).compareTo(b + a);
    }
}

public static String lowestString2(String[] strs) {
    if (strs == null || strs.length == 0) {
        return "";
    }
    //贪心，排完序之后进行拼接的肯定是最小的
    Arrays.sort(strs, new MyComparator());
    String res = "";
    for (int i = 0; i < strs.length; i++) {
        res += strs[i];
    }
    return res;
}

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

//暴力递归
// 还剩什么会议都放在programs里
// done 之前已经安排了多少会议，数量
// timeLine目前来到的时间点是什么

// 目前来到timeLine的时间点，已经安排了done多的会议，剩下的会议programs可以自由安排
// 返回能安排的最多会议数量
public static int process(Program[] programs, int done, int timeLine) {
    if (programs.length == 0) {
        return done;
    }
    // 还有会议可以选择
    int max = done;
    // 当前安排的会议是什么会，每一个都枚举
    //每个会议都当开头，timeLine之后接着筛选合适的会议
    for (int i = 0; i < programs.length; i++) {
        if (programs[i].start >= timeLine) {
            //移除i位置上的元素，拷贝新数组，所以不需要还原现场
            Program[] next = copyButExcept(programs, i);
            max = Math.max(max, process(next, done + 1, programs[i].end));
        }
    }
    return max;
}

//贪心算法
//按照结束时间排序，结束时间最早的，优先进安排
public static int bestArrange2(Program[] programs) {
    Arrays.sort(programs, new ProgramComparator());
    int timeLine = 0;
    int result = 0;
    for (int i = 0; i < programs.length; i++) {
        if (timeLine <= programs[i].start) {
            result++;
            timeLine = programs[i].end;
        }
    }
    return result;
}

public static class ProgramComparator implements Comparator<Program> {
    @Override
    public int compare(Program o1, Program o2) {
        return o1.end - o2.end;
    }
}

给定一个字符串str，只由‘X’和‘.’两种字符构成。
‘X’表示墙，不能放灯，也不需要点亮
‘.’表示居民点，可以放灯，需要点亮
如果灯放在i位置，可以让i-1，i和i+1三个位置被点亮
返回如果点亮str中所有需要点亮的位置，至少需要几盏灯

// str[index....]位置，自由选择放灯还是不放灯
// str[0..index-1]位置呢？已经做完决定了，那些放了灯的位置，存在lights里
// 要求选出能照亮所有.的方案，并且在这些有效的方案中，返回最少需要几个灯
public static int process(char[] str, int index, HashSet<Integer> lights) {
    if (index == str.length) { // 结束的时候
        for (int i = 0; i < str.length; i++) {
            // 当前位置是点的话，判断当前位置及左右是否有灯，若无则无效答案
            if (str[i] != 'X') { 
                if (!lights.contains(i - 1) 
                    && !lights.contains(i) 
                    && !lights.contains(i + 1)) {
                    return Integer.MAX_VALUE;
                }
            }
        }
        return lights.size();
    } else { // str还没结束
        // i   X  .
        //当i位置不放灯的递归答案
        int no = process(str, index + 1, lights);
        int yes = Integer.MAX_VALUE;
        //当i位置是'.'，并且放灯的答案
        if (str[index] == '.') {
            lights.add(index);
            yes = process(str, index + 1, lights);
            lights.remove(index);
        }
        //求最小值
        return Math.min(no, yes);
    }
}

//贪心算法
// i位置为 X -->i = i+1
// i位置为i时：
//  -> i+1位置为X --> i放灯, i=i+2
//  -> i+1位置为i
//     -> i+2位置为X-->i+1放灯，i=i+3
//     -> i+2位置为i-->i+1放灯，i=i+3
public static int minLight2(String road) {
    char[] str = road.toCharArray();
    int index = 0;
    int light = 0;
    while (index < str.length) {
        if (str[index] == 'X') {
            index++;
        } else { // i -> .
            //不管什么情况，都需要找个位置放灯，然后移动下标
            light++;
            if (index + 1 == str.length) {
                break;
            } else {
                if (str[index + 1] == 'X') {
                    index = index + 2;
                } else {
                    index = index + 3;
                }
            }
        }
    }
    return light;
}

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

例如,给定数组{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 static int process(int[] arr, int pre) {
    if (arr.length == 1) {
        return pre;
    }
    int ans = Integer.MAX_VALUE;
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            ans = Math.min(ans, process(copyAndMergeTwo(arr, i, j), pre + arr[i] + arr[j]));
        }
    }
    return ans;
}

//贪心算法
//哈夫曼树，数据压入小根堆中，依次弹出两个数相加（累加到sum），并再次压入栈中，一直到栈中只剩下一个元素
public static int lessMoney2(int[] arr) {
    PriorityQueue<Integer> pQ = new PriorityQueue<>();
    for (int i = 0; i < arr.length; i++) {
        pQ.add(arr[i]);
    }
    int sum = 0;
    int cur = 0;
    while (pQ.size() > 1) {
        cur = pQ.poll() + pQ.poll();
        sum += cur;
        pQ.add(cur);
    }
    return sum;
}

输入: 正数数组costs、正数数组profits、正数K、正数M
costs[i]表示i号项目的花费
profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
K表示你只能串行的最多做k个项目
M表示你初始的资金
说明: 每做完一个项目，马上获得的收益，可以支持你去做下一个项目。不能并行的做项目。
输出：你最后获得的最大钱数。

贪心思路：
花费: 1 1 4 5     假设K = 2，M = 1
利润: 3 1 3 2
定义一个小根堆，按照花费排序，这个小根堆认为是锁住的项目：(1,1),(1,3),(4,3),(5,2)
定义一个大根堆，按照利润排序，这个大根堆认为是解锁的项目，那么M = 1 能够解锁 (1,1),(1,3)
将解锁的(1,1),(1,3)放进大根堆，取出堆顶的(1,3)项目做，做完之后本金+利润 M = 4
这时候解锁了(4,3)，再放进大根堆，取出堆顶的项目(4,3)，周而复始，做够K个项目

//贪心算法
//按照花费放进小根堆中，按照利润放到大根堆中
public static int findMaximizedCapital(int K, int W, int[] Profits, int[] Capital) {
    //小根堆
    PriorityQueue<Program> minCostQ = new PriorityQueue<>(new MinCostComparator());
    //大根堆
    PriorityQueue<Program> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());
    for (int i = 0; i < Profits.length; i++) {
        minCostQ.add(new Program(Profits[i], Capital[i]));
    }
    for (int i = 0; i < K; i++) {
        while (!minCostQ.isEmpty() && minCostQ.peek().c <= W) {
            maxProfitQ.add(minCostQ.poll());
        }
        if (maxProfitQ.isEmpty()) {
            return W;
        }
        W += maxProfitQ.poll().p;
    }
    return W;
}

public static class Program {
    public int p;
    public int c;

    public Program(int p, int c) {
        this.p = p;
        this.c = c;
    }
}

并查集

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 HashMap<V, Node<V>> nodes;
//每个样本节点对应的父样本节点
public HashMap<Node<V>, Node<V>> parents;
//样本头节点和它底下的链路数量
public HashMap<Node<V>, Integer> sizeMap;

一开始都是自己指向自己,若属于一个并查集，最终指向的parent节点一定是同一个
通过parent节点是否相等判断属于同一个并查集
通过改变parent节点的指向，O(1)的代价合并两个并查集
{a},{b},{c},{d} -> union(a,b) (c,d) -> {a,b} {c,d} -> union(a,c) -> {a,b,c,d}

public class Code01_UnionFind {

    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) {
            nodes = new HashMap<>();
            parents = new HashMap<>();
            sizeMap = new HashMap<>();
            for (V cur : values) {
                Node<V> node = new Node<>(cur);
                nodes.put(cur, node);
                parents.put(node, node);
                sizeMap.put(node, 1);
            }
        }
    //扁平化链表，调用该方法次数越多，它的时间复杂度越低，因为链表约扁平
        // 从点cur开始，一直往上找，找到不能再往上的代表点，返回
        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);
            }
            // cur头节点
            while (!path.isEmpty()) {
                parents.put(path.pop(), cur);
            }
            return cur;
        }

        public boolean isSameSet(V a, V b) {
            if (!nodes.containsKey(a) || !nodes.containsKey(b)) {
                return false;
            }
            return findFather(nodes.get(a)) == findFather(nodes.get(b));
        }

        public void union(V a, V b) {
            if (!nodes.containsKey(a) || !nodes.containsKey(b)) {
                return;
            }
            Node<V> aHead = findFather(nodes.get(a));
            Node<V> bHead = findFather(nodes.get(b));
            if (aHead != bHead) {
                int aSetSize = sizeMap.get(aHead);
                int bSetSize = sizeMap.get(bHead);
                //数量短的链表合并到数量长的链表中，降低扁平化的循环次数
                Node<V> big = aSetSize >= bSetSize ? aHead : bHead;
                Node<V> small = big == aHead ? bHead : aHead;
                parents.put(small, big);
                sizeMap.put(big, aSetSize + bSetSize);
                sizeMap.remove(small);
            }
        }
    }
}

// (1,10,13) (2,10,37) (400,500,37)
// 如果两个user，a字段一样、或者b字段一样、或者c字段一样，就认为是一个人
// 请合并users，返回合并之后的用户数量
public static int mergeUsers(List<User> users) {
    UnionSet<User> unionFind = new UnionSet<>(users);
    HashMap<String, User> mapA = new HashMap<>();
    HashMap<String, User> mapB = new HashMap<>();
    HashMap<String, User> mapC = new HashMap<>();
    for(User user : users) {
        if(mapA.containsKey(user.a)) {
            unionFind.union(user, mapA.get(user.a));
        }else {
            mapA.put(user.a, user);
        }
        if(mapB.containsKey(user.b)) {
            unionFind.union(user, mapB.get(user.b));
        }else {
            mapB.put(user.b, user);
        }
        if(mapC.containsKey(user.c)) {
            unionFind.union(user, mapC.get(user.c));
        }else {
            mapC.put(user.c, user);
        }
    }
    // 向并查集询问，合并之后，还有多少个集合？
    return unionFind.getSetNum();
}

图

1）由点的集合和边的集合构成

2）虽然存在有向图和无向图的概念，但实际上都可以用有向图来表达

3）边上可能带有权值

// 点结构的描述  A  0
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<>();
    }
}

//边
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;
    }
}

//图
public class Graph {
    //<编号，点>
  public HashMap<Integer, Node> nodes;
    //边
  public HashSet<Edge> edges;
  
  public Graph() {
    nodes = new HashMap<>();
    edges = new HashSet<>();
  }
}

//把各种数据结构的图表达形式转换成固定的算法解析的格式
// matrix 所有的边
// N*3 的矩阵
// [weight, from节点上面的值，to节点上面的值]
public static Graph createGraph(Integer[][] matrix) {
    Graph graph = new Graph();
    for (int i = 0; i < matrix.length; i++) { 
        // matrix[0][0], matrix[0][1]  matrix[0][2]
        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);
        fromNode.nexts.add(toNode);
        fromNode.out++;
        toNode.in++;
        fromNode.edges.add(newEdge);
        graph.edges.add(newEdge);
    }
    return graph;
}

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

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

// 从node出发，进行宽度优先遍历
// SET 过滤重复的节点
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 : cur.nexts) {
            if (!set.contains(next)) {
                set.add(next);
                queue.add(next);
            }
        }
    }
}

//深度优先遍历
//先把节点压入栈中，输出，然后遍历它的next节点，发现没遍历过则压入原节点和next节点（并打印），break
//等next节点的深度遍历完后，最后重新弹出原节点继续遍历没被遍历完的next节点，周而复始
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;
            }
        }
    }
}

图的拓扑排序算法

1）在图中找到所有入度为0的点输出
2）把所有入度为0的点在图中删掉，继续找入度为0的点输出，周而复始
3）图的所有点都被删除后，依次输出的顺序就是拓扑排序

要求：有向图且其中没有环
应用：事件安排、编译顺序

// directed graph and no loop
public static List<Node> sortedTopology(Graph graph) {
    // key：某一个node
    // value：剩余的入度
    HashMap<Node, Integer> inMap = new HashMap<>();
    // 剩余入度为0的点，才能进这个队列
    Queue<Node> zeroInQueue = new LinkedList<>();

    for (Node node : graph.nodes.values()) {
        inMap.put(node, node.in);
        if (node.in == 0) {
            zeroInQueue.add(node);
        }
    }
    // 拓扑排序的结果，依次加入result
    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;
}

最小权重生成树算法之Kruskal

1）总是从权值最小的边开始考虑，依次考察权值依次变大的边
2）当前的边要么进入最小生成树的集合，要么丢弃
3）如果当前的边进入最小生成树的集合中不会形成环，就要当前边
4）如果当前的边进入最小生成树的集合中会形成环，就不要当前边
5）考察完所有边之后，最小生成树的集合也得到了

//所有边权重排序，并依次使用并查集判断是否需要使用边来合并from和to的节点
//如果是无向图，因为按照集合边淘汰原则，丢失了（无向边=来回的双向边）双向边的一部分，所以需要补边
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) { // M 条边
      priorityQueue.add(edge);  // O(logM)
    }
    Set<Edge> result = new HashSet<>();
    while (!priorityQueue.isEmpty()) { // M 条边
      Edge edge = priorityQueue.poll(); // O(logM)
      if (!unionFind.isSameSet(edge.from, edge.to)) { // O(1)
        result.add(edge);
        unionFind.union(edge.from, edge.to);
      }
    }
    return result;
  }

最小权重生成树算法之Prim

1）可以从任意节点出发来寻找最小生成树
2）某个点加入到被选取的点中后，解锁这个点出发的所有新的边
3）在所有解锁的边中选最小的边，然后看看这个边会不会形成环
4）如果会，不要当前边，继续考察剩下解锁的边中最小的边，重复3）
5）如果不会，要当前边，将该边的指向点加入到被选取的点中，重复2）
6）当所有点都被选取，最小生成树就得到了

public static Set<Edge> primMST(Graph graph) {
    // 解锁的边进入小根堆
    PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());

    // 哪些点被解锁出来了
    HashSet<Node> nodeSet = new HashSet<>();
    Set<Edge> result = new HashSet<>(); // 依次挑选的的边在result里
    
    //for循环主要是为了防止森林，多个图
    for (Node node : graph.nodes.values()) { // 随便挑了一个点
        // node 是开始点
        if (!nodeSet.contains(node)) {
            nodeSet.add(node);
            for (Edge edge : node.edges) { // 由一个点，解锁所有相连的边
                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) {
                        priorityQueue.add(nextEdge);
                    }
                }
            }
        }
        // break;
    }
    return result;
}

Dijkstra算法

1）Dijkstra算法必须指定一个源点
2）生成一个源点到各个点的最小距离表，一开始只有一条记录，即原点到自己的最小距离为0，源点到其他所有点的最小距离都为正无穷大
3）从距离表中拿出没拿过记录里的最小记录，通过这个点发出的边，更新源点到各个点的最小距离表，不断重复这一步
4）源点到所有的点记录如果都被拿过一遍，过程停止，最小距离表得到了

public static HashMap<Node, Integer> dijkstra1(Node from) {
    // 从head出发到所有点的最小距离
    // key : 从head出发到达key
    // value : 从head出发到达key的最小距离
    // 如果在表中，没有T的记录，含义是从head出发到T这个点的距离为正无穷
    HashMap<Node, Integer> distanceMap = new HashMap<>();
    distanceMap.put(from, 0);
    // 已经求过距离的节点，存在selectedNodes中，以后再也不碰
    HashSet<Node> selectedNodes = new HashSet<>();
    // from 0
    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 + edge.weight));
            }
        }
        selectedNodes.add(minNode);
        minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
    }
    return distanceMap;
}

public static Node getMinDistanceAndUnselectedNode(
    HashMap<Node, Integer> distanceMap, 
    HashSet<Node> touchedNodes) {
    Node minNode = null;
    int minDistance = Integer.MAX_VALUE;
    for (Entry<Node, Integer> entry : distanceMap.entrySet()) {
        Node node = entry.getKey();
        int distance = entry.getValue();
        if (!touchedNodes.contains(node) && distance < minDistance) {
            minNode = node;
            minDistance = distance;
        }
    }
    return minNode;
}

//改进：优化每个节点都需要遍历获取最小路径的问题
public static Node getMinDistanceAndUnselectedNode(
    HashMap<Node, Integer> distanceMap, 
    HashSet<Node> touchedNodes) {
    Node minNode = null;
    int minDistance = Integer.MAX_VALUE;
    for (Entry<Node, Integer> entry : distanceMap.entrySet()) {
        Node node = entry.getKey();
        int distance = entry.getValue();
        if (!touchedNodes.contains(node) && distance < minDistance) {
            minNode = node;
            minDistance = distance;
        }
    }
    return minNode;
}

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; // 实际的堆结构
    // key 某一个node， value 上面堆中的位置
    private HashMap<Node, Integer> heapIndexMap;
    // key 某一个节点， value 从源节点出发到该节点的目前最小距离
    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;
    }

    // 有一个点叫node，现在发现了一个从源节点出发到达node的距离为distance
    // 判断要不要更新，如果需要的话，就更新
    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]);
        // free C++同学还要把原本堆顶节点析构，对java同学不必
        nodes[size - 1] = null;
        heapify(0, --size);
        return nodeRecord;
    }

    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;
        }
    }

    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;
    }
}

// 改进后的dijkstra算法
// 从head出发，所有head能到达的节点，生成到达每个节点的最小路径记录并返回
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，有明确的不需要继续进行递归的条件(base case)
3，有当得到了子问题的结果之后的决策过程
4，不记录每一个子问题的解

汉诺塔问题

1	打印n层汉诺塔从最左边移动到最右边的全部过程

//1.汉诺塔简单版本写法
public static void hanoi1(int n) {
    leftToRight(n);
}

// 请把1~N层圆盘 从左 -> 右
public static void leftToRight(int n) {
    if (n == 1) {
        System.out.println("Move 1 from left to right");
        return;
    }
    leftToMid(n - 1);
    System.out.println("Move " + n + " from left to right");
    midToRight(n - 1);
}

// 请把1~N层圆盘 从左 -> 中
public static void leftToMid(int n) {
    if (n == 1) {
        System.out.println("Move 1 from left to mid");
        return;
    }
    leftToRight(n - 1);
    System.out.println("Move " + n + " from left to mid");
    rightToMid(n - 1);
}

public static void rightToMid(int n) {
    if (n == 1) {
        System.out.println("Move 1 from right to mid");
        return;
    }
    rightToLeft(n - 1);
    System.out.println("Move " + n + " from right to mid");
    leftToMid(n - 1);
}

public static void midToRight(int n) {
    if (n == 1) {
        System.out.println("Move 1 from mid to right");
        return;
    }
    midToLeft(n - 1);
    System.out.println("Move " + n + " from mid to right");
    leftToRight(n - 1);
}

public static void midToLeft(int n) {
    if (n == 1) {
        System.out.println("Move 1 from mid to left");
        return;
    }
    midToRight(n - 1);
    System.out.println("Move " + n + " from mid to left");
    rightToLeft(n - 1);
}

public static void rightToLeft(int n) {
    if (n == 1) {
        System.out.println("Move 1 from right to left");
        return;
    }
    rightToMid(n - 1);
    System.out.println("Move " + n + " from right to left");
    midToLeft(n - 1);
}

/*思想:（from -> to）
  拆成三个大步：
    1.把N-1的圆盘移动到 other上
    2.把N的圆盘移动到to上
    3.把N-1的圆盘移动到to上（这步操作等于递归N-1的圆盘重新移动）
  移动的最优步数：(2^n -1)
*/
public static void hanoi2(int n) {
    if (n > 0) {
        func(n, "left", "right", "mid");
    }
}

// 1~i 圆盘 目标是from -> to， other是另外一个
public static void func(int N, String from, String to, String other) {
    if (N == 1) { // base
        System.out.println("Move 1 from " + from + " to " + to);
    } else {
        func(N - 1, from, other, to);
        System.out.println("Move " + N + " from " + from + " to " + to);
        func(N - 1, other, to, from);
    }
}

//非递归的版本
public static class Record {
    public boolean finish1;
    public int base;
    public String from;
    public String to;
    public String other;

    public Record(boolean f1, int b, String f, String t, String o) {
        finish1 = false;
        base = b;
        from = f;
        to = t;
        other = o;
    }
}

public static void hanoi3(int N) {
    if (N < 1) {
        return;
    }
    Stack<Record> stack = new Stack<>();
    stack.add(new Record(false, N, "left", "right", "mid"));
    while (!stack.isEmpty()) {
        Record cur = stack.pop();
        if (cur.base == 1) {
            System.out.println("Move 1 from " + cur.from + " to " + cur.to);
            if (!stack.isEmpty()) {
                stack.peek().finish1 = true;
            }
        } else {
            if (!cur.finish1) {
                stack.push(cur);
                stack.push(new Record(false, cur.base - 1, cur.from, cur.other, cur.to));
            } else {
                System.out.println("Move " + cur.base + " from " + cur.from + " to " + cur.to);
                stack.push(new Record(false, cur.base - 1, cur.other, cur.to, cur.from));
            }
        }
    }
}

逆序栈问题

1
2
3

给你一个栈，请你逆序这个栈，
不能申请额外的数据结构，
只能使用递归函数。

/*
思路：
1.先把栈底的元素拿出来
2.再递归调用函数依次拿出每次栈底的数据，重新push进去。二层递归嵌套
*/
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;
    }
}

子序列问题

1	打印一个字符串的全部子序列

/*
思路：
深度优先遍历，到了每个index判断index是否要拼接到path里，yes/no，一直到index==length时，添加进集合
*/
public static List<String> subs(String s) {
    char[] str = s.toCharArray();
    String path = "";
    List<String> ans = new ArrayList<>();
    process1(str, 0, ans, path);
    return ans;
}

// str固定，不变
// index此时来到的位置, 要  or 不要
// 如果index来到了str中的终止位置，把沿途路径所形成的答案，放入ans中
// 之前做出的选择，就是path
public static void process1(char[] str, int index, List<String> ans, String path) {
    if (index == str.length) {
        ans.add(path);
        return;
    }
    //不添加路径
    String no = path;
    process1(str, index + 1, ans, no);
    //拼接路径
    String yes = path + String.valueOf(str[index]);
    process1(str, index + 1, ans, yes);
}

1	打印一个字符串的全部子序列，要求不要出现重复字面值的子序列

// str  index  set

public static List<String> subsNoRepeat(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[] str, int index,
                            HashSet<String> set, String path) {
    if (index == str.length) {
        set.add(path);
        return;
    }
    String no = path;
    process2(str, index + 1, set, no);
    String yes = path + String.valueOf(str[index]);
    process2(str, index + 1, set, yes);
}

全排列问题

1	打印一个字符串的全部排列

/*
思路：index=0，大于等于index的元素都有机会和index的元素进行交换，做出不同的排列，index++，依次排，递归排完后还原现场，把交换的数据交换回来
*/
public static ArrayList<String> permutation(String str) {
    ArrayList<String> res = new ArrayList<>();
    if (str == null || str.length() == 0) {
        return res;
    }
    char[] chs = str.toCharArray();
    process(chs, 0, res);
    return res;
}

// str[0..i-1]已经做好决定的
// str[i...]都有机会来到i位置
// i终止位置，str当前的样子，就是一种结果 -> ans
public static void process(char[] str, int i, ArrayList<String> ans) {
    if (i == str.length) {
        ans.add(String.valueOf(str));
    }
    // 如果i没有终止，i...  都可以来到i位置
    for (int j = i; j < str.length; j++) { // j  i后面所有的字符都有机会
        swap(str, i, j);
        process(str, i + 1, ans);
        //还原交换现场
        swap(str, i, j);
    }
}

1	打印一个字符串的全部排列，要求不要出现重复的排列

/*
 思想：分支限界
 要交换的数值和index上的数值相同则跳过
*/
public static ArrayList<String> permutationNoRepeat(String str) {
    ArrayList<String> res = new ArrayList<>();
    if (str == null || str.length() == 0) {
        return res;
    }
    char[] chs = str.toCharArray();
    process2(chs, 0, res);
    return res;
}

// str[0..i-1]已经做好决定的
// str[i...]都有机会来到i位置
// i终止位置，str当前的样子，就是一种结果 -> ans
public static void process2(char[] str, int i, ArrayList<String> res) {
    if (i == str.length) {
        res.add(String.valueOf(str));
        return;
    }
    boolean[] visit = new boolean[26]; // visit[0 1 .. 25]
    for (int j = i; j < str.length; j++) {
        // str[j] = 'a'   -> 0   visit[0] -> 'a'

        // str[j] = 'z'   -> 25   visit[25] -> 'z'
        if (!visit[str[j] - 'a']) {

            visit[str[j] - 'a'] = true;
            swap(str, i, j);
            process2(str, i + 1, res);
            swap(str, i, j);
        }
    }
}

皇后问题

N皇后问题是指在N*N的棋盘上要摆N个皇后，
要求任何两个皇后不同行、不同列， 也不在同一条斜线上
给定一个整数n，返回n皇后的摆法有多少种。 
n=1，返回1
n=2或3，2皇后和3皇后问题无论怎么摆都不行，返回0
n=8，返回92

public static int num1(int n) {
    if (n < 1) {
        return 0;
    }
    // record[0] ?  record[1]  ?  record[2]
    int[] record = new int[n]; // record[i] -> i行的皇后，放在了第几列
    return process1(0, record, n);
}

// 潜台词：record[0..i-1]的皇后，任何两个皇后一定都不共行、不共列，不共斜线
// 目前来到了第i行
// record[0..i-1]表示之前的行，放了的皇后位置
// n代表整体一共有多少行  0~n-1行
// 返回值是，摆完所有的皇后，合理的摆法有多少种
public static int process1(int i, int[] record, int n) {
    if (i == n) { // 终止行
        return 1;
    }
    // 没有到终止位置，还有皇后要摆
    int res = 0;
    // 当前行在i行，尝试i行所有的列  -> j
    for (int j = 0; j < n; j++) { 
        // 当前i行的皇后，放在j列，会不会和之前(0..i-1)的皇后，不共行共列或者共斜线，
        // 如果是，认为有效
        // 如果不是，认为无效
        if (isValid(record, i, j)) {
            record[i] = j;
            res += process1(i + 1, record, n);
        }
    }
    return res;
}

// record[0..i-1]你需要看，record[i...]不需要看
// 返回i行皇后，放在了j列，是否有效
public static boolean isValid(int[] record, int i, int j) {
    for (int k = 0; k < i; k++) { // 之前的某个k行的皇后	
        //假设 a行b列的皇后  和 c行d列的皇后，他们之间的关系？
        //不能和列、左对角线、右对角线匹配上
        //由于概念已经定义，必然不共行，那么 b == d 时 共列
        // 若 |a - c| == |b - d| ，那么他们共斜线
        if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {
            return false;
        }
    }
    return true;
}

/*
N皇后的位运算优化，优化常数项，复杂度都相同。
*/
// 请不要超过32皇后问题
public static int num2(int n) {
    if (n < 1 || n > 32) {
        return 0;
    }
    // 如果你是13皇后问题，limit 最右13个1，其他都是0
    int limit = n == 32 ? -1 : (1 << n) - 1;
    return process2(limit, 0, 0, 0);
}

// limit 划定了问题的规模 -> 固定

// colLim 列的限制，1的位置不能放皇后，0的位置可以
// leftDiaLim 左斜线的限制，1的位置不能放皇后，0的位置可以
// rightDiaLim 右斜线的限制，1的位置不能放皇后，0的位置可以
public static int process2(
    int limit, 
    int colLim, 
    int leftDiaLim,
    int rightDiaLim) {
    
    // base case  要么有结果（相等），要么放不下皇后（pos=0不进循环，直接return）
    if (colLim == limit) { 
        return 1;
    }
    // 所有可以放皇后的位置，都在pos上
    // colLim | leftDiaLim | rightDiaLim   -> 总限制
    // ~ (colLim | leftDiaLim | rightDiaLim) -> 取反会产生一大堆左侧的1，
    //limit & (...) 可以把左侧的一坨0干扰，右侧每个1，可尝试
    int pos = limit & ( ~(colLim | leftDiaLim | rightDiaLim) );
    int mostRightOne = 0;
    int res = 0;
    while (pos != 0) {
        // 取取出pos中，最右侧的1来，剩下位置都是0
        mostRightOne = pos & (~pos + 1);
        pos = pos - mostRightOne;
        //累加计算的结果
        res += process2(limit, 
                        colLim | mostRightOne,
                        (leftDiaLim | mostRightOne) << 1,
                        (rightDiaLim | mostRightOne) >>> 1);
    }
    return res;
}

//两种皇后优化时间的对比
public static void main(String[] args) {
    int n = 10;

    long start = System.currentTimeMillis();
    System.out.println(num2(n));
    long end = System.currentTimeMillis();
    System.out.println("cost time: " + (end - start) + "ms");

    start = System.currentTimeMillis();
    System.out.println(num1(n));
    end = System.currentTimeMillis();
    System.out.println("cost time: " + (end - start) + "ms");
}

动态规划

从左往右的尝试模型：

规定1和A对应、2和B对应、3和C对应...
那么一个数字字符串比如"111”就可以转化为:
"AAA"、"KA"和"AK"
给定一个只有数字字符组成的字符串str，返回有多少种转化结果

/*
思路：找到BaseCase 递归（i、i+1），下个递归是（i+1、i+2）
分支限界 i+1 <str.length , i+1 < 26
*/
public static int number(String str) {
    if (str == null || str.length() == 0) {
        return 0;
    }
    return process(str.toCharArray(), 0);
}

// str[0...i-1]已经转化完了，固定了
// i之前的位置，如何转化已经做过决定了, 不用再关心
// i... 有多少种转化的结果
public static int process(char[] str, int i) {
    if (i == str.length) {
        return 1;
    }
    //开头如果是0字符，则直接无法转换
    if (str[i] == '0') {
        return 0;
    }
    int res = 0;
    //1~9必然能转换
    res += process(str, i + 1);
    //判断i~i+1 的值是否 < 26,是则参与计算
    if (i + 2 <= str.length && (str[i] == '1' || (str[i] == '2' && str[i + 1] <= '6'))) {
        res += process(str, i + 2);
    }
    return res;
}

/*
暴力递归改动态规划
一维表 dp[i] 表示以i开头到最后的字符串的转化结果
*/
public static int dpWays(String s) {
    char[] str = s.toCharArray();
    int N = str.length;
    int[] dp = new int[str.length + 1];

    if (str == null) {
        return 0;
    }
    dp[N] = 1;
    for (int i = N - 1; i >= 0; i--) {
        if (str[i] == '0') {
            dp[i] = 0;
        } else {
            dp[i] = dp[i + 1];
            if (i + 1 < N && (str[i] == '1' || (str[i] == '2' && str[i + 1] <= '6'))) {
                dp[i] += dp[i + 2];
            }
        }
    }
    return dp[0];
}

背包问题

从左往右的尝试模型：

给定两个长度都为N的数组weights和values，
weights[i]和values[i]分别代表 i号物品的重量和价值。
给定一个正数bag，表示一个载重bag的袋子，
你装的物品不能超过这个重量。
返回你能装下最多的价值是多少?

/*
思路：寻找baseCase，两种情况，要么背，要么不背，计算背的重量超过bag就返回
*/
public static int getMaxValue(int[] w, int[] v, int bag) {
    return process(w, v, 0, 0, bag);
}

// 不变 ： w[]  v[]  bag
// index... 最大价值
// 0..index-1上做了货物的选择，使得你已经达到的重量是多少alreadyW
// 如果返回-1，认为没有方案
// 如果不返回-1，认为返回的值是真实价值
public static int process(int[] w, int[] v, int index, int alreadyW, int bag) {
    if (alreadyW > bag) {
        return -1;
    }
    // 重量没超
    if (index == w.length) {
        return 0;
    }
    int p1 = process(w, v, index + 1, alreadyW, bag);
    int p2next = process(w, v, index + 1, alreadyW + w[index], bag);
    int p2 = -1;
    if (p2next != -1) {
        p2 = v[index] + p2next;
    }
    return Math.max(p1, p2);

}

/*
思路：背包没剩余空间就返回
*/
public static int maxValue(int[] w, int[] v, int bag) {
    return process(w, v, 0, bag);
}

// 只剩下rest的空间了，
// index...货物自由选择，但是剩余空间不要小于0
// 返回 index...货物能够获得的最大价值
public static int process(int[] w, int[] v, int index, int rest) {
    if (rest < 0) { // base case 1
        return -1;
    }
    // rest >=0
    if (index == w.length) { // base case 2
        return 0;
    }
    // 有货也有空间
    int p1 = process(w, v, index + 1, rest);
    int p2 = -1;
    int p2Next = process(w, v, index + 1, rest - w[index]);
    if(p2Next!=-1) {
        p2 = v[index] + p2Next;
    }
    return Math.max(p1, p2);
}

/*
暴力递归改动态规划
二维表：
  行 ：i..N-1 可供挑选的物品 先从只背最后一个开始入手
  列 ：0...bag 背包的剩余空间
  值 ：当前背包的最大价值
*/
public static int dpWay(int[] w, int[] v, int bag) {
    int N = w.length;
    int[][] dp = new int[N + 1][bag + 1];
    for (int index = N - 1; index >= 0; index--) {
        for (int rest = 0; rest <= bag; rest++) {
            dp[index][rest] = dp[index + 1][rest];
            if (rest >= w[index]) {
                dp[index][rest] = Math.max(dp[index][rest], v[index] + dp[index + 1][rest - w[index]]);
            }
        }
    }
    return dp[0][bag];
}

**范围上尝试的模型**

给定一个整型数组arr，代表数值不同的纸牌排成一条线，
玩家A和玩家B依次拿走每张纸牌，
规定玩家A先拿，玩家B后拿，
但是每个玩家每次只能拿走最左或最右的纸牌，
玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。

/*
思路：
  f函数表示先手获取的卡牌，f函数先手肯定会取一个对后手取牌最不好的结果
  s函数表示后手选择的卡牌，s函数后手肯定只能选择先手留给你的最差的结果
*/
public static int win1(int[] arr) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    return Math.max(
        f(arr, 0, arr.length - 1),
        s(arr, 0, arr.length - 1)
    );
}

// L....R
// F  S  L+1..R
// L..R-1
public static int f(int[] arr, int L, int R) {
    if (L == R) {
        return arr[L];
    }

    return Math.max(
        arr[L] + s(arr, L + 1, R),
        arr[R] + s(arr, L, R - 1)
    );
}

// arr[L..R]
public static int s(int[] arr, int L, int R) {
    if (L == R) {
        return 0;
    }
    return Math.min(
        f(arr, L + 1, R), // arr[i]
        f(arr, L, R - 1)  // arr[j]
    );
}

/*
暴力递归改动态规划
*/
public static int win2(int[] arr) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    int N = arr.length;
    int[][] f = new int[N][N];
    int[][] s = new int[N][N];
    for(int i = 0; i < N;i++) {
        f[i][i] = arr[i];
    }
    // s[i][i] = 0;
    for(int i = 1; i < N;i++) {
        int L =0;
        int R =i;
        while(L < N && R < N) {

            f[L][R] = Math.max(
                arr[L] + s[L + 1][ R],
                arr[R] + s[L][R - 1]
            ); 
            s[L][R] = Math.min(
                f[L + 1][R], // arr[i]
                f[L][R - 1]  // arr[j]
            ); 
            L++;
            R++;
        }
    }
    return Math.max(f[0][N-1], s[0][N-1]);
}

四种模型

**什么暴力递归可以继续优化？**

有重复调用同一个子问题的解，这种递归可以优化

如果每一个子问题都是不同的解，无法优化也不用优化

**任何暴力尝试，只要有重复计算的过程，把可变参数的结构变成固化的过程，做成缓存，再精细之后，就是动态规划**

**暴力递归和动态规划的关系**

某一个暴力递归，有解的重复调用，就可以把这个暴力递归优化成动态规划

任何动态规划问题，都一定对应着某一个有解的重复调用的暴力递归

但不是所有的暴力递归，都一定对应着动态规划

**如何找到某个问题的动态规划方式？**

1）设计暴力递归：重要原则+4种常见尝试模型！重点！

2）分析有没有重复解：套路解决

3）用记忆化搜索 -> 用严格表结构实现动态规划：套路解决

4）看看能否继续优化：套路解决

**常见的4种尝试模型**

1）从左往右的尝试模型

2）范围上的尝试模型

3）多样本位置全对应的尝试模型

4）寻找业务限制的尝试模型

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

1）你已经有了一个不违反原则的暴力递归，而且的确存在解的重复调用
2）找到哪些参数的变化会影响返回值，对每一个列出变化范围
3）参数间的所有的组合数量，意味着表大小
4）记忆化搜索的方法就是傻缓存，非常容易得到
5）规定好严格表的大小，分析位置的依赖顺序，然后从基础填写到最终解
6）对于有枚举行为的决策过程，进一步优化

假设有排成一行的N个位置，记为1~N，N 一定大于或等于 2
开始时机器人在其中的M位置上(M 一定是 1~N 中的一个)
如果机器人来到1位置，那么下一步只能往右来到2位置；
如果机器人来到N位置，那么下一步只能往左来到 N-1 位置；
如果机器人来到中间位置，那么下一步可以往左走或者往右走；
规定机器人必须走 K 步，最终能来到P位置(P也是1~N中的一个)的方法有多少种
给定四个参数 N、M、K、P，返回方法数。

/*
思想：
  最小化问题 每次走一步，有哪些选择，制定baseCase
*/
public static int ways1(int N, int M, int K, int P) {
    // 参数无效直接返回0
    if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
        return 0;
    }
    // 总共N个位置，从M点出发，还剩K步，返回最终能达到P的方法数
    return walk(N, M, K, P);
}

// N : 位置为1 ~ N，固定参数
// cur : 当前在cur位置，可变参数
// rest : 还剩res步没有走，可变参数
// P : 最终目标位置是P，固定参数
// 该函数的含义：只能在1~N这些位置上移动，当前在cur位置，走完rest步之后，停在P位置的方法数作为返回值返回
public static int walk(int N, int cur, int rest, int P) {
    // 如果没有剩余步数了，当前的cur位置就是最后的位置
    // 如果最后的位置停在P上，那么之前做的移动是有效的
    // 如果最后的位置没在P上，那么之前做的移动是无效的
    if (rest == 0) {
        return cur == P ? 1 : 0;
    }
    // 如果还有rest步要走，而当前的cur位置在1位置上，那么当前这步只能从1走向2
    // 后续的过程就是，来到2位置上，还剩rest-1步要走
    if (cur == 1) {
        return walk(N, 2, rest - 1, P);
    }
    // 如果还有rest步要走，而当前的cur位置在N位置上，那么当前这步只能从N走向N-1
    // 后续的过程就是，来到N-1位置上，还剩rest-1步要走
    if (cur == N) {
        return walk(N, N - 1, rest - 1, P);
    }
    // 如果还有rest步要走，而当前的cur位置在中间位置上，那么当前这步可以走向左，也可以走向右
    // 走向左之后，后续的过程就是，来到cur-1位置上，还剩rest-1步要走
    // 走向右之后，后续的过程就是，来到cur+1位置上，还剩rest-1步要走
    // 走向左、走向右是截然不同的方法，所以总方法数要都算上
    return walk(N, cur + 1, rest - 1, P) + walk(N, cur - 1, rest - 1, P);
}

/*
思路：
记忆搜索下的动态规划：（暴力递归重复计算做缓存）
任何暴力尝试，只要有重复计算的过程，把可变参数的结构变成固化的过程，做成缓存，再精细之后，就是动态规划
*/
public static int ways2(int N, int M, int K, int P) {
    // 参数无效直接返回0
    if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
        return 0;
    }
    int[][] dp = new int[K + 1][N + 1];
    dp[0][P] = 1;
    for (int i = 1; i <= K; i++) {
        for (int j = 1; j <= N; j++) {
            if (j == 1) {
                dp[i][j] = dp[i - 1][2];
            } else if (j == N) {
                dp[i][j] = dp[i - 1][N - 1];
            } else {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
            }
        }
    }
    return dp[K][M];
}

给定数组arr，arr中所有的值都为正数且不重复
每个值代表一种面值的货币，每种面值的货币可以使用任意张
再给定一个整数 aim，代表要找的钱数
求组成 aim 的方法数

//暴力递归
// arr中都是正数且无重复值，返回组成aim的方法数
public static int ways1(int[] arr, int aim) {
    if (arr == null || arr.length == 0 || aim < 0) {
        return 0;
    }
    return process1(arr, 0, aim);
}

public static int process1(int[] arr, int index, int rest) {
    if(index == arr.length) {
        return rest == 0 ? 1 : 0 ;	
    }
    int ways = 0;
    for(int zhang = 0;  zhang * arr[index] <= rest ;zhang++) {
        ways += process1(arr, index + 1, rest -  (zhang * arr[index])  );
    }
    return ways;
}

/*
暴力递归改记忆搜索
*/
public static int ways2(int[] arr, int aim) {
    if (arr == null || arr.length == 0 || aim < 0) {
        return 0;
    }
    int[][] dp = new int[arr.length+1][aim+1];
    // 一开始所有的过程，都没有计算呢
    // dp[..][..]  = -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);
}

// 如果index和rest的参数组合，是没算过的，dp[index][rest] == -1
// 如果index和rest的参数组合，是算过的，dp[index][rest]  > - 1
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 zhang = 0;  zhang * arr[index] <= rest ;zhang++) {
        ways += process2(arr, index + 1, rest -  (zhang * arr[index]) , dp );
    }
    dp[index][rest] = ways;
    return ways;
}

/*
标准动态规划
dp行：使用i..N-1个面值的纸币时，结果
dp列：剩余多少金额
*/
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;// dp[N][1...aim] = 0;
    for(int index = N - 1; index >= 0; index--) {
        for(int rest = 0; rest <= aim; rest++) {
            int ways = 0;
            for(int zhang = 0;  zhang * arr[index] <= rest ;zhang++) {
                ways += dp[index + 1] [rest -  (zhang * arr[index])];
            }
            dp[index][rest] = ways;
        }
    }
    return dp[0][aim];
}

algorithm

优化的动态规划,省略动态规划的枚举行为

假设求图中问号的结果：
当不选择本次面值时，rest - 0 * arr[index] = rest
所以不选择本次面值时， dp[index][rest] = dp[index+1][rest]; 也就是图中的 a 位置

当选择本次面值时，它依赖 dp[index+1][rest - ? * arr[index]]，也就是图中的 a + b + c + ...
而由于 dp[index][rest - arr[index]]，也就是星号的位置，其实是已经求过 b + c的结果
所以，问号的结果 = 星号的结果 + a的结果

/*
优化的动态规划,省略动态规划的枚举行为
*/
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;// dp[N][1...aim] = 0;
    for(int index = N - 1; index >= 0; index--) {
        for(int rest = 0; rest <= aim; rest++) {
            //不用arr[index]面值时的结果，面值不参与计算，其结果和 index + 1的相同
            dp[index][rest] = dp[index+1][rest];
            //若不越界，使用之前的累加结果 + 不使用面值的结果
            if(rest - arr[index] >= 0) {
                dp[index][rest] += dp[index][rest - arr[index]];
            }
        }
    }
    return dp[0][aim];
}

public static void main(String[] args) {
    int[] arr = { 5, 10,50,100 };
    int sum = 1000;
    System.out.println(ways1(arr, sum));
    System.out.println(ways2(arr, sum));
    System.out.println(ways3(arr, sum));
    System.out.println(ways4(arr, sum));
}

给定一个字符串str，给定一个字符串类型的数组arr。
arr里的每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来。
返回需要至少多少张贴纸可以完成这个任务。
例子：str= "babac"，arr = {"ba","c","abcd"}
至少需要两张贴纸"ba"和"abcd"，因为使用这两张贴纸，把每一个字符单独剪开，含有2个a、2个b、1个c。是可以拼出str的。所以返回2。

/*
思路：
把贴纸都转换成二维数组存储26个字母的数量，通过数量相减计算字符串rest的字符
*/
public static int minStickers1(String[] stickers, String target) {

    int n = stickers.length;

    int[][] map = new int[n][26];// stickers -> [26] [26] [26]
    for (int i = 0; i < n; i++) {
        char[] str = stickers[i].toCharArray();
        for (char c : str) {
            map[i][c - 'a']++;
        }
    }
    HashMap<String, Integer> dp = new HashMap<>();
    dp.put("", 0);
    return process1(dp, map, target);
}

// dp 傻缓存，如果t已经算过了，直接返回dp中的值
// t 剩余的目标
// 0..N每一个字符串所含字符的词频统计
// 返回值是-1，map 中的贴纸  怎么都无法rest
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; // ans -> 搞定rest，使用的最少的贴纸数量 
    int n = map.length; // N种贴纸
    int[] tmap = new int[26]; // tmap 去替代 rest
    char[] target = rest.toCharArray();
    for (char c : target) {
        tmap[c - 'a']++;
    }
    for (int i = 0; i < n; i++) {
        // 枚举当前第一张贴纸是谁？
        if (map[i][target[0] - 'a'] == 0) {
            continue;
        }
        StringBuilder sb = new StringBuilder();
        // i 贴纸， j 枚举a~z字符
        for (int j = 0; j < 26; j++) { // 
            if (tmap[j] > 0) { // j这个字符是target需要的
                for (int k = 0; k < Math.max(0, tmap[j] - map[i][j]); k++) {
                    sb.append((char) ('a' + j));
                }
            }
        }
        // sb ->  i
        String s = sb.toString();
        int tmp = process1(dp, map, s);
        if (tmp != -1) {
            ans = Math.min(ans, 1 + tmp);
        }
    }
    // ans 系统最大  rest
    dp.put(rest, ans == Integer.MAX_VALUE ? -1 : ans);
    return dp.get(rest);
}

1
2
3

**多样本位置全对应的尝试模型**

两个字符串的最长公共子序列问题

//暴力递归
public static int lcs(String s1, String s2) {
    char[] str1 = s1.toCharArray();
    char[] str2 = s2.toCharArray();
    int N = str1.length;
    int M = str2.length;
    return process(str1, str2, N - 1, M - 1);
}

// str1[0....i1] 与 str2[0......i2]的最长公共子序列长度是多少？
public static int process(char[] str1, char[] str2, int i1, int i2) {
    if (i1 == 0 && i2 == 0) {
        return str1[i1] == str2[i2] ? 1 : 0;
    }
    // i1 和 i2 不同时为0
    if (i1 == 0) { // str1[0..0] str2[0...i2 - 1]
        return ((str1[i1] == str2[i2]) || process(str1, str2, i1, i2 - 1) == 1) ? 1 : 0;
    }

    if (i2 == 0) {
        return ((str1[i1] == str2[i2]) || process(str1, str2, i1 - 1, i2) == 1) ? 1 : 0;
    }
    // i1 和 i2 都不是0
    // 最长公共子序列结尾，不是以str1[i1]与str2[i2]结尾的
    int p1 = process(str1, str2, i1 - 1, i2 - 1);
    int p2 = process(str1, str2, i1, i2 - 1);
    int p3 = process(str1, str2, i1 - 1, i2);
    int p4 = 0;
    if (str1[i1] == str2[i2]) {
        p4 = p1 + 1;
    }
    return Math.max(Math.max(p1, p2), Math.max(p3, p4));
}

/*
思路
把样本数据当做二维数组，求最右下角的值，就是问题的答案
dp[i][j]的含义是以i、j下标结尾的字符串他们的最长子序列长度
db[i][j]赋值的四种思考方式：
  1.db[i][j] = db[i-1][j-1] : 最长子序列和两个字符串的最后字符无关
  2.db[i][j] = db[i-1][j] ：最长子序列和str1最后字符串无关
  3.db[i][j] = db[i][j-1] ：最长子序列和str2最后字符串无关
  4.db[i][j] = db[i-1][j-1] + 1 :  str1和str2最后字符相同（满足str1[i] = str2[j]）
*/
public static int lcse(char[] str1, char[] str2) {

    int[][] dp = new int[str1.length][str2.length];
  
    //str1第一个字符和str2第一个字符做比较
    dp[0][0] = str1[0] == str2[0] ? 1 : 0;
  
    for (int i = 1; i < str1.length; i++) {
        //若前面的字符已经答案是1了，则后面的都是1
        dp[i][0] = Math.max(dp[i - 1][0], str1[i] == str2[0] ? 1 : 0);
    }
    for (int j = 1; j < str2.length; j++) {
        dp[0][j] = Math.max(dp[0][j - 1], str1[0] == str2[j] ? 1 : 0);
    }
    for (int i = 1; i < str1.length; i++) {
        for (int j = 1; j < str2.length; j++) {
            //因为第二和第三种情况的数据来源都是基于第一种情况算出来的，所以这里不需要再考虑第一种情况
            //先求第二和第三种情况的最大值
            dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            //如果有第四种情况，则参与比较
            if (str1[i] == str2[j]) {
                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
            } 
        }
    }
    return dp[str1.length - 1][str2.length - 1];
}

**寻找业务限制的尝试模型**

给定一个数组，代表每个人喝完咖啡准备刷杯子的时间
只有一台咖啡机，一次只能洗一个杯子，时间耗费a，洗完才能洗下一杯
每个咖啡杯也可以自己挥发干净，时间耗费b，咖啡杯可以并行挥发
返回让所有咖啡杯变干净的最早完成时间
三个参数：int[] arr、int a、int b

// process(drinks, 3, 10, 0,0)
// a 洗一杯的时间 固定变量
// b 自己挥发干净的时间 固定变量
// drinks 每一个员工喝完的时间 固定变量
// drinks[0..index-1]都已经干净了，不用你操心了
// drinks[index...]都想变干净，这是我操心的，washLine表示洗的机器何时可用
// drinks[index...]变干净，最少的时间点返回
public static int process(int[] drinks, int a, int b, int index, int washLine) {
    if (index == drinks.length - 1) {
        return Math.min(Math.max(washLine, drinks[index]) + a, drinks[index] + b);
    }
    // 剩不止一杯咖啡
    // wash是我当前的咖啡杯，洗完的时间
    int wash = Math.max(washLine, drinks[index]) + a;// 洗，index一杯，结束的时间点
    // index+1...变干净的最早时间
    int next1 = process(drinks, a, b, index + 1, wash);
    // index....
    int p1 = Math.max(wash, next1);
    int dry = drinks[index] + b; // 挥发，index一杯，结束的时间点
    int next2 = process(drinks, a, b, index + 1, washLine);
    int p2 = Math.max(dry, next2);
    return Math.min(p1, p2);
}

/*
暴力递归改动态规划
根据每一杯咖啡的washLine的最大值来定二维数组
washLine的最大值是所有咖啡都放咖啡机洗的时间
*/
public static int dp(int[] drinks, int a, int b) {
    if (a >= b) {
        return drinks[drinks.length - 1] + b;
    }
    // a < b
    int N = drinks.length;
    int limit = 0; // 咖啡机什么时候可用
    for (int i = 0; i < N; i++) {
        limit = Math.max(limit, drinks[i]) + a;
    }
    int[][] dp = new int[N][limit + 1];
    // N-1行，所有的值
    for (int washLine = 0; washLine <= limit; washLine++) {
        dp[N - 1][washLine] = Math.min(Math.max(washLine, drinks[N - 1]) + a, drinks[N - 1] + b);
    }
    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]) + a;
            if (wash <= limit) {
                p1 = Math.max(wash, dp[index + 1][wash]);
            }
            int p2 = Math.max(drinks[index] + b, dp[index + 1][washLine]);
            dp[index][washLine] = Math.min(p1, p2);
        }
    }
    return dp[0][0];
}

请同学们自行搜索或者想象一个象棋的棋盘，
然后把整个棋盘放入第一象限，棋盘的最左下角是(0,0)位置
那么整个棋盘就是横坐标上9条线、纵坐标上10条线的区域
给你三个 参数 x，y，k
返回“马”从(0,0)位置出发，必须走k步
最后落在(x,y)上的方法数有多少种?

//暴力递归
// 马从(0,0)出发，有K步要走，并且一定要走完，最终来到x，y位置的方法数是多少
public static int way1(int x, int y, int k) {
    if (k == 0) {
        return x == 0 && y == 0 ? 1 : 0;
    }
    if (x < 0 || x > 9 || y < 0 || y > 8) {
        return 0;
    }
    // 有步数要走, x，y 也是棋盘上的位置
    // 马的走法，有8个位置能一步走到x,y
    return f(x + 2, y - 1, k - 1) 
        + f(x + 2, y + 1, k - 1) 
        + f(x + 1, y + 2, k - 1) 
        + f(x - 1, y + 2, k - 1)
        + f(x - 2, y + 1, k - 1) 
        + f(x - 2, y - 1, k - 1) 
        + f(x - 1, y - 2, k - 1) 
        + f(x + 1, y - 2, k - 1);
}

//另一种暴力递归
public static int ways2(int x, int y, int k) {
    return p(0,0,k,x,y);
}

// 当前来到row，col位置，还剩rest步，走完rest步之后，来到x，y位置，方法数多少
public static int p(int row, int col, int rest, int x, int y) {
    if(rest == 0) {
        return row == x && col == y ? 1 :0;
    }

    if (row < 0 || row > 9 || col < 0 || col > 8) {
        return 0;
    }

    return p(row + 2, col - 1, rest - 1, x, y) 
        + p(row + 2, col + 1, rest - 1, x, y) 
        + p(row + 1, col + 2, rest - 1, x, y) 
        + p(row - 1, col + 2, rest - 1, x, y)
        + p(row - 2, col + 1, rest - 1, x, y) 
        + p(row - 2, col - 1, rest - 1, x, y) 
        + p(row - 1, col - 2, rest - 1, x, y) 
        + p(row + 1, col - 2, rest - 1, x, y);

}

//动态规划
public static int ways3(int x, int y, int k) {
    int[][][] dp = new int[10][9][k + 1];// 0~k

    dp[0][0][0] = 1; // dp[..][..][0] = 0

    for (int level = 1; level <= k; level++) {
        // level层，x y
        for (int i = 0; i < 10; i++) { // x可能性
            for (int j = 0; j < 9; j++) { // y的可能性
                dp[i][j][level] = getValue(dp, i + 2, j - 1, level - 1) + getValue(dp, i + 2, j + 1, level - 1)
                    + getValue(dp, i + 1, j + 2, level - 1) + getValue(dp, i - 1, j + 2, level - 1)
                    + getValue(dp, i - 2, j + 1, level - 1) + getValue(dp, i - 2, j - 1, level - 1)
                    + getValue(dp, i - 1, j - 2, level - 1) + getValue(dp, i + 1, j - 2, level - 1);
            }
        }
    }

    return dp[x][y][k];
}

public static int getValue(int[][][] dp, int x, int y, int k) {
    if (x < 0 || x > 9 || y < 0 || y > 8) {
        return 0;
    }
    return dp[x][y][k];
}

最后更新： 2021年03月09日 22:59

原始链接： https://midkuro.gitee.io/2020/10/30/algorithm-base/

赏

Kuro's Blog

坚持是一种品格

'数据结构与算法'

基础算法

时间复杂度

选择排序

冒泡排序

插入排序

额外空间复杂度

算法流程的常数项

二分法

异或运算

栈和队列

递归

哈希表

归并排序

快速排序

堆结构

前缀树

桶排序

总结

链表

二叉树

二叉树的递归套路

贪心算法

并查集

图

暴力递归

汉诺塔问题

逆序栈问题

子序列问题

全排列问题

皇后问题

动态规划

背包问题

四种模型