还有人不知道算法的重要性？看算法大神（左程云）怎么带你七天刷爆LeetCo...
对数器=（随机样本生成器+正确解题方法）
return 正确结果；
然后调用自己觉得好的办法与对数器得出的结果进行对比
插入
排序，外层循环控制来到位置，内层循环决定是否进行交换，如果当前位置比左边小直接continue，初始有序状态会影响算法的时间复杂度。
除功能必须要求的原因之外，另外开辟的空间
记录当前位置是否大于等于，符合就记住，并进入下一次二分，如果下一次不成功，就结束，发送最近一个数
链表反转（普遍位置）head为当前节点，pre为上一节点，记录下一个节点为next=head.next;反转链表head.next=pre;反转完成来到新位置pre=head;head=next;重复操作
双向链表，实现头/尾部插入删除操作，是栈和队列的基础
3.栈：栈顶进栈顶出（规定那边是栈顶就行）
4.队列：头删尾插
栈
队列
数组队列
最小栈实现1
实现2：比最小栈栈顶小于等于的时候压入，只有和data栈顶一样大的时候才弹出返回，否则只是返回最小栈peak
栈实现队列
哈希表在非基础类型中不按值传递
归并排序实现细节
递归版
非递归版
快排序实现细节
荷兰国旗问题
快排
快排3.0
注意：堆和搜索树的区别是，搜索树是自顶向下找到自己的位置的，而堆是像队列一样每次进入时先排再队尾，然后向上heapInsert找到自己的位置，是先插后找。
堆的push利用HeapInsert
2.堆的pop利用Heapify（先--heapsize，因为下标是0开始的）
堆排序：先建成堆；每次拿heapsize-1下标处的数据与0下标的数进行交换；再heapsize--；然后heapify.....重复
堆排序
建堆：一种是向上看，这种是向下沉
堆中修改值resign
当一个数组每个数据离它正确排列位置不超过k时的问题
comp(o1,o2):返回-1则o1在前，否则o2在前
前缀树
结点（内含next节点数组）
insert
search
所有加入字符串中有几个以pre为前缀的
delete
实现2
基数排序（高位数字比低位数字有决定性，且后来者会颠覆前者）radixsort
newCount[i]=Count[i-1]+count[i];
help[--newCount[array[j]位值]]=array[j];
对于基础类型的数据，稳定性没有意义，因为基础类型是按值传递的，对于人来说两个相同的数字即便互换了顺序也没有实际影响。
对于非基础类型来说，比如一组数据开始按照时间顺序来排列，后来应业务需求的影响又按照大小来排序，如果具有稳定性的话，那么虽然整体是按照大小来排序，但原来时间的顺序也没有被破坏，这一点对于很多产品都很有意义。一下是各种排序特性总结:
如果奇数放在左边偶数放在右边——0/1标准的partition，如果这可以做到的话，那为什么partitionSort不做成有稳定性的呢？
略
先压入右后压入左是为了保证左孩子在栈顶进行打印，并且压入了右孩子便于以后返回来遍历右孩子先序：
后序：先压左再压右，此为头右左即为后序的逆序，把弹出打印改为弹出到另外一个栈中，最后打印这个栈。
一个栈实现的（先压入头节点）：h是进行标记打印过的位置的，如果左右都没有打印过就先压入左（并更新位置到左），如果左打印过了而有没有，就压入右，如果左右都打印过啦就弹出打印栈顶
注：第一个if必须包含对右孩子是否打印过的判断，否则上一次打印了右孩子，而左孩子没有了标记指针就会误以为左孩子没有打印过（右孩子都被标记过，那么左孩子必然也被标记过）
c进行peak相当于更新操作
中序非递归实现：尽量压入左边界，没有左边界可以压了就弹出打印，并且来到右树位置，栈中数据相当于一个线索，尽量走到最左边再进行处理
******************************************************************************************************************************************************************************
其它实现先序中序后序遍历见P30Morris
******************************************************************************************************************************************************************************
二叉树宽度优先遍历（队列）
统计二叉树最大宽度：没有到达下一层就++；否则就结算，重新统计下一层，而最后一层无法逾越，所以最后结束循环后还要结算一次。
levelmap节点在那一层的hashmap；curlevel当前正在统计层；curnodelevel当前节点层数；
curlevelnodes宽度（每次++）；max更新最大宽度
由于队列实现的宽度优先遍历的特性，最右一个本层节点必然在队列后面的位置，所以第一次遍历到节点是下一层的时候，必然说明一一本层节点已经全部遍历完了！！！
不用map实现：发现每一层结束位置即可
curend：当前层最右节点；nextend：下一层最右节点......
nextend一直不断更新向右边动，记录下一层最右节点，以便curend更新
如果当前节点cur是当前层最右节点就结算，如果不是就++
当cur来到了当前层最右节点，则nextend势必也会刚好找到当前层最右位置，
注：而且还会保证最后一层右边界不会越界（判断不为空才会更新）
左右孩子不为空才进行的nextend更新也保证了不会出现隔一层统计的情况
二叉树的序列化和反序列化
序列化
反序列化
按层序列化
树的打印（递归实现）：右头左的顺序是因为，右侧节点位于最高层，而且要先深度遍历打印
查找中序遍历结果的后继节点
纸条折痕问题
二叉树递归套路
平衡二叉树
两节点最大距离
搜索二叉树（任意一棵以当前节点为头结点的树，它的左子树都比自己小，右子树都比自己大），下面进行判断（返回最大搜索二叉树的头节点，即递归在不满足搜索二叉树处停止，并一步步向上返回此节点）：
个人观点：如果左树和右树都是搜索二叉树并且符合当前要求，size=左size+右size+1，更新max，min....
如果有一个不满足要求则取最大的搜索子树向上返回
派对快乐值问题：
个人观点当前头节点来：头节点快乐值+所有直接下级的直接下级快乐值之和与当前头节点不来：所有直接下级的快乐值之和的对比（和本题不太一样，请指正)
个人观点：对于初学者尽量将递归函数单纯的理解为一个黑盒，一个可以完成需求的黑盒，应该注重的是对于解决问题的宏观策略一一base case+基本策略
决定来时：当前节点快乐值+直接下级不来的最大快乐值
决定不来：0+（直接下级选择来或者不来的最大快乐值的最大值）累加
以与当前节点有关无关划分情况
第二期
打表
我们只能站在先手的立场上去尝试解决问题，这是从逻辑上来说的，不能同时站在两个立场。
个人观点：n-base已经代表当前后手的境地了，而当前后手的后手就是现在的先手。
暴力解、打表
矩阵处理技巧：不要把想法限制在局部坐标的变换或者变化规律上，而是有一个宏观调度
个人观点：应该以最直观的方式来实现一一观察它最朴实的移动方法
打印之字形矩阵A、B同步走，A不能再往右了就向下走，B不能再往下走，就向右，然后确定上下打印方向
转圈打印矩阵
原地旋转矩阵
会议问题
放灯问题：
暴力递归：如果当前位置是x跳过，递归下一步；如果是“。”就进行放灯何不放灯的抉择，分别再递归下一步，最后取min，base case为检测是否都照亮
for循环验证是否都照亮
lighes.remove是现场恢复的操作
贪心试法个人观点：来到当前节点如果是x就跳过
一、 i-1位置是是×时（从当前i位置观察）
1）。。。放于i+1位置，递归进行i+3位置的尝试
2）。。x放于i或者i+1无所谓结果一样，递归i+3
3）。x放于i位置，递归i+2
/*二、i-1位置是。
1.i-1位置放灯了
1）。。。在i+1位置放灯，递归i+3
2）。。x在i或者i+1位置放灯都一样，递归i+3
3）。x直接递归i+2
2.i-1位置没放灯，检测i-1是否照亮，若未照亮，不论如何在i位置点灯，递归i+2；若照亮了，就把i-1当x和一、处理方式一样*/
老师讲解不需要二、情况,因为i位置不应该被之前位置决定，但是依然可以用一、的方法，因为之前位置不影响现在位置等同于把i-1位置当作x
并查集解决连通性集合问题
Unionset初始化
findfather兼具寻找代表点和扁平化并查集的优化操作
学生归类问题，以三个字段作为是否归属一个集合并且合并的判断依据，以hashmap：key=string
value=user
图算法：图是点集和边集的集合
邻接矩阵法
点结构描述：value代表点的值；in、out分别代表入度和出度；nexts代表由自己出发的直接邻居；edges代表由自己出发的边包含权值、出发点、终点
边信息
点集+边集
将其他不同形式图的描述转化成这种标准形式
如果图的点集没有出现过from、to这个点就进行初始化（等下进行写入操作）
拿出from和to对应的点来fromNode和toNode
构建出这条新的边，接下来对两个点进行写入操作，最后边入集合
宽度优先遍历：队列实现，hashset防止重复加入形成环
预先进入一个节点，进入循环，先弹出后打印，然后for循环枚举没有set过的就进队......
深度优先遍历：栈实现，预先压入栈一个，后打印，进入while就pop栈顶元素，进入for循环并观察它是否有未进入set的子节点，如果有，则再次入栈，并把没有进入过set过的登记压栈，然后马上break，不深究当前节点所有的孩子，留到以后再去遍历......
在图中找到入度为0的点，入队，消除他的影响，重复......
K算法：先把所有边从小到大排序，找到最小边看两个点是不是一个集合，不是一个集合就要这条边，利用并查集归为一个集合，否则跳过寻找次之.......
找最小边权值的方法尝试用小根堆实现，
进行无向图其实也可以，因为只是反过来对另一侧不会出现重复情况而已，这一点是在并查集的isSameSet决定的，可以进行优化
用整体权重最小的边的集合，不改变连通性。
K算法：并查集+小根堆
P算法：任意指定出发点，解锁有关此点所有的边，选择最小边，查看此边另一端是否解锁过，如果解锁过就消除此边，否则就进行解锁，并把和这个新节点所有有关的边进行解锁，下一次再在解锁边集合中找最小边......
解锁的边和点放在set中，还可以实现忽视某些不符合规定的边
最外层for循环防止森林出现
K算法和P算法区别：K算法寻找最小权值边是从全局里面查找的（小根堆），而P算法是每解锁一次才查找一次最小权值边一一局部查找。
distanceMap
迪杰特斯拉算法（最短路径问题）
选择当前最短路径进行封存，并作为出发点，由此出发查找他能直接到达的所有位置，如果比远距离小：重置以出发点到达目的地的所有距离。计算完成后，重复......注意，已经到达的最短路径无需更改
/*旅行商问题个人观点：
base case：重回出发点，检测是否所有点都走过
无路可走 ：return false；
基本策略：暴力的每个地方都进行尝试（枚举当前节点nextEdge）*/
个人认为迪杰特斯拉算法可以进行优化：申请一个数组，长度为点个数，以下标代表节点a、b、c....而数组内部代表a->a,a->b,a->c的距离，初始化内部值无法到达的置为max，将找到的最短路径封存入hashmap，并在数组中置为0，每次查找数组中非0的最小值......
可以利用小根堆进行加速，解决弹出最短边以及改堆值重建小根堆和添加新值的问题，这不是普通堆。忽略重回节点的边。
暴力递归：base case+基本策略
...............................................................................
个人观点：对于逆序一个栈，即便我们一开始没什么思路，但是仍然可以从直观上进行一定的分析，作者本身进行了提示一一递归，直观思路是：
每次提取出最底层的数据，然后把他压入一个新的栈中，如果配合递归那就是，每次提取出栈底元素，然后交由递归再提取出新栈的底层元素，这样就实现了1>2>3(3为栈底)这个原始栈提取元素栈底的顺序是这样的：第一层 3 ；第二层 2 ；第三层 1 至此递归到达最底层（栈空了），然后下面跳出递归，进行重新压入新栈的的操作，即本方法是这样的
base case：到达原始栈栈底 return
基本策略：先将本层中原始栈栈底取出，然后利用递归进入下一层重复这一操作直至结束
结束后把取出的每一层栈底元素压回新栈........（仅个人意见，不对指教，非科班出身请见谅）
函数优先执行的是递归调用上面的部分，所以需要优先完成什么操作要在递归调用之前进行......
本题中取栈底元素的操作也用了递归实现（存在现场恢复）
整体实现
这个问题揭示了递归栈对于数据的保存作用，值得研究。
递归必须保证子问题只是比原问题规模小而已
对于暴力递归求解问题，不论是针对先手后手型问题，还是一般的逐层求解性问题，一定不能考虑计算机是怎样实现的，容易被“催眠”。我们只需要站在当前立场上，按照最为直接、朴素、直观的态度处理问题即可！！！！！
打印字符串全部子序列问题：当前字符进行要与不要的抉择，然后递归对下一个字符进行同样抉择，最终实现每一个字符要与不要的抉择
进阶：不重复打印，liyongset比较浪费空间
打印字符串的全排列
每一层函数进行枚举，然后下一层交给递归（含现场恢复）
不重复的全排列：可以用set，但是也可以利用分支限界一一在枚举阶段摒除相同的两个字母和当前i位置交换，在源头上过滤
从左往右的尝试模型：
如果已经超重就无效，如果方案有效但是没货就返回0；下面对于要货或者不要货物进行抉择，然后递归进入下一层，最终对两种抉择进行比较取舍。
范围上的尝试模型：
每个人绝顶聪明的意思是：
当前先手得到最优的结局，而后手承受先手带来的最差的结局
以往的决策都是对当前一个元素进行取舍，这次对最左和最右两个元素的范围进行选择和取舍
海盗分硬币问题：方案只有赞成票超过一半才能通过，否则杀死
剩余E:必然同意
剩余·DE:D必然被否决，E得全部金币
剩余CDE:C告诉D如果自己死它的结局，迫使D同意自己C：100 D： 0 E：0
剩余BCDE:B告诉后人自己死他们的遭遇B： 98 C ：0 D：1 E：1
剩余ABCDE:同理A ：97 B： 0 C ：1 D：2 E：0
每个人都和紧挨着自己的人是最大的对手，在此基础上针对自己的对手，并且给对手之后的人更大一点的报酬即可（只要人数超过一半）
欧拉信封问题：一个村子里每个人必须寄出一封信收到一封信，问总共有多少种寄信方式？
1个人有0种方法，2个人有1种方法，3个人有2种........
n个人中，当a寄给b一封信，则b可以选择回寄给b或者不回寄给b一一
1）回寄则问题缩小成为n-2规模
2）不回寄，则a还差收到一封信，b差寄出一封信，二者可以视作一个人一一寄出一封信收到一封信，问题规模缩小为n-1
int f（int n）{
base case：人数为1 return 0；
2 return 1；
3 return 2；
基本策略：return 4*（ f（n-1）+f（n-2））；
}
base case：来到length就return 1；
如果未来到length但是没有地方可以摆return 0；
基本策略：在当前行每一列进行尝试，然后标记，递归进入下一行......
判断：数组记录摆放列，每次遍历数组非负项，只要数据不同并且......
.
在本层递归中，对于某一列的一位标记1，左移得到左限制，右移得到右限制，三者或运算为总限制，下一级递归挑选未标记过的位置重复此步骤
00001000
00010000--->00011100;下一层00011100选第3-->
00000100
00100000
个0的位置标记1 01000000-->01110000并与之前
00010000
标记想与01111100
base case：当来到最后一步，检测是否到达，是返回1，否则返回0
res=0；
基本策略：如果来到最左res+=process（向右走）；
如果来到最右res+=process（向左走）；
除此之外res+=process（向左）+process（向右）；
return res；
动态规划初级版一一记忆化搜索
只有含有重复子问题的递归才有改成动态规划的必要
最重要的就是分析清楚有几个可变参数，这关系我们要做一个几维表
背包问题改动态规划：
字符串问题改动态规划：一个可变参数
抽纸牌问题改动态规划：L和R作为两个可变参数组成二维表，L不可能大于R，否则就越界啦！！！
记忆化搜索和动态规划的区别：如果决策过程中没有枚举行为（有限动作），记忆化搜索没必要改为动态规划，否则有必要改为经典动态规划。
将n种不同面值的纸币凑成一个特定值：两种思路，第一种将当前货币枚举m张，下一层递归不再使用这张货币再去尝试；第二种当前将n种货币试一遍（只试一张），下一级递归亦如此。。。。。
for循环中已经包含了base case的一部分即：rest<0时，return 0；
改成记忆化搜索：所谓后效性问题是指可变参数未找全导致问题未全部解决。
改成经典动态规划：
由于内部含有枚举行为，还可以进一步优化：
略
未来知识
多样本位置全对应的尝试模型：
递归尝试 int f（str L，str R，i，j）：str1在i位置，且str2在j位置公共子序列下一步递归一一
主调用f（str L，str R，0，0）；
base case：如果两个字符串越界，
return 0；
if（L[i]==R[j]）
return 1+f(L，R，i-1，j-1)；
else
return max（f（L，R，i+1，j），f（L，R，i，j+1））；
此问题包含三种可能性：既不以str1又不以str2结尾（缩小问题规模），以str1或者str2结尾（分别缩小规模进行尝试取max），既已str1又以str2结尾（说明当前必然相等1+二者缩小规模的比较）。
之所以会感到困惑一一如果当前i和j一个字符相同，那么他真的为公共子序列做贡献了吗，当然是，因为我们是从左往右一点一点考虑的，产生这样的困惑是因为我们忽视了当前的决策正是建立在之前的基础上，它不是空中楼阁，左边的公共子序列长度我们已经检查过啦。这种困惑也曾经在其他递归求解中出现过，注意！！！！！！
若i和j位置相同三种情况进行比较
寻找业务限制的尝试模型
在之前一些尝试模型基础之上，添加关于本题的具体限制，本质上就是精细化的前几种尝试模型。
常规思路就是当前决定洗杯子，还是挥发杯子，然后对这两种行为做具体执行，进入下一层继续抉择。本题中洗咖啡机洗咖啡的时间是有业务限制的要么咖啡没时间洗，要么洗咖啡机没有空闲时间
。
决定挥发杯子，那就直接跳到下一层进行下一个杯子的抉择，但要给出洗咖啡机能用的时间。
决定洗杯子，先看一下咖啡杯什么时候能洗，然后去洗，进行下一层咖啡杯的抉择，但要给出洗咖啡机能用的时间。
不管当前决定洗或者不洗，都得让i后面的杯子也都洗完，最后才能比较时间，不能只管当前这一杯。
1）wash计算决定洗则下一次咖啡机有空的时间，next1是后续决策过程所用最短时间，二者取max即为index及其往后都洗完所用的时间
/*p1记录决定洗杯子index并完成index++所到的时间点；p2记录挥发当前index杯子并完成index++所到的时间点，二者取min*/
2）dry是挥发当前杯子，next2是将后续.........
最后二者取min
改为动态规划：
*********************************************************
*********************************************************
*********************************************************
全问题
*********************************************************
******************************************************************************************************************
三维动态规划：建立出空间感
象棋问题：象棋棋子马规定在棋盘内部必须走完n步，且到达特定目的地，问一共有多少种走法？
分析：马在棋盘中在不越界的情况下可以走八个不同的方向，所以在当前层枚举各个方向的可能性，然后下一层重复此抉择，base case为最后一步是否到达目的地。（如果越界return 0；）
可变参数：棋子坐标、剩余步数
给定两个参数n、m表示n行m列，给定鲍勃一个初始坐标（a，b），他向上下左右等概率随机的，在给定参数k。一旦越界就会死掉。求存活概率。
一共有4的k次方种走法，暴力递归像上下左右四个方向尝试并进行统计一一最后一步到达位置不越界即为1，若有越界行为即为0.......
找钱问题
一种钱只在当前层尝试，下一级递归不再使用
斜率优化：当填表的时候有枚举行为，就看邻近的位置能不能替代，只和观察有关，与原题意无关。
经典哈希函数：
1）输入域无穷，输出域相对有限
2）相同的输入参数返回相同的输出值（可以用来检测文件传输是否正确）
3）由于输入域无穷，输出域有限，所以有可能会发生哈希碰撞，只是几率非常小
4）假如每一个输入in都会在大域上映射一个点，则每一个小圆圈圈中的点几乎一样，即均匀性、离散性（即便输入有规律，哈希函数也会让它尽可能离散均匀）
in1通过哈希函数得到out1再经过模运算得到m1
如果能保证在哈希域上均匀分布，也就能保证可以在m域上均匀分布
假设有一个大文件都是无符号整数0一一2的32次方-1（42亿++），40亿个，如果只给1G内存，返回出现最多的数？
哈希表key为数，value为频率，这样内存根本不够用，一条记录至少需要8字节，最差情况这40亿个数不一样，一共需要320亿B内存即320G，考虑其他方法
对于每一个数调用哈希函数得到一个值，然后取模100，分配在100个桶中，由于不同的数根据哈希函数会尽可能地离散均匀，然后取模之后也是离散均匀，那么我们只需要观察哪一个桶最多，之后再针对这个桶的数进行哈希筛查（一个数做以上步骤属于这个桶的才归入统计中），所用内存320G/100。
注：说白了就是先大致分析一下什么性质的数最有可能频率最高，然后对这种性质的数做仔细筛查
num[数据取哈希函数%100]++；
哈希函数的实现：
技术一：当某一链表长度到达6时，由于哈希函数的性质，也可以认为其它链也到达6，后续杯需要扩容为2倍
n个数需要扩容O(logn)次，而每一次扩容的代价是全要重新计算哈希值、重新挂在格子上O(n)，所以总的代价是O(n*logn),单次代价是O(logn)，而又因为每个链的长度可以自己定义很长，故可以视为O(1)。用哈希表还有删除操作，更会减少扩容次数。
技术二：JAVA等虚拟机语言特有的离线扩容技术
注意，哈希表是使用上O(1)的时间，理论上O(logn)
具体语言对于链表可能替换成为有序树、开放地址法……
主要是删除操作不能硬删，否则会有很多“洞”，令最后一条记录去填补这个洞
布隆过滤器
解决黑名单问题、网络爬虫问题，允许一定的失误率，但是布隆过滤器只可能错杀。
基础知识
位图：假设有一个int数组含100个元素空间，一个元素4字节一一32比特，对于黑名单上每一个文件取哈希函数后并对于每一位进行标记，就可以大大节省空间。而这种位图需要基础类型拼一一i
int [] arr=new int [10]相当于320比特
numindex定位在哪个数上面去找这个位，bitindex是具体位，可以在这一位进行标记和查询状态......
布隆过滤器就是一个大位图
一个url1文件分别调用k个哈希函数，然后取模，将那一位置1，多个哈希函数相当于对url1提取不同的特征信息，以便进行识别检验。同理url2......
查询的时候，url文件分别调用k个哈希函数并取模m检验是否都进行了标记，如果没有都进行标记，说明没有在黑名单。
那么使用多少个哈希函数呐，m应该是多少
如果m很小，经历过100亿个url文件后，格子可能全部描黑了，都是黑名单。m决定失误率，而k太大会导致一条url文件描黑很多格子。
一致性哈希原理
逻辑端不需要维持数据，数据端需要维持大量数据。逻辑端只是使用，数据端是进行维护。尽量选择种类比较多的，词频分配比较均匀或者说每个种类都有一定的数量。
当业务扩展时，数据大规模增加，导致机器数也会增加，数据量的重新分配就成了一个问题。
一致性哈希不需要模运算，m1、m2、m3根据哈希函数得到三个值，在环上各自的到一个位置，每输入一条信息打到环上一个位置，顺时针最近的就是他的归属机器。逻辑端的所有有序数组载有这三个机器数，根据二分法可以找到一条数据的归属机器。
现在增加一个机器：
这样做存在两个问题，初始时数量很少的机器怎么把环均分，即便可以均分那么增删一个机器又怎么保证均分呢？
解决方法是虚拟节点技术：假设三台机器各有1000个字符串，m1每一个字符串都算一个哈希值去抢环，m2......任意一段abc节点数差不多，此外还可以管理负载，可以让负载能力强的多承担节点。
base case：如果越界或者被标记过或者不是岛（！=1），直接return
基本策略：以上条件不中就是1，进行标记为2，然后上下左右依次尝试
计算岛的个数然后进行感染过程：
感染过程：
下面进行并行计算：利用并查集解决这种集合问题将整张表一分为二，分别看左右两个表各自有几个岛，依次归集为abcd，最终在交界处将两个不属于同一个集合的数据union，最后看有几个集合。
KMP算法：
当一段字符串有公共串时，必然二者有前后位置，所谓KMP算法就是当一个字符串比对到一个位置不匹配时，看这个字符前面的字符串拥有的最长公共子序列，将公共前缀的位置移动到公共后缀的位置，然后继续进行比较。
所谓的next数组即公共前缀的下标的再下一个位置。
经典解法：所加特殊字符没有特殊要求，它只是一种标记而已
求每个位置最长回文子串的长度放于数组
R：之前所扩所有位置所到达的最右回文右边界
C：取得更远边界时中心点位置，二者是伴生状态
1）当前没在最右回文右边界R内，暴力扩展并进行R和c的更新
2）当前来到最右回文右边界内部，此时i必然在C的右侧，i关于C做一个对称点S，由S向两侧尽力扩展
1.如果S的最左回文右边界没有超出C的左边界，则继续i+1.
2.S的最左回文右边界超过了C的左边界，那么根据对称关系，我们只能保证i在边界内部的部分是回文，再向右位置不是回文，可以证明
X==Y,Y==Z如果Z==P的话那么以C为中心的回文必然会扩大，与原题设矛盾，故Z！=P。
3.S向两边扩压线L，则i的回文可能更向右，需要i继续尝试
注：S为之前已经求过回文子串长度的位置，这是一种由于回文子串对称性带来的加速。C对于这种加速做了前提保证一一我本身就是回文子串，可以利用我的对称性。
总结：说白了这种求最长回文子串长度数组的算法，利用了回文子串具有对称性来进行加速的一一尽量在回文字串范围内部求解。
for循环内第一句求的是以当前节点为中心至少拥有的回文子串长度，之后视情况还会再while循环内部更新
滑动窗口：双端队列实现，内部存放下标既可以得到位置又可以得到数据。
R向右动：要保证内部数据从大到小，一旦遇到数据大于等于就一个一个弹出，直至符合严格递减才可以放入
L向右动：L向右动看一下哪个位置信息过期，如果他是双端队列头部位置就弹出，不是就不用管
双端队列存放的是可能性，局部最大值的可能性排列
猜测：可以先让全部数据进队列，即R++，然后一个一个出队列，即L++，每一次L++都会过期一个数据，没过期一个数据就看一下他的下标是否和队头下标相同，如果相同就弹出队头下标，否则当前局部最大值就是淘汰元素自己本身。
这是因为如果过期元素下标如果和队头下标差距很多，说明队头元素淘汰过很多元素，而又因为这个队是严格递减的淘汰的元素也必然是严格递减的，所以说明一件事情一一从当前淘汰元素到队头元素下标的前一个位置所有的值一定是严格递减的。
例如本题中按所猜想试验一下：
队中元素：如果先一股脑只进队emmmmm只有7，说明何时进队何时出队存在调度问题
改正：先让自由窗口变为大小为3的然后每次再加一个数让一个数过期，即先R++再L++......
寻找每一个数左边和右边离他最近且比他大的数据的下标。
单调栈：设计一个栈按自底向上单调递减的依次压入栈中，如果遇到数据S破环规律就弹出栈顶元素，新栈顶和这个破环规则的数S构成了左右边界，记录下来。再看S是否破环这个新栈规律，重复.......
以上若有重复元素就挂在元素链的后面
party of happy value
Morris遍历：前提是可以改变底层节点空闲指针，又称线索二叉树。
流程：
1.当前节点cur：如果它有左树，就寻找它左树上最右节点，
1）如果最右节点的右指针为null就让它指向cur，然后cur来到它的左孩子
2）否则如果不是null（那就是指向了当前节点本身），说明当前cur节点是第二次遍历，那就重新回到cur，并且把最右节点右指针置null，然后来到cur的右孩子
2.如果cur没有左树，就来到它的右孩子，重复以上1.操作优先执行左孩子
3.如果左右都为null就结束
如果一个节点没有左树说明它不会被二次遍历。
如果一个节点有左树，一定能回到它自己两次。
代码
先序：如果一个节点只能到达它一次直接打印，如果可以到达两次，就第一次打印。
如果没有左树，说明当前节点只能到达一次，先打印再向右；如果有左树就在大if里面的小if里先打印再向左，因为这里代表了第一次遍历
中序：只能到达一次的节点，直接打印，可以到达两次的节点第二次打印。
如果没有左树直接打印，因为只能遍历一次，如果有左树就在大if里面的else里面打印，因为这是第二次遍历。
而在这里的代码中中了else以后先修改了最右节点，然后逐步跳出大if，然后进行了打印，从功能上来说符合了逻辑。正常来说可以在这个else中打印后直接continue，这样写代码相当于简化了
后序：把打印时机放在能打印两次的节点上，在第二次到达某一结点时逆序打印自己左树的右边界。
尽量不要用栈，会增加空间复杂度，我们可以将左树右边界进行逆序然后打印，最后再逆序回来。
判断一个树是否是搜索二叉树：中序遍历时一直是升序即可
思想方法和布隆过滤器一样，先看这些数大部分分布在什么范围，然后再看哪些部分很少涉猎，一步步细分。
将这些数放在512个桶中，看哪个桶的数最少再仔细研究，其中每个桶包含一定范围的数，将这个定位的范围再分成512份......
进一步假设只能申请有限几个变量，进行词频统计，一步步二分。
可以用哈希函数分流
看1G内存最多有多少条记录一一key：桶序号 value：词频数，看看能分成多少个小文件，一个小文件有多少记录，然后细分
位图的方法：用位图的两位表示出现次数，00（0次），01（1次），10（2次），11（多次）。
寻找中位数依然是范围统计的思想，先进行词频统计，然后看位于中间的数在哪一个桶中，对这个捅进行仔细筛查查找正好处于20亿位的数。
先看这5G内存大致可以存放多少词条，由此来确定建立一个小根堆（按照key值进行排序）有多大（2的27次方），有符号数为2的32次方，一份2的27次方有2的5次方份（即统计2的5次方份）。
先统计最小范围的数据，不在此范围的数据进行忽略，统计完此范围之后，从小根堆依次弹入到新文件，然后进行下一个范围的数据统计......
说白了一个范围一个范围的进行统计，但是尽量堆大一点，这样每次就可以多统计一些。
第二种方法：做一个只能放下三个记录的大根堆，不够三条记录就加进去，加入过就词频++，每有一个数比堆顶大就跳过，小就弹出堆顶将其入堆，统计完一遍之后弹入小根堆，并且记住这里面最大的那个数以便下一次进行划分范围。
注：大根堆可以进行前n个最小数据的统计
位运算
n右移31位得到符号位，然后&1
sign可以得到符号，scA、scB必然一个是0，一个是1，缺点是可能会产生溢出。
改进
2的幂：二进制只有一个1，所以x减去x与上自己的取反加一等于0或者自身减去1之后令所有的1打散一一x&（x-1）==0
4的幂：只有一个1并且1后面有偶数个
x&（010101.。。。。）！=0是
加减运算
或（无进位相加 ）
利用&然后再向左移动一位为进位
然后二者再或.....
及重复两次：先求无进位相加再求进位，再来一次不断重复计算无进位相加和求进位运算，直至没有进位为止。
减法即加b的相反数.....
乘法
乘数如果是0直接复制被乘数是1就复制，并且每次伴随着左移运算。
被乘数每次向左移动一位实现每次错开一位的操作，b每次向右移一位直至成为0，运算结束
除法
假设被除数a：0110111 除数b：00011
尝试a-（b左移17位）不能就跳过，依次尝试16、15、14......直到能减得出结果a‘，再让
a’尝试减去b向左移动3位、2位......得到a‘’，由于不能再减了就忽略
一步步让a尝试减去b左移位数得到的新值进行更新，直至最后可以视为0
让x右移相当于让y左移然后进行比较，但是y左移面临溢出的危险，不如让x右移
以下版本是考虑正负号的
略，此处为动态规划，前文已讲！！！！！
略，此处为动态规划的补充部分，已经归到了动态规划最后一节。
有序表：O（logn），可以由红黑树、AVL树、SB树以及跳表（skiplist）实现，他们之间只有常数时间的区别。但是利用树实现的结构一一BST，必然会用到平衡树、树旋转的概念。
搜索树，对于每一个当前头节点，左树都比自己小，右树都比自己大。
增加：按规律加入即可。
查找：一个数据和6最为接近，6如果发现一个节点比6小就去它的右树找，如果比自己大就去左树找。
删除：
1）有左右孩子 找到自己左树的最右节点或者自己右树的最左节点，将它的所有孩子交给自己的父亲，然后去替代删除节点的位置。最后返回删除的数据。（即左树上面最大的或者右树上面最小的）
2）没有左右孩子，直接删除返回
3）删除节点只有左孩子或者右孩子，直接让孩子替代然后返回即可。
但是这样建立的树没有平衡性，建立平衡搜索二叉树还需要进一步操作BST。而这里的平衡性要求不是太严格，只需保证任何一个结点的左右两树相差不大一一高度相差不太大或者个数差不多
下面我们利用左旋和右旋这两个基本操作进行平衡性的实现。
AVL、SB、红黑树之间的共同特点是都利用了左右旋这两个基本操作进行平衡性的实现，区别是它们判定何时需要进行平衡操作的条件以及怎么用这两个操作不一样。
AVL树：维持高度信息
下面作为主要实例进行讲解
SB树：节点数量信息
LL//RR型：左孩子的左孩子个数大于右孩子个数，先对T做一个右旋L上去，m（T）表示以哪个节点为头进行调整，原则是右旋之后发现哪个节点的孩子发生变化了，调函数对这个节点进行操作，这里是T变了，所以再来一个m（T），L节点也变化了，来一个m（T）
m（T）{
1）右旋；
2）m（T）
3）m（L）
}//左旋就第一步变化
LR//RL型：左孩子的右孩子大小大于右树，想办法让B变成头部。先对L左旋，然后对T右旋，然后谁的孩子变化了重复m谁
红黑树：1）每一个节点非黑即红 2）头节点和叶结点（最底层的空节点）必须为黑 3）任何两个红结点不能相邻 4）从任何一个当前cur结点出发，每一条到达结束路径的黑节点数量一样一一保证了最长和最短路径长度不超过二倍关系。
检查违规情况中，新增标准的操作5个，删除标准8个。
********************************************************************************************************************
如果左旋只操作头节点和他的右孩子；如果右旋只操作头节点和他的左孩子。
********************************************************************************************************************
AVL树
一个重要的问题是这些树是如何意识到自己是否是不平衡的呐？
对于AVL树，它每加入一个节点，都会往上检查它的平衡性，假如加入一个节点x ，当x来到了自己合适的位置时，它会先检查x处是否有平衡性，然后沿着父节点一步步检查平衡性，没有就利用左右旋转进行平衡。
删除一个节点时，比如说删除节点5，先进行完
删除操作，利用6进行替代，并将6的孩子托付给自己的父亲...，然后从自己的父亲7开始向上进行检查平衡性一一相当于7的结构被修改过了所以要进行检查，而6原来的孩子本身就有平衡性不需要进行检查。
那检查出什么样子就算不平衡呐，分为4种情况：
（节点用⚪代替，子树用🔺代替）
左树的左边过长一一右旋操作，右树的右边过长一一左旋，
左树的右边过长一一让最底层考虑的节点x转成头部即可（先对y左旋让x上去，然后让z右旋再让x上去）。
右树的左边过长一一让最底层考虑的节点c转成头部即可（先对b进行右旋让c上去，再对z进行左旋让c上去）
这些调整都是常数型的，下面看具体实现：旋转操作自带高度更新，如果没有进行旋转，也会进行一次更新一一updateHeight。做完当前节点之后，向上继续进行修改。
跳表
可以认为是一个多链表skiplist
{
1.假设有一个默认节点，默认它的key是全局最小的，开始只有一条向外指的指针。
增加节点操作：
while{
2.现在用户开始加数据，封装数据之后，开始摇骰子，用以决定这个新节点有几条指针，如果指针数量比当前默认节点数量多的话，默认节点也要增加指针。还要将新节点的所有指针置为null。
3.下一步进行添加操作这里我们假设跳表已经有了一定的数据量，详述具体添加操作。
从默认节点最高层开始，如果最高层指向null一一说明这个新节点更新了层数，就让最高层指向新节点，然后继续下一层，以下遵守下列原则：
/*当前新节点记作cur。*/
****************************************************************************************************************************************************************************** 以 默认节点为对象从最高层指针开始，假设进行检验的节点记为S,初始化S=默认节点。
1）S指向的下一个数据比cur大
①比cur层数高就反弹回来，S节点直接进行下一层的检验。
②和cur层数一样，S节点本层就指向cur，而cur最高层指针就承接S节点指针的数据，开始进行S节点的下一层尝试。
//③默认节点不可能比cur层数低
2）S节点指向的下一个数据比cur小就跳转到下一个数据，重复1）2）......
******************************************************************************************************************************************************************************
}
}
//从最高层开始是进行检查的一个加速
例子
删除节点操作：
先进行查找后进行删除，大体还是利用了增加操作的很多思想，这里不再进行赘述。
