算法
二分法
比较适合有序数组搜索，
深搜，广搜
比较适合树，图，迷宫等
动态规划
比较适用于求解最值问题，例如走台阶
贪心算法
递归与回溯
比较适合能拆分成小问题，例如+-数字
哈希表
比较适合配对，例如数组中找两个数相加为给定值
滑动窗口
适用于子串极值问题
栈
例如k个一组反转链表/数组，数组/链表循环右移k个位置也可以
队列
二分法代码：
function search(arr, v) {
if (!arr.length) return -1
let start = 0
let end = arr.length - 1
let mid = Math.floor((start + end) / 2)
while (true) {
if (arr[mid] < v) {
start = mid
} else if (arr[mid] > v) {
end = mid
} else {
break
}
if (end - start <= 1) {
break
}
}
if (arr[mid] === v) {
return mid
}
if (arr[start] === v) {
return start
}
if (arr[end] === v) {
return end
}
return -1
}经典面试题
最大连续子序和
动态规划问题，r(n) = r(n-1)+a(n) > a(n) ? r(n-1)+a(n) : a(n)
// r[n] = r[n-1] > 0? a[n]+r[n-1] : a[n]
var maxSubArray = function(nums) {
let res = nums[0];
nums.reduce((sum, num) => {
sum = num + Math.max(sum, 0);
res = Math.max(res, sum);
return sum;
})
return res;
};跳台阶：一个为n的台阶，小明可以一次走一步、两步或者五步，问一共几种走法？
分析：典型的动态规划问题，那么就是要找到递归公式是什么。
r[n]是第几个台阶，它有多少种走法，与r[n-1]的关系是，首先肯定+1，因为一次可以走一步；其次两步的时候就是r[n-2]，五步的时候就是r[n-5]，因此公式为：
r[n] = r[n-1] + r[n-2] + r[n-5]任务调度器II
给你一个下标从 0 开始的正整数数组 tasks ，表示需要 按顺序 完成的任务，其中 tasks[i] 表示第 i 件任务的 类型 。
同时给你一个正整数 space ，表示一个任务完成 后 ，另一个 相同 类型任务完成前需要间隔的 最少 天数。
在所有任务完成前的每一天，你都必须进行以下两种操作中的一种：
- 完成 tasks 中的下一个任务
- 休息一天
请你返回完成所有任务所需的 最少 天数。
示例 1：
输入：tasks = [1,2,1,2,3,1], space = 3
输出：9
解释：
9 天完成所有任务的一种方法是：
第 1 天：完成任务 0 。
第 2 天：完成任务 1 。
第 3 天：休息。
第 4 天：休息。
第 5 天：完成任务 2 。
第 6 天：完成任务 3 。
第 7 天：休息。
第 8 天：完成任务 4 。
第 9 天：完成任务 5 。
可以证明无法少于 9 天完成所有任务。
示例 2：
输入：tasks = [5,8,8,5], space = 2
输出：6
解释：
6 天完成所有任务的一种方法是：
第 1 天：完成任务 0 。
第 2 天：完成任务 1 。
第 3 天：休息。
第 4 天：休息。
第 5 天：完成任务 2 。
第 6 天：完成任务 3 。
可以证明无法少于 6 天完成所有任务。每次更新 同类型任务需要的最小天数
完成任务的时候 判断 是比上次加1天 还是 受同类型任务影响的 更多天数
var taskSchedulerII = function(tasks, space) {
let ans = 0, hash = {}
for(let t of tasks){
ans = Math.max(ans + 1, hash[t] ?? 0)
hash[t] = ans + space + 1
}
return ans
};如何得到一个数组中第k大的数？
- o(n): 采用普通排序，返回第k个元素。既然有o(n)的做法，实际上就不会出这道题了
- o(logn): 采用快速排序，比较哨兵的index与第k个位置的关系，选第0个当哨兵，也从第0个开始，左边是小于等于哨兵的，右边是大于哨兵的，这就很清楚了，接下来再递归即可。
// @param k 从1开始
// @return 第k大的数
function maxK(arr, k) {
if (!arr || !arr.length) return
if (arr.length == 1) return arr[0]
let lArr = []
let rArr = []
let mid = arr[0]
arr.forEach(a => {
if (a <= mid) {
lArr.push(a)
} else {
rArr.push(a)
}
})
const i = arr.length - k // 要找的第k大的值的index
if (lArr.length > i) {
return maxK(lArr, k - 1 - rArr.length)
} else if (lArr.length == i) {
return mid
} else {
return maxK(rArr, k)
}
}将数组循环右移k个位置
首先将前k个元素逆置，然后将后n-k个元素逆置，最后整体逆置一次
原地旋转图像
右上-左下对称swap，然后水平翻转180度完成操作，最少也要O(n)的时间复杂度。
最大连续子序积
同理动态规划，r[n] = r[n-1]*a[n] > a[n] ? r[n-1]*a[n] : a[n]
如何在一个数组中获取总和是固定值的长度最小的连续子数组？
滑动窗口经典题，用滑动窗口法，不够就移动左指针，够了就移动右指针，直到不够为止。
function minEqualSumLen(arr, sum) {
let i = 0
let j = 0
let minLen = arr.length
while(true) {
const t_sum = getSum(arr, i, j)
if (t_sum == sum) {
if (minLen > j-i) minLen = j-i
}
if (t_sum > sum) {
if (i < arr.length - 1) i += 1
} else {
if (j < arr.length - 1) {
j += 1
} else {
i += 1
}
}
if (i >= arr.length) {
break
}
}
return minLen + 1
}盛水最多的容器：找最大面积，假设数组的元素值为高度，找到最大的矩形面积
滑动窗口经典题，向中间移动数字较少的哪那一个，为什么呢？如果移动较大的，保留小板，那么必然整体就会变小，这就是求盛水最小的容器了。
必会的基本算法
快速排序
大根堆（优先队列）
单调栈
是一种特殊的数据结构，它维持栈内元素的单调性，即栈内元素要么单调递增，要么单调递减。这种数据结构在处理某些算法问题时非常高效。单调栈的主要操作包括元素的入栈和出栈，但在入栈时需要保证栈内元素的单调性。
排序
冒泡排序（Bubble Sort）
- 在一轮中，依次比较所有相邻元素,如果第一个比第二个大，则交换它们，最后能把最大的数放到最后面
- 在第二轮，继续依次比较，这样能把第二大的数推到倒数第二位
- 执行n轮，完成排序。这个算法的名字由来是因为大的数会经由交换慢慢“浮”到数列的顶端。
function sort(arr) {
for(let i = 0; i < arr.length - 1; i++) {
for(let j = 0; j < arr.length - 1 - i; j++) {
if(arr[j] > arr[j+1]) {
const temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}选择排序（Selection Sort）
- 找到数组中的最大值，将其放置在最后一位
- 接着找到剩余数组中的最大值，将其放置到倒数第二位
- 执行n轮，就可以完成排序。与冒泡排序的区别是选择排序不是相邻比较，而是全局比较
function sort(arr) {
for(let i = 0; i < arr.length - 1; i++) {
let pos = 0;
let max = arr[0];
for(let j = 0; j < arr.length - 1 - i; j++) {
if(max < arr[j]) {
pos = j;
max = arr[j];
}
}
const temp = arr[arr.length - 1 - i]
arr[arr.length - 1 - i] = max
arr[pos] = temp
}
}插入排序（Insertion Sort）
- 从第二个数开始往前比，在前面排好序的数据中找到自己应该插入的地方插入
- 以此类推进行到最后一个数
function sort(arr) {
for(let i = 1; i<arr.length; ++i) {
const temp = arr[i];
let j = i;
while(j > 0) {
if(arr[j-1] > temp) {
arr[j] = arr[j-1];
} else {
break;
}
j -= 1;
}
arr[j] = temp;
}
}归并排序（Merge Sort）
- 分：把数组劈成两半，再递归地对数组进行“分”操作，直到分成一个个单独的数
- 合：把两个数合并为有序数组，再对有序数组进行合并，直到全部子数组合并为一个完整数组
快速排序
- 分区：从数组中任意选择一个基准，所有比基准小的元素放到基准前面，比基准大的元素放到基准的后面
- 递归：递归地对基准前后的子数组进行分区
function sort(arr) {
const rec = (arr) => {
if(arr.length === 1 || arr.length === 0) { return arr; }
const left = [];
const right = [];
const mid = arr[0];
for(let i = 1; i < arr.length; ++i) {
if(arr[i] < mid) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...rec(left), mid, ...rec(right)];
};
return rec(arr);
}堆排序
实际上堆是一个一个插入进去的，反应到数组上，就是一次遍历。但是每次只能得到最大值而已。
外部排序
用归并法，最佳归并树，败者树
数组部分
寻找数组峰值(一定有峰值，元素不重复，任意一个就行，这个值比两边相邻的值都大就称为峰值)(首尾元素不相同)
- 一般需要O(n)，挨个找一遍即可。
- 但最快可以log(n)，因为有条件的限制，用二分法，首先两端节点一定是上升或下降趋势的，假如是下降趋势的(首元素大于尾元素)，先找中间节点，如果首节点与中节点是上升趋势的(中间节点大于首节点)，那么表明有峰值在右边，如果是下降趋势的，那么表明有峰值在左边。(因为随便一个峰值就行)，这样时间复杂度就是O(logn)，好厉害。
找到乱序数组中缺失的最小数(从1开始)(缺失的第一个正数)
从1开始，1234....直到有一个地方断开了，直接到100之类的(不重复)，必须O(n)的时间复杂度和常数级别的空间。如果题目给定的数组是不可修改的，那么就不存在满足时空复杂度要求的算法；但如果我们可以修改给定的数组，那么就可以采用原地数组哈希方法。这个方法自然是需要INT_MAX的数组大小(因为数就这么大，你可以扩展原空间或者复制到新空间里面去)，每个i位置上的数是i+1，然后从0开始swap，找到第一个位置与值不相符的地方就行了。 如果能使用常数级别的空间，那么就设一个INT_MAX的数组就好了。 但是有负数怎么办？这就不行了。有重叠的怎么办？ 用额外空间的话也只是O(n)而已。
荷兰国旗问题
荷兰国旗是由红白蓝3种颜色的条纹拼接而成，假设这样的条纹有多条，且各种颜色的数量不一，并且随机组成了一个新的图形，把这些条纹按照颜色排好，红色的在上半部分，白色的在中间部分，蓝色的在下半部分，我们把这类问题称作荷兰国旗问题。
抽象一下，就是数组中只有三种类型的数，对其进行排序。
一般而言，首先要考虑o(logn)，原空间。
设三个指针，边缘指针是下一项，它之前的都是最左边或最右边的数了，当中间指针指向两边的数，那么就跟两边指针对换，如果是中间的数，就没有任何关系，时间复杂度O(n)，但是超过三种颜色就不行了，可能是说，在一个数组里区分好几种队列，每一次移动都要移动相当量的数。如果不限的话，跟普通排序没什么区别了，用普通排序更好。
合并区间
输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]。
排序，如果后面的区间开始小于前面区间结束的话就合并删除好了。基本区间的问题总是先排序。
插入区间
必定先排好序，将区间插入后，合并区间就好了。当合并好后，可以直接将上下的统统加入即可。判断效率也不低。 第二种方法是依次比对扩充区间，最后排序去重，还是排序。
数组中重复元素
或者两个数的差值小于一定范围，用桶排序（哈希实现）
滑动窗口中的最大值
这个就是用大根堆实现的最好方式了，大根堆是优先队列的一种，这里问题的关键是如何判断堆里元素还是否在窗口内，关键就是连index也一起存上，就酱
链表
没有特殊说明，是有头的，有头结点的链表统一了算法的实现，无头节点减少了节点个数，头节点的存在就是为了方便操作，减少特殊情况。 链表排序，用最普通的选择排序最棒了。
k个一组反转链表
只想说没有什么特殊解法，正常做就好了。
集合
取差集，交集，并集(必须有序)
当然两个链表$A,B$是有序的，每个节点是一个区间，例如取$A-B$吧，每过一个i，保证j稍大于它，这样就会判断出等于，判断出等于后就减去就好了。本身两个集合自己自然是没有重复的，也是取稍大一个的，证明B之前的都已经被检验过。并集也是一样。 必然有序，然后一个额外的res
栈和队列
优先队列
先进，优先级大的先出，往往用二叉堆实现（二叉树堆是一棵完全二叉树）（最后一层的叶子节点全左排列）（二叉堆可以很容易用数组来表示），二叉堆的插入就是插入到最后然后挨个往前即可，删除时就是最顶部的，然后下面两个子节点挑一个小的，然后依次。。。都是logn，例如用于进程调度系统，
柱状图中最大面积的矩形
第一次学单调栈，如果能获取以每个柱为最高限度的矩形，求最大就可以了，另外单调栈在运算的过程中，是能够一遍获取到所有的柱子的最远距离的，左边遍历一次，右边遍历一次，宽度区间就出来了。 单调栈如果栈里的数大于该数，就全pop掉，这样里面的数据都是稍微小于该节点的，自然不要，这样就出来了。实际上，由于每次循环都是一根柱子，因此两次遍历可以放在一个循环中写，更进一步，在进行出栈操作时可以确定它的右边界！当被弹出栈时，说明这个节点高度大于等于要进来的节点高度，且中间没有更低的了，但是这里是小于等于，如果后面还有等于的，就添加不进去，实际上，如果还有等于的，那么相等的最后一个就肯定是正确的了，没有太大关系。。
规范化路径
给出一串路径(例如/home/ubuntu/../hello)，让其变成绝对路径，这的确是用栈，它说的单调栈应该是遇见.或者..就当场运算掉。
逆波兰表达式求值
栈的老问题了，看到数就一直压，看到操作符就弹出来两个。
中序表达式转后序表达式
只维护一个符号栈，如果栈里的符号优先级比较小就弹出来，如果是左括号直接放入，优先级重新计数。
单调栈
字符串
KMP算法
原串与子串比较，就这样比(分别在原串的第i位和子串的第j位)，一旦发现不相符了，j不是直接归零，而是变成一个较小的数，它能保证前面的仍然比对正确，一旦j到达终点，就比对出来一个串。 那么这个数组怎么构建呢？是子串自己跟自己的比对，没法只能硬记：
void Getnext(int next[],String s)
{
int i=0,j=-1; // i是主串位置序号，j是从串位置序号
next[0]=-1;
while(i<s.length-1)
{
if(j==-1 || s[i]==s[j]) // 对，这两个算一个状态
{
i++; j++;
next[i] = j; // 在这里就会补上0
}
else j = next[j];
}
}这没有任何意义，因为这是经过情况压缩的。这里讲一下next[i]=j，如果两个字符相等，那么它们的下一个字符进行设置，为什么，因为我们保证的是之前的字符串相同，当换掉之后，能保证之前的序列相同，同时，此时的仍要比较，形成继续，就是这样。
马拉车算法
它的优点就是在于用了对称点的回文信息 首先插入分隔符，没问题吧 有一个最右回文串，它的中心是C，它的右边界是R。 遍历的指针i，被放在C与R之间， 每次遍历，是确定以指针i为中心的最长回文串， 这里分情况了，通过跟C的映射，得到基础回文串长度，如果长度不超过最右边界，就填这个好了。 如果刚好的话，也只能是，毕竟限制是左边的。 如果更长的话，就延展R，看是否跟左边的相符。这时候就要更换最右字符串为本i。 为什么最右字符串呢？普通字符串怎么样呢？首先说你要确保i在一个回文串的右臂上对吧，如果是普通字符串，就不能保证是在右臂上了。 注意，添加#号的字符串的回文串都是奇数长度(单中心)，每个位置保存的长度是单臂长度(不包括中心)，也是实际回文串长度，注意#号的值也是有意义的，它代表双中心的长度。 获取开头下标也有简单技巧，用 P 的下标 i 减去 P [ i ]，再除以 2 ，就是原字符串的开头下标了。
最长不重复子串算法(是元素的不重复)
采用滑动窗口，每进来一个字符都要整体检查，或者从后向前检查，如果没有就加上，如果有就滑动窗口，$o(n)$复杂度。
最小覆盖子串(单词是否在这个字符串里)
经典的滑动窗口算法，指针r一直向右滑动，直到刚好成立，然后收缩l指针，直到不能成立，记录下最小字符串。关键在于如何确定里面有这个字符串，自然是哈希表，哈希表比对减1，26个元素数组即可。
将字符串拆分成回文子字符串的最小数量(切分)
动态规划，每个元素是当前字符串回文串最小数量，再来一个字符，就遍历前面的某一个元素，该元素之后是否为一个回文串，如果是就是这个元素的值+1，这样遍历下来取最小值就是了。时间复杂度双层循环了。
将字符串拆分成单词
这个蛮重要的，虽然英语多以空格分割，但是汉语没有啊，自然是动态规划， 在所有已过的字母中，前面已经形成了单词的不用管，剩余不能组成单词的字母，再向前看一个，加上该字母是否形成单词。 如果加空格返回字符串呢？所有的情况就都要保留着了，分为两个字符串数组，第一个是已经形成句子的，第二个是剩余字母，到最后挑剩余字母为0的就是了(剪枝就是减去超过最大单词长度的)。
格雷编码
格雷码是一个二进制数系，其中两个相邻数的二进制位只有一位不同. 3 位二进制数的格雷码序列为 000,001,011,010,110,111,101,100，（可以看成一个环，第一个格雷码 000 与最后一个格雷码 001 也只有一位不同）. 交替构造：从全 0 格雷码开始构造 k 位格雷码： 翻转最低位得到下一个格雷码，如 000 变成 001. 把最右边的 1 左边的位翻转得到下一个格雷码，如 001 变成 011. 交替按照上述步骤进行$2^k-1$次，即可得到所有的 k 位格雷码. 镜像构造：k 位格雷码可以根据 k-1 位格雷码以上下镜射后加上新位的方式快速的得到，如下图：
递归与回溯
解数独
就是回溯(回溯其实跟dp一样，可以保存状态的)，从左到右，从上到下的排列，如果没有，就返回上一个，进行改变，每一个位置都维护着一个占用数组，通过剪枝，效率还是蛮高的，就这样。
括号匹配
进行深搜或广搜，只需要一个int标志位，左括号+1，右括号-1，这个标志位不能为负，到最后整体为0，就是如此
图
欧拉回路
不重复地经过每一条边，最后回到原点。判断它的做法是一是判断是不是孤立点（度为0），二是判断度是不是偶数，就是这么简单。度是进去有几条线或者出去有几条线。
汉密尔顿回路
不重复地走过所有的节点(不必通过图中的每一条边)，最后回到原点。没有充分必要条件，只能暴力解。
有向图中的环
这叫拓扑排序，经典的拓扑排序题。 根据依赖关系，构建入度数组(是二维数组)，表项都是入度。 选取入度为 0 的数据，根据邻接表，减小依赖它的数据的入度(就是消消消)。 找出入度变为 0 的数据，重复第 2 步。 直至所有数据的入度为 0，得到排序，如果还有数据的入度不为 0，说明图中存在环。 实现邻接表的方法绝对有100种以上。邻接表就是用来存储图的。这里就适合一个二维数组，每次只消仅有这个值的，然后别的行也同时消去，直到最后全部消去，就算成功，否则会出现明明还有数据，但是没有那种单一的情况，那就是有环了。 如果没有环，返回顺序的话，就每次消去的时候记上就可以了。
普利姆算法
用于构建最小生成树的，从一个点开始，不断求其连向外的最短路径，直到生成这个最小生成树。
克鲁斯卡尔算法
用的是线段，先pop出一个最小的线段，看它是否在两个连通分量之间，不是则抛弃。
迪杰斯特拉算法求最短路径
就是绕圈取最小值的方法，它的原理是比较这个点直接到原点的距离和其他已知点最短路径到它的距离， 找到最短路径就填入了。它只能求任一点到某一点的距离。贝尔曼-福特算法(Bellman–Ford algorithm )用于计算出起点到各个节点的最短距离，支持存在负权重的情况，它的原理是对图进行最多V-1次松弛操作，得到所有可能的最短路径。其优于狄克斯特拉算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达O(VE)。所谓的松弛，以边ab为例，若dist(a)代表起点s到达a点所需要花费的总数，dist(b)代表起点s到达b点所需要花费的总数,weight(ab)代表边ab的权重， 若存在:
(dist(a) +weight(ab)) < dist(b)
则说明存在到b的更短的路径,s->…->a->b,更新b点的总花费为(dist(a) +weight(ab))，父节点为a 这也表明了的解斯特拉算法不支持负数。
弗洛伊德算法求最小路径
每个顶点都有可能使得另外两个顶点之间的路程变短。 基本思想就是：最开始只允许经过1号顶点进行中转，接下来只允许经过1和2号顶点进行中转……允许经过1~n号所有顶点进行中转，求任意两点之间的最短路程。举一个例子：开始时，第一个点连接其他的点时，用第二个点来判断，即判断(1,3)和(1,2)+(2,3)，然后判断完成一遍，紧接着用3来判断一遍，，，就是这样。这个可以求任一点到任一点的距离。
二叉树
完全二叉树，都有左右孩子(但最后一层没有满没关系，其余每层节点数都达到最大值)，完美二叉树，所有孩子在同一层。
二叉树的迭代遍历
用栈了。如果有左节点，就一直压栈，如果没有了，看右节点，压栈后继续左节点压栈，这样就实现了遍历。
二叉搜索树的迭代器
可以将二叉搜索树展开到数组中输出，但是会占用空间，如果是受控递归，只需要一个层大的栈就可以了，如果有，一直到最后的左子节点，没有了，输出本值，然后转移一个右节点，继续，如果右节点也没有，输出，这样。has_Next若栈中还有元素，则返回 true，反之返回 false。所以这是一个 O(1)的操作。都是O(1)操作。
二叉树层序交叉输出
你明白什么意思啊，这个解法就是两个队列，就可以实现分层效果了。一个队列就正向输出，另一个队列就是反向输出。
二叉树原地成链表
关键在于一个全局前驱节点，例如都放在左孩子成为一个链表，这样每处理一个节点，那么这个节点就会存入前驱节点，等回溯的时候，欸，就很自然的连上了。
二叉树序列化和反序列化
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
搜索二叉树节点的最低公共父节点
判断数字，当分叉时就是公共最近父节点
给二叉树节点添加一个next指针(一层一层指)
这个指针横着指，一层一层的指，可以用双队列处理，不难，但是很重要。但关键最后是完美二叉树才行，当然，看怎么用了。
生成所有由 1 ... n 为节点所组成的 二叉搜索树
如果仅仅是得出数量的话，这是一个动态规划题，如果输出树的话，就是一个回溯题，遍历完各种树然后输出，这个题要层序输出，而且空位置要填null，好像不是问题，填入就好了，那么如何从这种数组恢复呢？维持一个队列然后一层一层装就可以了。
恢复二叉树
二叉树中的两个节点被对调了，现在恢复它，因为中序遍历是递增的，只要找到两个递减位置就可以了，如果只有一个递减的，那么就是相邻的。中序节点的返回就是再遍历一次就可以了。直接隐式遍历就可以了，遍历的同时记录出错节点，就是这样。
构造二叉树
根据数组构造二叉树，当然必须是排序二叉树(也叫搜索二叉树)了，不然谁知道遍历到哪里了(当然还不能有重复元素)，而且还必须至少有两个序遍历，前序就用递归，就一直递归下去就可以了，中序遍历的话，中序遍历是没法做的，只能根据前序遍历来。必须同时给出前序遍历和中序遍历，根据前序遍历找到父节点，根据中序遍历找到左子树和右子树，递归之。
二叉树的最大路径和
就是一串路径的最大和，不一定从根节点开始，方法是回溯法，从上而下做，很像动态规划，该节点的最大路径和就是自己加上子节点的最大路径和，就是这样，二叉树天然有动态规划的优点。
霍夫曼编码
霍夫曼编码是根据出现概率(权重)来编写的二叉树，概率低的代码也长，就是挑取两个权重 小的组成新节点，新节点的值为两个节点的和，左边是0右边是1或者左边是1右边是0都可以。 带权路径长度WSL=叶子节点*其所在层数(算上叶子节点，不算根节点，或者说，到根节点的路径长度)
最小(大)堆
最小(大)堆的特点就是能够始终保证第一个最小(大)，构造堆并不是给一个数组排序，而是依次插入，或者说，不是从后向前排序，是从前向后遍历，然后往前排序。 然后使用，是自上而下的方法，把根节点去除后，把最后一个节点放到首部，然后从上而下进行比较交换。
完全二叉树节点数的快速计算
可以比O(N)还快实现,一个非常完美的二叉树有n层吧,1,2,4：1,3,7=>2^n-1，就是如此。
BST第k小的元素
用遍历+大根堆，将元素全部取出然后放入容量为k的大根堆，就是如此了
二叉平衡搜索树AVL
- 它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1。
- 它的左子树和右子树都是一颗平衡二叉树(左子节点小于该节点，右子节点大于该节点)。
- 插入删除过程中需要几种旋转完成操作。### 红黑树
10亿数据进行不到30次比较就能查找到目标
红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质：
性质1：每个节点要么是黑色，要么是红色。 性质2：根节点是黑色。 性质3：每个叶子节点（NIL）是黑色。 性质4：每个红色结点的两个子结点一定都是黑色。 性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。 八种条件，太难。
B树
B树由于良好的查找性与局部性，对磁盘更友好，往往被用于数据库。
败者树
败者树相当有意思，它可以实现n路归并的算法，每个节点存放的是比较失败的那一项，从而在下次比较的时候好比较，最后的根节点的相反方就是胜利者，当然，每次都是胜利者往上传，胜者树也是胜利者往上传。
TRI树，字典树
就是这样一棵树，自动补齐有大用
树状数组
例如计算右侧小于当前元素的个数，注意是所有元素都要算
线段树
哈希表
搜索
二分搜索
关键在于理解思想，就不写代码了。二分搜索的一个注意点就是不要数字溢出，因为往往会比较大。
找出数组中第n大的数
通过快速排序，快速排序能够把哨兵左右排好(每个阶段都要做完，不会损失时间复杂度的)，然后根据第几个到相应区域继续排序，直到排完，就是这样。 但是前三个就不必这么做，完全可以先找出第一个，然后找出第二个这样解决。
贪心
跳到最后位置
从正向出发，在该数笼罩的范围内，找到跳的最远的那个，就是那个。时间复杂度是O(n)
文本左右对齐
贪心，尽可能往一行塞尽可能多的单词，塞不了再匀。或者说，这就是最普通的做法吧？
11. 动态规划
找到二维数组中的最大矩形
注意是矩形，因此长方形也可以，因此每个节点都保存有当前最大的宽高，每一个点取最小值，是为最长的宽高，最后遍历一遍获得最大矩形。
单词1转换成单词2所使用的最少操作数
编辑距离算法被数据科学家广泛应用，是用作机器翻译和语音识别评价标准的基本算法。最直观的方法是暴力检查所有可能的编辑方法，取最短的一个。所有可能的编辑方法达到指数级。动态规划算法用 D[i][j] 表示 A 的前 i 个字母和 B 的前 j 个字母之间的编辑距离。
买卖股票最佳时机
实际上是找后面减前面的最大值，这里的关键是维护了一个最小价格，也就是说在动态规划数组外还要维护一个变量，这个是之前没想过的。 当然这只是一次，如果多次的话，用动态规划版的状态机，实际上是个多维数组，但每维都有特别的含义，例如dp[3][0]表示第三天未持有，这样两层循环，填到最后就是最终结果了。关键在于这个状态机思维。 如果是两次呢？
排序二叉树总数
这道题放到二叉树不对的，只是用了二叉树的形式而已。这道题是两种函数叠加形成的。比较困难。
组合与排列
组合(子集)
一个递归，一个回溯，组合的效率是比较坑爹的，一个一个存入也要O(n^2)的时间， 回溯算法就是前序遍历树，树的结构为
固定大小的组合
回溯法可以剪枝，当大于count的时候就不要递归下去了。只有回溯法可以使用了。仅仅的区别只是最开始的res.push有判断和return而已。
排列
排列也是用回溯，这个回溯是从0开始选择，判断新来的数是否contain了，就是这样。之所以不会乱序是因为for循环的缘故。按大小进行排列的话，可以递归实现，每位每次一个数，接着下一层，如此填入res中。字典序算法的话，就是下面的算法，你可以从123456789最小开始，这样填入。生成 N! 个全排列需要时间 $O(N×N!)$(生成下一个排列是$O(N)$).
获取字典序的下一个排列
我们希望下一个数比当前数大，因此只需要将后面的大数与前面的小数交换，就能得到一个更大的数。 我们还希望下一个数增加的幅度尽可能的小，这样才满足紧邻的要求。在尽可能靠右的低位进行交换，将一个 尽可能小的大数与前面的小数交换。将大数换到前面后，还需要将大数后面的所有数重置为升序，升序排列才是最小的排列。
获取指定位置排列
普通递归全排列即可，递归时剪枝，深度优先，我们在递归前就可以通过阶乘预先知道子节点数量，时间复杂度超级小。（能否在O1时间计算出？）
获取指定位置排列（允许重复）
用最小堆或动态规划，最小堆比不上动态规划不说了
和为某个特定数的所有组合
给定一个不重复数组和一个目标数，找到数组里的，emmm，几个数相加是目标数，返回这几个数的数组，是二维数组。 输入：candidates = [2,3,6,7], target = 7, 所求解集为：[ [7], [2,2,3] ] 解法是递归+回溯，击败99.8%，这就是最好的，回溯就是树，树你要想清树的结构，然后就好办了，根据树的结构写递归代码。
数学
把分数变成小数
关键就是在于循环小数的判断，如果余数是循环的话，商也是循环的。
只出现一次的数字
异或：如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。 任何数和 0做异或运算，结果仍然是原来的数 任何数和其自身做异或运算，结果是 0 异或运算满足交换律和结合律
求众数(默认有数字超过多半数)
这个并没有什么直观的做法(除了哈希表)，最好的用投票法O(n)，什么是投票法(Boyer-Moore 算法)呢？ 我们维护一个候选众数 candidate 和它出现的次数 count。初始时 candidate 可以为任意值(比如第一个)，count 为 0；
求中位数
可以使用两个优先队列，保证这两个队列一致(前提是排好序，但是排好序直接求中间就可以了。。。)
颠倒二进制位
不用循环的话，用分治法，虽然它们的时间复杂度都是O(n)，就算颠倒普通十进制数字，也只是循环做而已。
数组按位与
这个问题的关键是当数特别大时有更好的算法，我们观察按位与运算的性质。只要有一个零值的位，那么这一系列位的按位与运算结果都将为零。它的规律是最大的那一位是1,后面都是0,因为这是连续的，进一步说，是第一个数字和最后一个数字的公共前缀，我们通过右移，将两个数字压缩为它们的公共前缀。在迭代过程中，我们计算执行的右移操作数。将得到的公共前缀左移相同的操作数得到结果。
返回二进制数中1的总数
- 不断把数字最后一个 1反转，并把答案加一。当数字变成 0 的时候偶，我们就知道它没有 11 的位了，此时返回答案。 这里关键的想法是对于任意数字 n ，将 n 和 n−1 做与运算，会把最后一个 1的位变成 0(不是最后一位！证明稍显困难) 。
欧里几德算法，辗转相除法，给定两个正整数m和n，求它们的最大公因子，即能够同时整除m和n的最大正整数
m%n=r,然后n%r=k,直到k为0，那么r就是答案。 更相减损术是任意给定两个正整数；以较大的数减较小的数，接着把所得的差与较小的数比较是否相等，并接着以大数减小数。继续这个操作，直到所得的减数和差相等为止。则就是最大公约数。 扩展的欧里几德算法，am+bn=c
求一年是否是闰年
1.普通年(不能被100整除)能被4整除为闰年。(如2004年就是闰年,1900年不是闰年) 2.世纪年(能被100整除)能被400整除的是闰年。(如2000年是闰年,1900年不是闰年)
四平方和定理
四平方和定理证明了任意一个正整数都可以被表示为至多四个正整数的平方和。
位运算
88