算法训练营记录
算法训练营
时间复杂度、空间复杂度
常数阶O(1)
对数阶O(logN)
线性阶O(n)
线性对数阶O(nlogN)
平方阶O(n²)
立方阶O(n³)
K次方阶O(n^k)
指数阶(2^n)
一维数据结构：线性表（array、stack、listNode、queue）、散列表（set、dictionary）
二维数据结构：堆、树、图
树是特殊的图：每个结点下有两个子结点
链表是特殊的树：每个结点下只有1个子节点
堆就是树，堆分为最大堆或者最小堆（根节点最大或者最小）
1、堆中某个节点的值总是不大于或者不小于其父节点的值
2、堆总是一颗完全二叉树
二叉树的 前序、中序、后续
前序：根-左-右
中序：左-根-右
后续：左-右-根
二叉搜素树、二叉查找树、有序二叉树、排序二叉树，是指一颗空树或者具有下列性质的二叉树
1、左子树上所有结点的值均小于它的根结点的值
2、右子树上所有结点的值均大于它的根结点的值
3、以此类推：左、右子树也分别为二叉查找树
中序遍历：升序遍历
广度优先
深度优先
递归代码模板：
func recursion(level,param1,param2,...) {
// recursion terminator 递归终结条件
if level > MAX_LEVEL
process_result
return
// pricess logic in current level 处理当前层级的业务逻辑
process(level,data,...)
// drill down 进入到下一层去
self.recursion(level + 1,param1,param2,...)
// reverse the current level status if needed 如果需要清理当前层
}
递归的三个思维要点
1、抵制人肉递归
2、找最近重复性
3、数学归纳法思维
分治和回溯
分治和回溯是特殊的递归
二分查找的前提
1、目标函数单调性（递增或者递减）
2、存在上下界（bounded）
3、能够通过索引访问（index accessible）
动态规划
和递归或者分治 没有根本上的区别（关键看有无最优的子结构）
共性：找到重复子问题
差异性：最优子结构、中途可以淘汰次优解
关键点
1、最优子结构 opt[n] = best_of(opt[n-1],opt[n-2],...)
2、存储中间状态：opt[i]
3、递推公式（美名其曰：状态转移方程或者DP方程）
Fib: opt[n] = opt[n-1] + opt[n-2]
二维路径: opt[i,j] = opt[i+1,j] + opt[i,j+1]；(且判断a[i,j]是否空地)
动态规划小结
1、打破自己的思维惯性，形成机械思维
2、理解复杂逻辑的关键
3、职业进阶的要点要领，信任下属并merge反馈
字典树、trie树
并查集
适用场景：组团和配对问题
group or not ？
平衡二叉树
AVL树、红黑树、B树
AVL树
平衡因子：深度不超过绝对值1 【-1，0，1】
旋转操作：
右右子树 -> 左旋
左左子树 -> 右旋
左右子树 -> 左右旋
右左子树 -> 右左
不足：结点需要存储额外信息，操作太频繁
红黑树：近似平衡二叉树
它能够确保任何一个结点的左右子树的==高度差小于两倍==。
- 每个结点要么是红色，要么是黑色
- 根结点是黑色
- 每个叶结点（NIL结点，空结点）是黑色的
- 不能有相邻接的两个红色结点
- 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点
位运算
运算符：
- ~取反操作
- &与运算：同为1的时候为1
- |或运算：有1的时候为1
- ^异或运算：相同为0不同为1
- <<左移运算
- ‘>>’右移运算
tips
- 正数的反码和补码都与原码相同
- 负数取正数的二进制数，然后最高位补1
- 负数的反码为对该数的原码除符号位外各位取反
- 负数的补码为对该数的原码除符号位外各位取反，然后在最后一位加1
异或运算的特征
- 任何数和 0 做异或运算，结果仍然是原来的数，即 a ^ 0 = a
- 任何数和其自身做异或运算，结果是 0，即 a ^ a=0
- 异或运算满足交换律和结合律，即 a ^ b ^ a = a ^ a ^ b = b
常用整理：
- 判断奇偶：x % 2 == 1 -> (x & 1) == 1,x % 2 == 0 -> (x & 1) == 0
- x >> 1 -> x/2,即 x = x/2 -> x = x >> 1,mid = (left + right)/2 -> (left + right) >> 1
- x = x & (x - 1) 清零最低位的1
- x & -x -> 得到最低位的1
- x & ~x = 0 ~为取反
布隆过滤器
一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中
- 优点：空间效率和查询时间都远远超过一般的算法
- 缺点：有一定的误识别率和删除困难。
LRUCache
- 两个要素：大小、替换策略
- HashTable + Double LinkedList
- O(1)查询、修改、更新
- LFU - least frequently used 统计的频次
- LRU - least recently used 最少最近使用
排序算法
排序时间复杂度.jpg
比较类排序
- 交换排序：冒泡排序、快速排序
- 插入排序：简单插入排序、希尔排序
- 选择排序：简单选择排序、堆排序
- 归并排序：二路归并排序、多路归并排序
非比较类排序
- 计数排序
- 桶排序
- 基数排序
高级排序
- 快速排序
1、取数组标杆pivot，将小元素放pivot左边的子数组，大元素放右边的子数组；
2、依次对两个子数组进行快排，以达到整个序列有序。
public static void quickSort(int[] array, int begin, int end) {
if (end <= begin) return;
int pivot = partition(array, begin, end);
quickSort(array, begin, pivot - 1);
quickSort(array, pivot + 1, end);
}
// 找出标杆的位置并将其左右排好序
static int partition(int[] a, int begin, int end) {
// pivot: 标杆位置，counter: 小于pivot的元素的个数
int pivot = end, counter = begin;
for (int i = begin; i < end; i++) {
if (a[i] < a[pivot]) {
int temp = a[counter]; a[counter] = a[i]; a[i] = temp;
counter++;
}
}
int temp = a[pivot]; a[pivot] = a[counter]; a[counter] = temp;
return counter;
}
- 归并排序
1、把长度为n的输入序列分成两个长度为n/2的子序列；
2、对着两个子序列分别采用归并排序；
3、将两个排序好的子序列合并成一个最终的排序序列；
public static void mergeSort(int[] array, int left, int right) {
if (right <= left) return;
//(left + right) / 2 位运算更加快速
int mid = (left + right) >> 1;
mergeSort(array, left, mid);
mergeSort(array, mid + 1, right);
merge(array, left, mid, right);
}
// 将排好序的两个数组合并
public static void merge(int[] arr, int left, int mid, int right) {
// 中间数组，额外的空间复杂度
int [] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
// 将排序好的数组放回arr中
for (int p = 0 ; p < temp.lent; p++) {
arr[left + p] = temp[p];
}
}
- 堆排序
1、 数组元素一次建立小顶堆
2、依次取堆顶元素，并删除
void heap_sort(int a[], int len) {
priority_queue<int, vector<int>, greater<int>> q;
for(int i = 0; i < len; i++){
q.push(a[i]);
}
for(int i = 0; i < len; i++) {
a[i] = q.pop();
}
}
归并 和 快排 具有相似性，但步骤顺序相反
归并： 先排序左右子数组，然后合并两个有序子数组
快排： 先调配处左右两个子数组，然后对左右子数组进行排序
