/*
** 这是快排的partition函数
*/
public static void quickSort(int[] L) {
   QuickSort(L, 0, L.length - 1);
}

public static void QuickSort(int[] L, int low, int high) {
    int pivot;
    if (low < high) {
    
    //将L[low,high]一分为二,算出枢轴值pivot,该值得位置固定,不用再变化
    pivot = partition(L, low, high);

    //对两边的数组分别排序
    QuickSort(L, low, pivot - 1);
    QuickSort(L, pivot + 1, high);
    }
}

private int partition(int[] nums,int l,int r){
	int p = nums[l];//以最左边的为基准
	int i=l,j=r+1;
	while(true){
		while(i!=r && nums[++i]<p);//找到一个大于等于p,注意条件i!=r
		while(j!=l && nums[--j]>p);//找到一个小于等于p,注意条件j!=l
		if(i>=j)
			break;
		swap(nums,i,j);
	}
	swap(nums,l,j);//注意这里是l和j的位置交换
	return j;
}

/**
* 交换2元素
*/
private void swap(int[] nums,int i,int j){
 	int t=nums[i];
 	nums[i]=nums[j];
 	nums[j]=t;
}


/*
** 这是来自极客时间的笔记
*/
递推公式：
quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1, r)
终止条件：
p >= r

// 快速排序，A 是数组，n 表示数组的大小
quick_sort(A, n) {
 quick_sort_c(A, 0, n-1)
}
// 快速排序递归函数，p,r 为下标
quick_sort_c(A, p, r) {
 if p >= r then return   //3步曲 1、先判断结束条件

 q = partition(A, p, r) // 获取分区点 2、进行运算
 quick_sort_c(A, p, q-1)		3、返回值
 quick_sort_c(A, q+1, r)
}

快速排序的性能分析：

1.时间复杂度分析：T(n) 在大部分情况下的时间复杂度都可以做到 O(nlogn)，只有在极端（数组完全有序）情况下，才会退化到 O(n2 )。

2.空间复杂度分析：原地排序算法

3.快速排序并不是一个稳定的排序算法

递推公式：
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))
终止条件：
p >= r 不用再继续分解

// 归并排序算法, A 是数组，n 表示数组大小
merge_sort(int[] arr, n) {
 merge_sort_c(arr, 0, n-1)
}
// 递归调用函数
merge_sort_c(int[] arr,int l,int h) {
 // 递归终止条件
 if l >= h then return
 // 取 l 到 h 之间的中间位置 m
 m = (l+h) / 2
 // 分治递归
 merge_sort_c(arr, l, m)
 merge_sort_c(arr, m+1, h)
 // 将 A[p...q] 和 A[q+1...r] 合并为 A[p...r]
 merge(arr,l,m,h)
}

//merge函数的伪代码  可以用哨兵模式简化
merge(int[] arr,int start,int mid,int end) {
 int i = start，j = mid+1，k = 0 // 初始化变量 i, j, k
 int[] tmp := new int[end-start+1] // 申请一个大小跟 A[start-end] 一样的临时数组
 while (i<=mid AND j<=end){
 if arr[i] <= arr[j] {
 	tmp[k++] = arr[i++]; // i++ 等于 i:=i+1
 } else {
 	tmp[k++] = arr[j++];
 		}				//求逆序对的时候可以在这里进行计数
 }

 // 判断第一个数组是否有剩余
while(i<=mid){
	tmp[k++]=arr[i++];
}

 // 判断第二个数组是否有剩余
while(j<=mid){
	tmp[k++]=arr[j++];
}

 // 将 tmp 中的数组拷贝回 A[start end]
for(int l=0;l<tmp.length;i++){
	arr[start+l]=tmp[l];
}
}

left，right =0, len(array) -1
//注意结束条件
while left<=right:
	mid = left + (right - left) >1
	if array[mid] = target;
		break or return result
	elif array[mid] < target:
		left = mid +1
	else
		right = mid - 1
		
//

查找一个数是否存在，应用特性可以直接进行左右选择
void BST(TreeNode root, int target) {
    if (root.val == target)
        // 找到目标，做点什么
    if (root.val < target) 
        BST(root.right, target);
    if (root.val > target)
        BST(root.left, target);
}

删除操作
TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return null;
    if (root.val == key) {
        // 这两个 if 把情况 1 和 2 都正确处理了
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;
        // 处理情况 3
        TreeNode minNode = getMin(root.right);
        root.val = minNode.val;
        root.right = deleteNode(root.right, minNode.val);
    } else if (root.val > key) {
        root.left = deleteNode(root.left, key);
    } else if (root.val < key) {
        root.right = deleteNode(root.right, key);
    }
    return root;
}

TreeNode getMin(TreeNode node) {
    // BST 最左边的就是最小的
    while (node.left != null) node = node.left;
    return node;
} 

二叉树的前-中-后序  通用框架
void traverse(TreeNode root) {
    // 前序遍历
    traverse(root.left)
    // 中序遍历
    traverse(root.right)
    // 后序遍历
}



//二叉树的前序遍历-迭代算法模板

栈S;
p= root;
while(p || S不空){
    while(p){
        访问p节点；
        p的右子树入S;  //访问左子树之前，先将右子树入栈
        p = p的左子树;
    }
    p = S栈顶弹出;
}


//二叉树中序遍历的-迭代算法模板
栈S;
p= root;
while(p || S不空){
    while(p){
        p入S;
        p = p的左子树;
    }
    p = S.top 出栈;
    访问p;
    p = p的右子树;
}


//二叉树后序遍历的-迭代算法模板
//每到一个节点 A，就应该立即访问它。 然后将左子树压入栈，再次遍历右子树。
栈S;
p= root;
while(p || S不空){
    while(p){
        访问p节点；
        p的左子树入S;
        p = p的右子树;
    }
    p = S栈顶弹出;
}
结果序列逆序;

void traverse(TreeNode root) {
    for (TreeNode child : root.childern)
        // 前序遍历需要的操作
        traverse(child);
        // 后序遍历需要的操作
}

BFS通用模板
def BFS(graph，start,end):
	//BFS实现一般都需要用到一个队列
	queue = []
	
	queue.append([start])
	//个人感觉这里多加了一次root节点
	visited.add(start)
	
	//1、判断queue
	while queue：
		//2 取出最前面的节点
		node = queue.pop()
		
		//3、process current node
		process（node）
		
		//4、generated_nodes
		nodes = generate_related_nodes(node)
		
		//5、把相关的节点放入queue里面
		queue.push(nodes)
		
	....
	
	
需要记层数的模板
level = 0
while queue 不空：
    size = queue.size()
    while (size --) {
        cur = queue.pop()
        for 节点 in cur的所有相邻节点：
            if 该节点有效且未被访问过：
                queue.push(该节点)
    }
    level ++;

DFS模板
visited = set()

def dfs(node,visited):
	//1、做标记
	visited.add(node)
	
	//2、process current node here
	...
	//3、处理子节点
	for next_node in node.chirldren():
		if not next_node in visited:
			//4、递归调用子节点
			self.dfs(next_node,visited)

思路：
	1、定义状态变量
	2、状态转移方程

1、状态定义（状态定义的好坏决定题目是否能正常解决），一般一维（情况）不能解决那就增加维度（增加额外的情况）
dp = new int [m+1][n+1]

2、初始状态定义
dp[0][0] = x
dp[0][1] = y  //这里只是模拟，实际情况比这个复杂的多

//DP状态的推导
for i=0 i<= n; ++i{
	for j=0; j<=m; ++j{
		//1、发生状态的条件
		//2、状态的转移方程
		dp[i][j] = min{dp[i-1][j],dp[i][j-1]}  //这里的状态转移方程只是一个示范
	}
}

return dp[m][n];  //这里的返回值只是一个示范

//很重要，暴力解法很重要
def recursion（level， param1, param2...）:
	//1、终止条件
	if level>Max_level:
		print result
		return
		
	//2、处理逻辑在当前层
	process(level,data...)
	
	//3、调用下一层递归
	self.recursion(level+1,param1,param2....)
	
	//4、reverse the current level status if needed
	reverse_state(level) //看具体情况去进行要不要

//和上面的递归一样
//结束条件可以用 i， list.size等，看具体情况
result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择
 

比较常用的位运算
X & 1 ===1 OR == 0 判断奇偶

X = X & (X - 1) --> 清楚最低位的1

X & (-X) --> 得到最低位的1

马拉车算法
//只看过B站视频

KMP算法
//只看过B站视频

Rabin-Karp 编码

/* 返回 nums 中 LIS 的长度 */
public int lengthOfLIS(int[] nums) {
    int size = 0, n = nums.length;
    int[] top = new int[n];
    for (int i = 0; i < n; i++) {
        // 要处理的扑克牌
        int poker = nums[i];
        int left = 0, right = size;
        // 二分查找插入位置
        while (left < right) {
            int mid = (left + right) / 2;
            if (top[mid] >= poker)
                right = mid;
            else
                left = mid + 1;
        }
        if (left == size) size++;
        // 把这张牌放到牌堆顶
        top[left] = poker;
    }
    // 牌堆数就是 LIS 长度
    return size;
}


//第二种解法
    private int lengtOfLIS(int[] height) {
        int[] tails = new int[height.length];
        int size = 0;
        for (int x : height) {
            int i = Arrays.binarySearch(tails, 0, size, x);
            if (i < 0)
                i = -(i + 1);//这里i的值就为-1
            tails[i] = x;
            if (i == size) ++size;
        }
        return size;
    }