不再维护!，请参见。
第一章 栈和队列
单调栈
单调栈的功能是，寻找数组中每个元素的左右的两边第一个比他小或大的元素（分为是否有重复元素）
对单调栈的应用有：
求直方图最大矩形面积。扩展问题：求矩阵的最大子矩阵大小
求可见山峰对的数量。根据山峰高度是否有重复，分为无重复使用数学推导就可解决，和有重复利用单调栈模拟解决
第二章 链表问题
约瑟夫问题
利用图像变换，写出编号的递推公式。
第三章 二叉树问题
二叉树遍历
二叉树的遍历顺序分为前序、中序和后序三种，根据遍历的方式分为递归遍历和非递归遍历。需要注意非递归的后序遍历方式的实现。不同遍历的顺序有如下的特点：
搜索二叉树的中序遍历是有序的，应用：找出搜索二叉树中的颠倒节点
中序遍历最后的节点是树根，应用：利用后续序列，重建搜索二叉树
二叉树中累加和为指定值的最长路径长度
原始问题为：累加和为指定长度的最长子数组（第八章 数组和矩阵问题）。
树形DP问题
以每个节点为头节点进行分析，例如：
- 寻找最大二叉搜索树
- 寻找符合搜索二叉树条件的最大拓扑结构
第四章 递归和动态规划
思路汇总
- 暴力递归->添加记忆->动态规划
- 找出状态->探索边界->状态转移
- 空间压缩
最长递增子序列
额外维护的信息是：每个长度序列的最后元素的最小值，对应的数组是有序的，可以利用二分搜索进行加速
信封问题
转化成最长递增子序列问题，按照宽度从小到大排列，相同宽度的高度从大到小排列，高度序列的最长递增子序列就是信封类问题的答案
最长公共子序列 & 最长公共字串问题
区别子序列和子串！
第五章 字符串问题
完美洗牌问题
先考虑每个元素的旧新位置推导，利用多米诺骨牌的思想，逐个位置变换。关于需要从哪些位置开始进行转换，利用一个结论进行推算。
公式字符串求值
复习汇编语言课程中的算术优先级表格。
拼接所有的字符串产生字典序最小的字符串
本题是一道贪心算法的题，每次都需要找一个最好的字符串进行拼接，所以如何找出最佳的字符串就是贪心策略的核心。书中使用了a+b<b+a的策略进行排序，排序靠前就是最优。联想剑指offer中的数字数组的拼接。
最短包含字符串的长度
范围内最优问题，右边届移动去满足条件，左边届移动去掉冗余部分，维护str1对str2的亏欠情况。
子数组的最大异或和
范围内最优问题，首先考虑累加起来，XOR[i,j]=XOR[0,j] ^ XOR[0,i]。最大异或和，即从最高位贪心计算，因此需要维护一个XOR数组的前缀树。如此时间复杂度O(n*m) n为数组大小，m为数字位数，可认为是常数。
相关问题：字符串的前缀树、未排序数组累加和为指定值的最长子数组序列问题、子数组最大公约数和序列长度之积的最大值，最短包含字符串的长度
字符串匹配问题
情况分析类问题，对字符可以重复0次的理解。 Eg: string str="a",exp="a.*"
公式字符串求值
遇到括号的处理方法：递归
子数组的最大异或和
从两端穷举， 暴力计算 到两端穷举，加速计算再到一端穷举，锁定另一端的思考过程。同类：未排序数组中累加和为给定值的最长子数组系列问题
第六章 大数据和空间限制
布隆过滤器
第七章 位运算
不用额外变量交换两个整数的值
在其他数都出现k次的数组中找到只出现一次的数
第八章 数组和矩阵问题
思路汇总
- TopK 类问题，结合排序算法，进行求解，需要注意不同算法的时间空间特性。
- 范围内最优类问题，定义两个边界指针，结合题目要求移动指针找到最优范围，通常会结合一些倒排索引，加速计算，例如未排序数组中累加和为给定值的最长子数组长度以及子数组最大公约数和序列长度之积的最大值；或者结合信息记录，减少时间复杂度，例如字符串问题中的最短包含字符串的长度
找到无序数组中最小的K个数
TOP K 问题，两个主要思想：
- 遍历数组，同时维护最大容量为K的最大堆，复杂度为
O(NlogK) - 找到第K大的元素，使用partition的思想，找到第K大的元素。书中使用了BFPRT的思想，利用中位数进行parition操作，时间复杂度可以达到稳定的
O(N)
需要排序的最短子数组长度
范围内最优问题，此题只会有一个范围，找到最小即可。从右向左遍历，找到右侧范围中的最小值要调整到的最左侧位置；同理，从左向右遍历找到左侧范围中的最大值要调整到的最右侧位置。
在数组中找到出现次数大于n/k的数
原始题目为在数组中找出出现次数大于一半的数，最高效的方式就是对当前数字计数的方式，当计数变成0的时候，更换数字，最后校验候选数字是否满足条件。该题目为扩展题目，需要同时对K-1个数字进行计数统计，道理逻辑与原始问题相同。
未排序数组中累加和为给定值的最长子数组长度
范围内最优问题，结合累加和数组，我们可以快速计算出某个范围的累加和，具体参考子数组的最大异或和中的思路。主要思路是结合左右两个范围指针的移动，求出最优解。因为相比于简单版问题规定的正数数组，所以不能根据简单的条件来判断数组的移动。因此引入了倒排索引，累加和为x值的数组范围是从0到y位置的，来加快判断，这种思路也用到了子数组最大公约数和序列长度之积的最大值中。
计算数组的小和
对归并排序的应用。归并排序的的非递归版本的实现。
子矩阵的最大累加和问题
原问题：子数组的最大累加和问题。此题属于矩阵范围最优问题，通过遍历所有叠加行的方式，将矩阵内求解变成数组内求解的方式，再找出最优的矩阵范围，类似问题参考：第一章--求最大的子矩阵的大小。
在数组中找到一个局部最小的位置
二分搜索，二分搜索不仅仅局限于在有序数组中搜索，只要能确定选左还是选右就可以使用。类似问题参考：第四章--最长递增子序列。
做项目的最大收益问题
第一次尝试的时候，按照动态规划的初级思想，编写了状态和转移函数，添加了记忆，加速计算，但超时了，没有按照动态规划使用数组存储状态的原因是可以拥有的资金范围太大了。查阅答案：emmmm，有点简单，单步决策就可以了，找出所有可以投资的项目，然后根据利益最大的顺序开始投资，直到没有项目或者投资数量耗尽。
第九章 其他题目
折纸问题
从每次折叠时每层纸产生的的新折痕的角度进行思考（down``up交替出现），每两个新折痕之间夹着上一轮中的老折痕，最后构成一棵满二叉树的结构，使用中序遍历得到最终的结果。
能否完美地拼成矩形
两个判断标准：大矩形的面积等于小矩形的面积之和 && 所有小矩形的顶点集合除了构成大矩形的四个顶点之外出现的次数应均为偶数。
LRU缓存结构设计
双向链表，记录头和尾节点的结构设计，包含动作删除尾节点，添加头节点，移动节点到头节点。
LFU缓存结构设计
在双向链表的基础之上增加一个次数维度的双向链表，统计缓存的使用次数。链表问题还需要多多练习。
小帕寄语：每次更新都掰着指头数着哪项参数更新了哪些没更新是否需要更新 比如说插入一个节点 那么前后都需要更新 开头不论是否是次数节点均需要更新 这样就不会少。
其他来源
子数组最大公约数和序列长度之积的最大值
范围内最优问题。普通思路：遍历每个子数组计算最大公约数乘序列长度的值，时间复杂度O(N^3)，序列的长度为N。进阶思路：记录每个序列的GCD值的对应的最早起始位置map<从x位置到现在位置的GCD值,x>，因为GCD值的数量最多是logN，所以时间复杂度将为O(N*logN)
转账总金额最少
问题描述：有一组账户，账户之间互相有转账记录，现在要求更改转账记录中的金额，实现总的转账金额最少（不能增加新的转账记录）。解决思路：BFS广度搜索，记录每个账户所在的层数，从起始账户到达每个账户的路径上的转账最小金额MIN。当广搜遇到白色点，只记录信息。遇到灰色或者黑色点，需要将层数大的路径上的最小转账金额转移到层数小的路径上。从每个顶点运行一遍程序，问题解决。没有验证正确性，和同学交流后暂时没有发现问题
感谢
感谢与我一起刷题的伙伴们，互相“嘲讽”，互相帮助，让我可以保持着刷题的动力，其中尤其需要感谢我的本科同学，ACM大神，小帕，无数次帮我debug我已经陷入绝望了的乱麻般的代码，让我没有那么多烂尾，保持着继续下去的热情。