第一章 栈和队列
1.1 $getmin$ 栈
用两个栈， $A$ 正常使用， $B$ 在 $A$ 的 $push$ 和 $pop$ 时保持栈顶是 $A$ 的最小值
1.2 两个栈组成队列
两个栈方向相反， $A$ 压栈代表入队， $B$ 退栈代表出队，当 $B$ 为空时，把 $A$ 反向导入 $B$
问题是不能保证出队 $O(1)$ ？
1.3 用递归函数和栈逆序一个栈
两个递归函数， $A$ 递归 $pop$ 栈中所有元素，返回最后一个元素，再把剩下的 $push$ 回去。 $B$ 递归调用 $A$ ，把 $A$ 返回的 $push$ 回去
1.4 猫狗队列
一个队列存猫，一个队列存狗，一个数组用01标注存放顺序
1.5 用一个栈实现另一个栈的排序
把A栈的依次 $pop$ ，如果比B栈顶大就 $push$ 到 $B$ ，否则把 $B$ $pop$ 并 $push$ 回 $A$ 直到比 $B$ 栈顶大，核心就是利用两个栈来回倒，用一个临时变量做插入排序
1.6 用栈求解汉诺塔
递归思路：把 $1\sim N$ 从左移动到右，相当于把 $1\sim(N-1)$ 从左移动到中，再把 $N$ 从左移动到右，再把 $1\sim(N-1)$ 从中移动到右
1.7 生成窗口最大值数组
维护一个最大长度为 $k$ 的队列，保证队头是当前位置往前 $k$ 个数的从大到小的下标，遇到较大值就弃掉前边比他小的
1.8 maxtree
对每一个元素，从左边和右边各选择第一个比这个元素大的值，选择值较小的元素作为父节点。证明过程就是先证明结果只有一棵树，再证明数组里每个元素在左右两侧最多分别有一个孩子
1.9 最大子矩阵
以每一行为底，算出每行的纵向向上连续高度，根据高度差找最大矩阵
1.10 最大值减最小值小于等于 $num$ 的子数组数量
仿照 1.7 维护两个队列，分别存储最大值和最小值的下标，若 $a[i,j]$ 满足/不满足条件，她的所有子数组也满足/不满足条件，因此只需要两个 $flag$ 遍历数组， $j$ 向后遍历，遇到不满足的就让 $i+1$ ，再接着遍历 $j$
第二章 链表问题
2.1 打印两个有序链表的公共部分
因为是有序的，所以就交错遍历，遇到相等就打印
2.2 在单链表和双向链表中删除倒数第k个节点
遍历两次
2.3 删除链表的中间节点
立个 $flag$ 表示中点，一边遍历一边移动 $flag$
2.4 反转单向和双向链表
维护三个指针，每次反转一条边
2.5 反转部分单向链表
把中间那段提出来仿照 2.4 反转，再反过来拼接上
2.6 环形链表的约瑟夫问题
简单版：模拟过程转圈找
进阶版：总结出递归表达式提前算出答案
2.7 判断链表是否回文
简单版：遍历两次，空间 $O(N)$
进阶版：反转后半部分指向中间节点，从两头同时遍历，空间 $O(1)$
2.8 单链表划分成左边小中间相等右边大
遍历一遍，把链表拆成三段，再把三段拼起来，因为是对原链表的指针操作，所以空间 $O(1)$
2.9 复制含有随机指针节点的链表
简单版：遍历两次，使用哈希表确定节点
进阶版：遍历两次，第一次在每个节点后边生成复制节点，第二次复制连接，最后分离原始链表和复制链表，不必使用额外数据结构
2.10 两个单链表模拟整数相加
用栈或反转链表，目的是实现低位到高位的计算
2.11 一个链表是否有环
快慢指针追逐法，第一次相遇后快指针变慢指针从头跑，两个慢指针会在入环点相遇
2.12 两个无环链表是否相交
因为是单链表，所以一旦相交，后续将合并成一个链表，因此只需要对比两个链表的尾结点
2.13 两个有环链表是否相交
找到两个入环点，追逐法判断是否是同一个环
2.14 将单链表每k个节点之间逆序
计数反转后拼接
2.15 删除无序单链表中值重复的节点
方法一：哈希表，遍历一遍，时间空间都是 $O(N)$
方法二：从每个节点遍历一遍，时间 $O(N^2)$ ，空间 $O(1)$
2.16 单链表删除指定值的节点
直接遍历，时间 $O(N)$ ，空间 $O(1)$
2.17 二叉树转双向链表
用队列保存中序遍历，再依次出队重连
2.18 单链表选择排序
时间 $O(N^2)$ ，空间 $O(1)$
2.19 怪异的节点删除方式
要删除节点 $A$ ，可以先把 $A.next$ 的数据复制到 $A$ ，把 $A$ 指向 $A.next.next$ ，本质上只是复制数据，没有删除节点
2.20 向有序环形单链表插入新节点
遍历，插入
2.21 合并两个有序单链表
一个插到另一个里，时间 $O(M+N)$ ，空间 $O(1)$
2.22 按照左右半区重新组合单链表
提前知道链表长度，找到左右半区的头节点，交叉拼接
第三章 二叉树问题
3.1 非递归二叉树先序遍历
一个栈，压入头节点，[ 弹，右，左，弹 ] 循环
3.2 非递归二叉树中序遍历
一个栈，循环压左到 $null$ ，弹出栈顶节点并转到他的右节点，这两步循环
3.3 非递归二叉树后序遍历
两个栈， $A$ 栈中，弹，左，右循环，弹出到 $B$ 栈，最后 $B$ 全部弹出
3.4 打印二叉树边界节点
得到二叉树每层的左右边界：遍历得到树的高度 $h$ ，建立二维数组 $edge[h][2]$ ，递归先序遍历，数组第一位保存每层最先遍历到的节点，也就是左边界，每遍历到新的节点就更新数组的第二位，最终保存的就是右边界
3.5 直观打印二叉树
右中左遍历并打印，因为纵向看，每一个节点都可以占单独的一列，无脑输出换行就行
3.6 二叉树的序列化和反序列化
先序遍历+分隔符，把 $null$ 也记录下，方便计算子树在字符串中的范围。核心思想是用 $null$ 占位变成满二叉树，节点位置就可以计算了
3.7 遍历二叉树的神级方法
$Morris$ 遍历法，不使用递归和栈结构保存历史，让每个节点的左子树的最右节点指向该节点，核心思想是修改 $null$ 指针实现遍历时的回溯
3.8 在二叉树中找到累加和为指定值的最长路径长度
先序遍历二叉树，对每条路径应用 8.11 的方法，但是从左子树转到右子树时要把左子树在哈希表的记录删除，可以通过在哈希表记录节点的所在层次判断
3.9 找到二叉树中的最大搜索二叉子树
递归后序遍历，遍历完左右子树后，如果都是搜索二叉树，那么最大搜索二叉树要么是包括父节点的整棵树，要么是左右子树里节点多的那个，通过比较节点值可以确定
3.10 找到二叉树中符合搜索二叉树条件的最大拓扑结构
自顶向下法：以每个节点为头节点往下找，满足条件就计数，时间 $O(N^2)$
自底向上法：后序遍历，记录左右子树对父节点能贡献多少个满足条件的节点，空间 $O(N)$ ，根据树的形状，时间最优 $O(N)$ 最差 $O(NlogN)$ ，证明懒得看
3.11 二叉树按层打印和 $zigzag$ 打印
按层打印：使用队列，根据当前层的末尾标记出队，出队的时候把其子节点入队，入队同时更新标记下层的最后一个节点，也就是用两个末尾标记实现在队列里区分层次
$zigzag$ 打印：双端队列，头进尾出和尾进头出交替进行
3.12 调整搜索二叉树中两个错误节点
中序遍历，如果降序一次，错的就是降序的两个节点，如果降序两次，错的是第一次的大节点和第二次的小节点。交换两个节点时要考虑各种连接情况
3.13 判断 $t1$ 树是否包含 $t2$ 树全部的拓扑结构
把所有头节点与 $t2$ 相同的子树都匹配一遍，时间 $O(M\times N)$
3.14 判断 $t1$ 树中是否有与 $t2$ 树拓扑结构完全相同的子树
方法一同上，方法二遍历成字符串，看 $t2$ 是不是 $t1$ 子串，时间 $O(M+N)$
3.15 判断二叉树是否是平衡二叉树
后序遍历，记录遍历深度，递归检验左右子树是否是平衡二叉树
3.16 根据后序数组重建搜索二叉树
后序遍历头节点都在末尾，比值确定前面左右子树分界
3.17 判断一颗二叉树是否是搜索二叉树和完全二叉树
搜索二叉树：中序遍历一遍
完全二叉树：按层遍历，节点不够时判断是否时靠左排的叶节点
3.18 通过有序数组生成平衡搜索二叉树
数组中间的节点就是头节点，再递归处理左右子树
3.19 在二叉树中找到一个节点中序遍历的后继节点
先找右子树，再回溯父节点
3.20 在二叉树中找到两个节点的最近公共祖先
后序遍历，遍历左右子树后返回是否有目标节点，当左右子树都各找到一个目标节点是，当前节点就是最近祖先
3.21 $Tarjan$ 算法与并查集解决二叉树节点最近公共祖先的批量查询问题
单独写
3.22 二叉树节点间的最大距离
最大距离有三种可能：左子树最大距离，右子树最大距离，左子树深度+1+右子树深度。后序遍历一次，同时记录子树最大距离和深度，比值得出结果
3.23 先中后序数组两两结合重构二叉树
先后序数组根节点在两端，代入中序数组可以区分左右子树。
只有先后序时，由于左右可以混淆，如果有任一节点只有一个子节点，都无法重构原二叉树，先序中根节点之后就是左子树根节点，后序数组中左子树根节点之前的就是左子树，因此利用先后序数组可以区分左右子树。
3.24 通过先序和中序数组生成后序数组
用先序数组确定后序数组最右的值，再利用中序数组分离出左右子树的先中序数组，重复这两步，把后序数组从右到左填满
3.25 统计和生成所有不同的二叉树
中序遍历为 $1\sim N$ 的一定是搜索二叉树，找规律，如果 $i$ 是头节点，则左子树有 $i-1$ 个节点，右子树有 $N-i$ 个节点，所以 $num(N)=\sum_{i=1}^Nnum(i-1)*num(N-i)$
3.26 统计完全二叉树的节点数
一直向左遍历可以得到树的深度，因为完全二叉树叶节点靠左排列，所以遍历一个节点的右子树的最左节点，得到右子树的深度，如果等于整个树的深度，说明左子树节点是满的，循环这个步骤遍历右子树，如果深度小于树的深度，说明在这个深度下右子树节点是满的，循环这个步骤遍历左子树
第四章 递归和动态规划
优化思路：压缩空间，枚举简化
4.1 求斐波那契第N项
递归向下算，时间 $O(2^N)$
从左向右依次算每一项，时间 $O(N)$
用通项公式直接算，时间 $O(logN)$
4.2 斐波那契求奶牛数量
$C(n)=C(n-1)+C(n-3)$ ，上一年的都活下来，三年前出生的都生一头小的，状态矩阵是三阶的
4.3 矩阵的最小路径和
动态规划，从左上角算到右下角，时间空间都是 $O(M\times N)$ ，只维护一行(列)空间时，向右或向下滚动更新，可以把空间压缩到 $O(min(M,N))$ ，之所以不用维护两行(列)是因为从前到后更新就相当于维护了两行(列)
P.S.：一般动态规划问题都可以用压缩空间的优化方法
4.4 换钱的最少货币数
货币无限+面值不重复：维护二维数组，货币种类数*目标钱数，数组元素表示使用前 $i$ 种货币组成 $j$ 钱数需要的最少张数，遍历到 $dp[i][j]$ 时，枚举所有可能的 $k\geq0$ ，选择使用 $k$ 张当前货币时，最少张数的子问题。
货币仅一张+面值可重复：和上面一样，只用做一次选择就够了，不用遍历所有 $k$ 。
4.5 换钱的方法数
暴力搜索： $i$ 张第一+ $j$ 张第二+ $k$ 张第三……，时间最差 $O(aim^N)$
带记忆的暴力搜索：避免重复计算，时间 $O(N\times aim^2)$
经典动态规划：和上题一样，把值换成方法数，时间 $O(N\times aim^2)$
时间复杂度一样是因为记忆搜索和经典动态规划的本质都是避免重复计算
优化的动态规划(上题也可以用)：枚举所有可能的 $k\geq0$ 可以分成两部分，不用和必用当前货币，不用就是 $dp[i-1][j]$ ，必用本质上是 $dp[i][j-当前货币值]$ ，所以枚举的过程可以省去。时间 $O(N\times aim)$
4.6 最长递增子序列
经典： $dp[i]$ 表示以 $arr[i]$ 结尾的最长递增子序列长度，枚举前面所有结尾比 $arr[i]$ 小的 $dp[k]$ ，最后根据 $arr$ 和 $dp$ 数组得出序列， $O(N^2)$
优化：建立辅助数组，记录长度为k的递增子序列最小结尾数，把枚举转化为在此数组上二分查找， $O(NlogN)$
4.7 汉诺塔
递归， $n-1$ 左右中， $1$ 左中右， $n-1$ 中左右，每次在两个柱子间移动要考虑第三个柱子是为了递归的时候变换柱子的位置
4.8 判断给的状态是不是汉诺塔最优过程中的某个状态
通过 $n$ 的位置可以知道进行到三个步骤中的哪个，然后递归检查 $n-1$ ，最后一定能确定具体步骤
4.9 最长公共子序列
$dp[i][j]$ 表示 $str1[:i]$ 与 $str2[:j]$ 的最长公共子序列长度，取值为 $max{dp[i-1][j],dp[i][j-1],dp[i-1][j-1]+1(当前两个字符相同时)}$ ，获取序列要从右下角回溯，选择了三个值的哪一个就移动到他的位置，如果选择了 $dp[i-1][j-1]+1$ 就把当前字符放进结果
4.10 最长公共子串
经典： $dp[i][j]$ 表示以 $str1[i]$ 与 $str2[j]$ 结尾的最长公共子串长度，要么是 $0$ ，要么是 $dp[i-1][j-1]+1$ ，根据最大的 $dp$ 值直接得到子串，空间 $O(M\times N)$
压缩：由于 $dp[i][j]$ 只和左上角的值有关，可以从左上到右下按斜线更新，一次更新一个，空间 $O(1)$
4.11 最小编辑代价
$dp[i][j]$ 表示 $str1[0,i-1]$ 编辑成 $str2[0,j-1]$ 的最小代价，第一行和第一列是全添和全删，中间的 $dp[i][j]$ 有四种取值： $dp[i-1][j]+删$ ，表示删去 $str1[i-1]$ 后把 $str1[0,i-2]$ 编辑成 $str2[0,j-1]$ ， $dp[i][j-1]+添$ ，表示把 $str1[0,i-1]$ 编辑成 $str2[0,j-2]$ 后添加 $str2[j-1]$ ， $dp[i-1][j-1]+改$ ，表示把 $str1[0,i-2]$ 编辑成 $str2[0,j-2]$ 后修改最后一个字符， $dp[i-1][j-1]$ ，表示当前两个字符正好相等
压缩：因为可取值太多，要维护两行(列)
4.12 字符串的交错组成
$dp[i][j]$ 表示 $aim[0,i+j-1]$ 能否被 $str1[0,i-1]$ 和 $str2[0,j-1]$ 交错组成，第一行和第一列就是和两个字符串单独比较，中间的 $dp[i][j]=true$ 有两种情况： $str1[i-1]=aim[i+j-1]$ 且 $dp[i-1][j]=true$ ， $str2[j-1]=aim[i+j-1]$ 且 $dp[i][j-1]=true$ ，其余情况都是 $false$
4.13 龙与地下城
和 4.3 一样，求的是最大值
4.14 数字字符串转换为字母组合的种数
$dp[i]$ 表示前 $k$ 位不可变时的组合数，从后往前算， $dp[N]=1$ ，当 $str[i+1]=0$ 时 $dp[i]=0$ ，当 $str[i,i+1]$ 可转换时， $dp[i]=dp[i+1]+dp[i+2]$ ，否则 $dp[i]=dp[i+1]$
4.15 表达式得到期望结果的组合种数
表达式 $express$ 一定是数字符号交错组成的，每一个奇数位上的符号把式子分成两部分，维护两个 $dp$ 二维数组分别表示 $express[i,j]$ 为 $true$ 和 $false$ 的组合种数， $dp[0,N]=\sum op_k(dp[0,k],dp[k,N-1])$ ，相当于在每个符号做一次分割，这种大分割产生的两组括号是唯一的，所以不同分割下不会出现重复的情况
4.16 排成一条线的纸牌博弈问题
维护两个二维 $dp$ ， $dp_1[i][j]$ 表示面对 $s[i,j]$ 先拿的人最终能得到多少分， $dp_2[i][j]$ 表示后拿的人最终能得到多少分，只剩一张牌时 $dp_1[k][k]=arr[k]$ ， $dp_2[k][k]=0$ ，从右下往左上算， $dp_1[i][j]$ 可取值有 $arr[i]+dp_2[i+1][j]$ 和 $arr[j]+dp_2[i][j-1]$ ， $dp_2[i][j]$ 可取值有 $dp_1[i+1][j]$ 和 $dp_1[i][j-1]$ ，时间 $O(N^2)$
4.17 跳跃问题
从左到右遍历一遍，维护三个临时变量， $jump$ 表示步数， $cur$ 表示以当前为起点能去的最远处， $next$ 表示以遍历过程中的点为起点能去的最远处，当遍历到 $cur$ 时，把 $cur$ 更新成 $next$ ，同时 $jump+1$
4.18 数组中的最长连续序列
每次遍历一个数，先使用哈希表去重，然后保存在一个列表里，当列表里出现连续对时，合并成表示范围的二元组 $(left,right)$ ，由于能查询哈希表，检测连续时不需要遍历列表，所以最终时间空间都是 $O(N)$
4.19 $N$ 皇后问题
暴力搜索：为减小空间复杂度，递归函数维护一维数组， $record[i]$ 表示第 $i$ 行放置的列数，遍历 $N$ 个列时实时检查该列能不能放
优化：利用位运算加速，用两个 $N$ 位二进制数表示当前哪些位置受列和斜线的影响不能放置，其实只加速了检查的操作
第五章 字符串问题
子串是连续的，子序列是可以分散的
5.1 判断两个字符串是否互为变形词
建一个字符集大小的数组计数
5.2 字符串中数字子串的求和
从左到右遍历，用几个变量标记
5.3 去掉字符串中连续出现k个0的子串
从左到右遍历，用一个变量标记0的个数
5.4 判断两个字符串是否互为旋转词
把两个 $str2$ 拼在一起，检查 $str1$ 是否是子串，方法同 $KMP$ 算法
5.5 将整数字符串转成整数值
从左到右遍历
5.6 替换字符串中连续出现的指定字符串
从左到右遍历
5.7 字符串的统计字符串
从左到右遍历
5.8 判断字符数组中是否所有的字符都只出现过一次
使用哈希保存遍历结果，时间空间都是 $O(N)$
原地排序，遍历检查，时间 $O(NlogN)$ ，空间 $O(1)$
5.9 在有序但含有空的数组中查找字符串
二分查找
5.10 字符串的调整与替换
从左到右遍历一遍，算出替换后的长度，再从右到左遍历，从尾部更新
5.11 翻转字符串
翻转单词：先整体逆序，再逐单词逆序
翻转片段：先逐片段逆序，再整体逆序
5.12 数组中两个字符串的最小距离
遍历一遍，找到 $str2$ 和他前后最近的两个 $str1$ 。进阶问题查询时间 $O(1)$ 就是先花时间做个查询表，mdzz
5.13 添加最少字符使字符串整体都是回文字符串
动态规划， $dp[i][j]$ 表示使 $str[i,j]$ 回文需要添加的最少字符数， $dp[i][j]$ 有三种取值：长度为 $1$ 时 $dp$ 是 $0$ ，长度为 $2$ 时 $dp$ 是 $0$ 或 $1$ ，长度大于 $2$ 时，首尾相等 $dp[i][j]=dp[i+1][j-1]$ ，首尾不等时 $dp[i][j]=min{dp[i+1][j],dp[i][j-1]}+1$ ，从对角线向两侧更新 $dp$ ，最后新建长为 $N+dp[0][N-1]$ 的空字符串，从 $dp[0][N-1]$ 回溯填充得到回文串，时间 $O(N^2)$
5.14 已知最长回文子序列，添加最少字符使字符串整体都是回文字符串
新建空字符串，长度为原字符串长度两倍减去回文子序列长度，从原字符串两端同时搜索回文子序列，每搜到一对就把两侧经过的其他字符拼接填充在左侧，逆序后再填充到右侧，时间 $O(N)$ ，回文子序列位置有混淆也不影响，因为最终遍历的回文对数是不变的
5.15 括号字符串的有效性和最长有效长度
有效性：从左到右遍历计数，右括号始终不能多于左括号且最终相等
最长有效长度：动态规划， $dp[i]$ 表示以 $str[i]$ 结尾的最长有效长度， $dp[0]=0$ ， $str[i]$ 是左括号时 $dp[i]=0$ ， $str[i]$ 是右括号时，如果 $str[i-1]$ 是左括号直接配对， $dp[i]=dp[i-2]+2$ ，如果 $dp[i-1]$ 不是 $0$ 且 $str[i-dp[i-1]-1]$ 是左括号， $dp[i]=dp[i-1]+2+dp[i-dp[i-1]-2]$ ，其余情况 $dp[i]=0$
5.16 公式字符串求值
数值栈+符号栈，遇到右括号和乘除尝试计算
5.17 $0$ 左边必有 $1$ 的二进制字符串数量
$dp[i]$ 表示满足条件的 $i$ 位字符串数量，一个满足条件的字符串后面可以补 $1$ ，但是只有末尾为 $1$ 时可以补 $0$ ，所以 $dp[i+1]=dp[i]+dp_1[i]$ ，而第 $i$ 位为 $1$ 时表示第 $i-1$ 位随意，所以 $dp_1[i]=dp[i-1]$ ，所以 $dp[i+1]=dp[i]+dp[i-1]$ ，是斐波那契数列，最优时间 $O(logN)$
5.18 拼接所有字符串产生字典顺序最小的大写字符串
如果 $A+B$ 的字典序小于 $B+A$ ， $A$ 就应该在 $B$ 前边，照这个思路选择排序。
$\color{red}{不理解这个为什么算贪心算法？为什么需要证明？}$
5.19 找到字符串的最长无重复字符子串
哈希表记录，标记子串头，从左到右遍历，时间 $O(N)$ ，空间 $O(M)$ ， $M$ 是字符集大小
5.20 找到被指的新类型字符
$str[k-1]$ 小写则结果从 $str[k]$ 开始， $str[k-1]$ 大写时，向左找有几个连续的大写，有偶数个大写则结果从 $str[k]$ 开始，反之结果从 $str[k-1]$ 开始
5.21 最小包含子串的长度
哈希表记录，左右边界设在起点，右边界向右找到子串，左边界向右缩小范围，得到备选子串，循环该过程不断从右边界重新遍历，选所有备选子串里最短的，时间 $O(N)$
5.22 回文最少分割数
动态规划， $dp[i]$ 表示 $str[0,i]$ 的最少分割数，从 $0$ 到 $i$ 找到第一个使 $str[j,i]$ 回文的 $j$ ， $dp[i]=dp[j]+1$ ，判断回文的过程可优化
5.23 字符串匹配问题
正则匹配原理：有限状态机+递归匹配
5.24 字典树的实现
简单粗暴，节点属性有共用数、词尾数、子节点集合
第六章 大数据和空间限制
降低精度或增加时间从而减少空间
6.1 布隆过滤器
创建一个巨大的长为 $m$ 的 $bit$ 数组，对每条数据使用 $k$ 个哈希函数，分别对 $m$ 取余，把 $bit$ 数组的 $k$ 个 $bit$ 置为 $1$ 。使用时如果输入对应的 $k$ 个位置都为 $1$ 就过滤，只会误杀不会漏杀
6.2 找到出现最多的数
读文件不会把整个文件放进内存，但是查哈希表是把整个表放进内存。 把 $N$ 个数的文件用哈希函数分配到 $k$ 个哈希表里，哈希函数能保证相同的数都在同一个表里，每次查找只把一个表放进内存，查完所有表后对比各自频次最多的数，把大的集合分组不仅能减少内存占用，还能减少哈希表里表示键值的比特长度
6.3 找到没出现的数
只考虑出现与否不需要计数，可以使用 $bit$ 数组减少内存占用，再优化还可以分组统计，每次只检查 $k$ 个数出现与否，但每组都要遍历一遍原文件
6.4 找到所有重复的 $url$
同 6.2 ，大文件拆成多个小文件
6.5 统计词汇 $top_k$
同 6.2 ，大文件拆成多个小文件，每个小文件 $top_k$ 再排序
6.6 找到出现两次的数
双倍 $bit$ 数组，每个数用两个 $bit$ 统计出现 $0$ 次、 $1$ 次、 $2$ 次和多次
6.7 找中位数
先分好 $k$ 个区间，遍历一遍文件得到中位数出现的区间，再遍历一遍在目标区间里接着找，空间不够可以继续分区间
6.8 一致性哈希算法
环形分配可以减小增删机器时数据迁移的代价，虚拟节点可以减小机器较少时的负载不均衡
第七章 位运算
7.1 不用额外变量交换两个整数的值
$a=a\oplus b$ , $b=a\oplus b$ , $a=a\oplus b$ ，第一步把 $a$ 和 $b$ 信息不同的比特位标为 $1$ ，第二步当信息不同且 $b$ 是 $0$ 时结果是 $1$ ，信息相同 $b$ 是 $1$ 是返回 $1$ ，所以结果就是原来的 $a$ ，第三步当信息不同且 $b$ (原来的 $a$ )是 $0$ 时结果是 $1$ ，信息相同 $b$ 是 $1$ (原来的 $a$ )是返回 $1$ ，所以结果就是 $a$ (原来的 $b$ )
7.2 不用任何比较判断找出两个数中较大的数
二进制最高位是符号位， $1$ 是负数， $0$ 是非负，查看 $a$ 、 $b$ 和 $a-b$ 的符号， $a$ 和 $b$ 符号相反直接返回非负的， $a$ 和 $b$ 符号相同则 $a-b$ 不会溢出，根据 $a-b$ 符号返回结果
7.3 只用位运算不用算术运算实现整数的加减乘除运算(不考虑溢出)
加法：只相加不进位时 $a+b=a^b$ ，向前进位的序列是 $(a\&b)\ll 1$ ，再以异或序列和进位序列不断循环前两步，直到进位序列全是 $0$
减法： $a-b=a+(-b)$ ， $b$ 的相反数是把 $b$ 取反加一得到补码，再和 $a$ 做上述加法
乘法： $a\times b$ 本质是 $a$ 循环累加，把 $b$ 按位拆分，最低位是 $1$ 时结果加 $a$ ，高位都代表 $2$ 的乘方，通过对 $a$ 向左移位可以实现，最终 $a\times b=a\times b0+\sum{i=1}^n(a\ll i)\times b_i$ ，因为 $b_i$ 是 $0$ 或 $1$ ，所以式子里的乘法只是形式上的， $b$ 是负数也成立
除法： $a\div b$ 本质是 $a$ 循环减去 $b$ ，因此可以对 $b$ 移位比大小得到比 $a$ 小的最大的数。如果 $a$ 、 $b$ 中有负数要先转成非负，最后再考虑符号。一个特例是， $int$ 的最小值的绝对值比最大值大 $1$ ，所以 $int$ 的最小值不能转成正数，当不能直接判断出结果，也就是最小值必须参与计算时，可以把最小值拆成几段分开算，最后用余数再算一次
7.4 整数的二进制表达中有多少个 $1$
方法一：循环 $n=n\And(n-1)$ 或 $n-=n\And(1-n)$ 直到 $n=0$ ，这个操作本质上是去掉 $n$ 最右边的 $1$ ，两个式子右边一个返回去掉末尾 $1$ 的 $n$ ，一个直接返回末尾 $1$
方法二：平行算法，统计 $1$ 的个数不用把整个二进制序列当成一个数，同时在每个bit上操作既提高了效率又排除了序列里高低位的影响，平行算法采用归并的思路，依次算出每 $2^k$ 位里有多少个 $1$ ，最后一步的结果就是整个序列里有多少个 $1$int function(unsigned int n)
{
n = (n & 0x55555555) + ((n>> 1) & 0x55555555); #每2bit为一组相加
n = (n & 0x33333333) + ((n >> 2) & 0x33333333); #每4bit为一组相加
n = (n & 0x0f0f0f0f) + ((n>> 4) & 0x0f0f0f0f); #每2bit为一组相加
n = (n & 0xff00ff) + ((n>> 8) & 0xff00ff); #每16bit为一组相加
n = (n & 0xffff) + ((n>> 16) & 0xffff) ; #每32bit为一组相加
return n;
}
7.5 在其他数都出现偶数次的数组中找到出现奇数次的数
一个数奇数次： $n\oplus0=n,n\oplus n=0$ ，所以只要用一个 $0$ 把所有数都异或一遍，剩下的值就是奇数次那个数
两个数奇数次：用 $0$ 异或一遍结果是 $a\oplus b$ ，两个数不相等结果必有个第 $k$ 位是 $1$ ，再用 $0$ 与第 $k$ 位是 $1$ 的所有数异或一遍，得到的就是 $a$ 或 $b$
7.6 在其他数都出现 $k$ 次的数组中找到只出现一次的数
$k$ 个相同的 $k$ 进制的数无进位相加结果是 $0$ ，因为结果每一位都是 $(k\times a)\%k$ ，所以把所有数转为 $k$ 进制累加，得到的结果就是只出现一次的数
第八章 数组和矩阵问题
8.1 转圈打印矩阵
就是从外到内逐层打印，用每一圈的四个角的坐标判断
8.2 将正方形矩阵顺时针旋转 90°
方阵里一个数顺时针旋转 90° 就是沿着他所在的一圈顺时针走一条边的距离，和上题一样逐圈操作
8.3 之字形打印矩阵
算坐标，碰到边界再判断怎么移动
8.4 找到无序数组中最小的 $k$ 个数
$O(Nlogk)$ 方法：维护一个 $k$ 个节点的大根堆，遍历数组，如果元素小于堆顶就插入堆，其中遍历 $O(N)$ ，堆插入 $O(logk)$
$O(N)$ 方法： $BFPRT$ 算法可以从数组中找到第 $k$ 小的数，把原数组每五个数分一组，分别求中位数，再递归求中位数的中位数，最终得到一个中位数 $x$ ，用 $x$ 划分原数组中大于 $x$ 和小于 $x$ 的数，在其中一边继续用中位数方法划分，最终能得到 $x$ 在数组中的位置是第 $k$ ，可以用数学证明该过程时间复杂度是 $O(N)$ ，大概意思就是用中位数划分数组效率高，所以能收敛到 $O(N)$ ，所以找到 $k$ 个最小的数总的时间复杂度也是 $O(N)$
8.5 需要排序的最短子数组长度
从左到右、从右到左分别遍历，找边界
8.6 在数组中找到出现次数大于 $N/K$ 的数
遍历一遍数组，循环排除 $K$ 个不同的数，直到剩下的不足 $K$ ，剩下的就是出现次数大于 $N/K$ 的数。具体实现是建立两个长度为 $K-1$ 的数组， $A$ 数组存数组里的数， $B$ 数组存出现次数，当遍历到的 $x$ 与 $A$ 里的都不同时， $B$ 数组都减一同时遍历下一个，就相当于排除了 $K$ 个不同的数，次数归零时用遍历到的数补位，最终时间复杂度 $O(N\times K)$ ，空间复杂度 $O(K)$
8.7 在行列都排好序的矩阵中找数
$M\times N$ 的矩阵中，每个以对角线上一点为右下角的一行和一列的组合里，对角线上这个点都是最大的，相当于从左上角到右下角沿着对角线剥洋葱，遍历的最大长度是对角线+一行+一列，时间 $O(M+N)$
8.8 最长的可整合子数组的长度
可整合数组就是元素不重复，最大值-最小值+1是元素个数的数组，从左到右以每个元素为起点遍历一次，时间 $O(N^2)$
8.9 不重复打印排序数组中相加和为给定值的所有二元组和三元组
二元组：一个左指针一个右指针向中间遍历，时间 $O(N)$
三元组：从左到右遍历，每遍历到一个元素，就把他后面的当成一个二元组问题求解，时间 $O(N^2)$
8.10 未排序正数数组中累加和为给定值的最长子数组长度
左右两个指针从数组头遍历，变量 $sum$ 存两个指针标记的子数组累加和，变量 $len$ 存 $sum$ 为给定值 $k$ 时的最长子数组长度，右指针向右遍历， $sum\geq k$ 时左指针加一
8.11 未排序数组中最长子数组系列问题
累加和为 $k$ ： $s[i]$ 表示子数组 $arr[0,i]$ 的累加和，则 $arr[j,i]$ 的累加和就是 $s[i]-s[j-1]$ ，从左到右遍历数组计算累加和，建立哈希表， $key$ 是累加和， $value$ 是最先产生该累加和的数组下标，若 $s[i]=k$ ，就得到了一个满足条件的子数组，若 $s[i]>k$ ，就在表中查找 $s[i]-k$
正数与负数个数相等：正数变 $1$ ，负数变 $-1$ ，相当于求累加和为 $0$
数组里只有 $0$ 和 $1$ ，子数组 $0$ 和 $1$ 个数相等： $0$ 变 $-1$ ，求累加和为 $0$
8.12 未排序数组中累加和小于或等于给定值的最长子数组长度
建立数组 $s$ 记录累加和，建立数组 $h$ 记录 $s[0,i]$ 之间的最大值，遍历一遍原数组 $O(N)$ ，每遍历一个元素，如果 $s[i]\leq k$ 就更新最长子数组长度，反之就在 $0\sim i$ 之间搜索是否存在 $s[i]-s[j-1]\leq k$ ，即 $s[j-1]\geq s[i]-k$ ，由于 $h$ 是递增数组，结合数组 $s$ 可以实现 $O(logN)$ 的二分查找，最终时间 $O(NlogN)$ ， 空间 $O(N)$
8.13 计算数组的小和
在归并排序的过程中计算小和，因为每一步操作的两个数组都是排好序的，所以节省了遍历的时间，对于 $s_1[i]$ ，只要找到第一个 $s_1[i]<s_2[j]$ ，直接给总数组小和加上 $s_1[i]*(len(s_2)-j+1)$ ，时间 $O(NlogN)$ ，空间 $O(N)$
8.14 自然数数组的排序
前提是已经知道了一个数应该放在哪里，从左到右遍历，如果一个位置上的数不对，就把他放到正确的位置，替换掉那个位置上的数，然后循环修正替换下来的数，最后会回到原来遍历中止的位置，继续往后遍历
8.15 奇数下标都是奇数或者偶数下标都是偶数
两个指针从左到右分别遍历数组的奇数和偶数位置，循环检查数组最后一个数，放在相应指针标记的位置，把该位置替换下来的数放在数组尾部，对应指针加二
8.16 子数组的最大累加和问题
从左到右累加，累加和变成负数就从下个数重新累加，用一个变量记录累加和的最大值
8.17 子矩阵的最大累加和问题
把矩阵的 $k$ 行累加成一行，转化成子数组的最大累加和问题，结果就是以这 $k$ 行为基础搜索矩阵的列找到的子矩阵，从上到下以每行为起点遍历所有行数的矩阵，搜索最大累加和的子矩阵，最终时间 $O(N^3)$ ，空间 $O(N)$
8.18 在数组中找到一个局部最小的位置
先判断首尾有没有，没有就二分查找，如果 $arr[mid]>arr[mid-1]$ ，因为左半边肯定不单调，所以一定存在局部最小，如果 $arr[mid]>arr[mid+1]$ 就在右半边找，最终时间 $O(logN)$
8.19 数组中子数组的最大累乘积
从左到右遍历，分别求以每个 $arr[i]$ 结尾的最大累乘积 $max[i]$ 和最小累乘积 $min[i]$ ，通过比较 $max[i-1]\times arr[i]$ 、 $min[i-1]\times arr[i]$ 和 $arr[i]$ 三个数确定最大最小累乘积，再用一个变量保存整个过程中的最大累乘积，时间 $O(N)$ ，空间 $O(1)$
8.20 打印 $N$ 个数组整体最大的 $topK$
维护一个大根堆，因为数组都是有序的，取 $N$ 个数组的最大值建堆，时间 $O(N)$ ，每次把堆顶加入 $topK$ 并把堆顶元素所在数组的下一个最大值插入堆，每次插入 $O(logN)$ ，插入总时间 $O(KlogN)$
8.21 边界都是 $1$ 的最大正方形大小
以每个点为正方形的左上角，对于所有可能的边长，检查正方形的四条边，时间 $O(N^4)$ ，空间 $O(1)$ 。可以通过预处理矩阵把检查四条边的时间变成 $O(1)$ ，预先生成两个矩阵，用来记录每个点向右和向下有多少个连续的 $1$ ，从右下角开始算，每次利用之前计算出的结果，可以把预处理时间降到 $O(N^2)$ ，优化后的总时间是 $O(N^3)$ ，空间 $O(N^2)$
8.22 不包含本位置值的累乘数组
使用除法：用总乘积除以每一位
不使用除法：创建两个数组分别存储从左到右和从右到左的累乘，不包含一个数的累乘相当于他的左累乘和右累乘的乘积；或者用异或代替除法
8.23 数组的 $partition$ 调整
从左到右遍历，交换数值，相当于用一个左指针把数组分成两个区，遍历过程中在区之间做交换。更复杂的问题可以用一个左指针一个右指针把数组分成三个区
8.24 求最短通路值
广度优先遍历，时间 $O(M\times N)$
8.25 数组中未出现的最小正整数
理想情况是数组里存着 $1\sim N$ ，当发现不属于这个范围的数或有重复数时，说明坑位不够了。初始化 $l=0$ 和 $r=N$ 标记空余位置的范围。循环遍历范围头部：
若 $arr[l]=l+1$ ，说明正好占对了最左边的坑， $l++$
若 $arr[l] < l$ 或 $arr[l]>r$ ，说明有范围外的占坑了，把 $arr[r-1]$ 保存到 $arr[l]$ ，同时 $r—$ ，表示删除一个坑位
若 $arr[arr[l]-1]=arr[l]$ ，说明 $arr[l]$ 是合法范围内的数，但是他应该在的位置 $arr[l]-1$ 上已经有相同的数了，说明出现了重复，把 $arr[r-1]$ 保存到 $arr[l]$ ，同时 $r—$ ，表示删除一个坑位
若以上错误都没出现，说明 $arr[l]$ 是合法范围内的数，把他和 $arr[l]-1$ 位置上的数交换
最终左右指针相遇， $l+1$ 就是未出现的最小正整数
8.26 数组排序之后相邻数的最大差值
遍历一次找到最大最小值，做桶排序，时间 $O(N)$
第九章 其他题目
9.1 从 $5$ 随机到 $7$ 随机及其扩展
$rand1to5$ 实现 $rand1to7$ ：独立调用两次 $rand1to5$ ， $res=(rand1to5-1)\times 5+(rand1to5-1)$ 等概率随机生成 $0\sim 24$ 之间的数，当结果在 $0\sim 20$ 之间时， $res\%7+1$ 就等概率随机生成 $0\sim 27$ 之间的数
$rand01p$ 实现 $rand1to6$ ：由于 $rand01p$ 生成 $01$ 和 $10$ 的概率都是 $p(1-p)$ ，所以先通过调用两次 $rand01p$ 实现等概率产生 $0$ 和 $1$ 的 $rand01$ 。 $rand0to3=rand01\times 2+rand01$ 等概率随机生成 $0\sim 3$ ， $res=rand0to3\times 4+rand0to3$ 等概率随机生成 $0\sim 15$ ，当结果在 $0\sim 11$ 之间时， $res\%6+1$ 就等概率随机生成 $0\sim 6$ 之间的数
$rand1toM$ 实现 $rand1toN$ ：如果 $M>N$ ，调用一次直接筛选 $res$ ，如果 $M<N$ ，调用多次拼接成一个多位的 $M$ 进制数，再筛选 $res$
9.2 一行代码求两个数的最大公约数
辗转相除法， $gcd(a,b)=gcd(b,a\%b)$
9.3 有关阶乘的两个问题
阶乘末尾 $0$ 的数量：遍历 $1\sim N$ 的所有数，累计每个数的因子 $5$ 的个数，遍历过程可以优化，一个数有多少 $5^k$ 的因子，就能提供多少个 $5$ ，所以因子 $5$ 总数为： $\sum_{k=1} N/5^k$
阶乘的二进制表示中最右边的 $1$ 的位置：末尾 $0$ 的数量是因子 $2$ 的个数 $\sum_{k=1} N/2^k$
9.4 判断一个点是否在矩形内部
比较坐标位置；或者看横纵直线和矩形的交点，一个点在凸多边形的内部，从这个点引出的横纵两条直线与多边形的四个交点一定分布在这个点的上下左右
9.5 判断一个点是否在三角形内部
同上
9.6 折纸问题
找规律，每次折叠产生的新折痕都是在上次折叠新产生的每一条折痕前后生成下折痕和上折痕
第一次折叠： 下
第二次折叠： 下 上
第三次折叠： 下 上 下 上
第四次折叠：下 上 下 上 下 上 下 上
中序遍历的结果就是折痕顺序
9.7 蓄水池算法
前 $k$ 个球直接放入，对于第 $i(i>k)$ 个球，以 $k/i$ 的概率决定放入，如果放入了就随机扔掉袋子里的一个球，可以数学证明每个球最终留在袋子里的概率都是 $k/N$
9.8 设计有 $setAll$ 功能的哈希表
给每个值附加一个时间戳，创建一个 $key=setAll$ 的条目，每次调用 $setAll$ 方法就更新 $setAll$ 条目的值和时间戳，当查询的值的时间比 $setAll$ 早时，返回 $setAll$ 条目的值，从查询结果看是重置了所有值，其实只是把查询重定向了
9.9 最大的 $leftMax$ 与 $rightMax$ 之差的绝对值
方法一：创建两个数组，从左到右和从右到左各遍历一遍，记录 $leftMax$ 和 $rightMax$ ，最后再遍历一次直接出结果，时间 $O(N)$ ，空间 $O(N)$
方法二：遍历一遍找到数组最大值，再和数组首尾两个元素分别算差值，因为当最大值在一侧时，另一侧最小的最大值就是只有一个元素的情况，时间 $O(N)$ ，空间 $O(1)$
9.10 设计可以变更的缓存结构
双向队列实现节点的排序，头部存旧节点，尾部存最近访问的节点，当一个节点被访问时就移到尾部，要淘汰节点时直接从头部删除，用哈希表映射节点实现 $O(1)$ 的时间复杂度
9.11 设计 $RandomPool$ 结构
数据只有 $key$ 没有 $value$ ，所以可以用哈希表给 $key$ 一个 $index$ ，一个哈希表的索引是 $key$ ，另一个的索引是 $index$ ， $getRandom$ 就是在 $0\sim index$ 之间生成一个随机数
9.12 调整 $[0,x)$ 区间上的数出现的概率
分别调用 $k$ 次 $random$ 函数，返回最大的值，因为只要有一次不在 $[0,x)$ 内，结果就不在 $[0,x)$ 内，说明随机到 $[0,x)$ 内的概率是 $x^k$
9.13 路径数组变为统计数组
从左到右遍历 $path$ ，如果不是首都就跳到他指向的城市，最终要么跳到首都要么跳到一个已经遍历过的节点，然后反向跳回去，同时设置每一步到首都的距离，遍历一遍后 $path[i]$ 就表示城市 $i$ 到首都的距离。再从左到右遍历 $path$ ，还是用跳跃的方法赋值，先 $path[path[0]]=1$ ，对替换下来的 $path[path[0]]$ 再 $path[path[path[0]]]=1$ ，遍历完后 $path[i]$ 就表示到首都距离为 $i$ 的城市数。两次遍历期间可以用数值的正负来区分数值代表的含义
9.14 正数数组的最小不可组成和
动态规划，对数组求一次总和 $sum$ ，把 $dp$ 长度设成 $sum$ ， $dp[i]$ 表示存在子数组累加和是 $i$ ，从左到右遍历数组，对于每一个元素 $k$ ，遍历 $dp[i]=1$ 使 $dp[i+k]=1$ ，最后再扫一遍 $dp$ 找最小不可组成和，时间 $O(N\times sum)$ ，空间 $O(sum)$
已知数组中有 $1$ 时：数组排序，遍历一遍求每个位置 $i$ 的 $range$ ，表示 $[1,range]$ 能够被 $arr[0,i-1]$ 表示，初始 $range=1$ ，如果 $arr[i]>range+1$ ，说明 $range+1$ 无法组成，直接返回结果，如果 $arr[i]\leq range+1$ ，说明 $[1,range+arr[i]]$ 能够被 $arr[0,i]$ 表示，让 $range+=arr[i]$ ，时间 $O(NlogN)$ ，空间 $O(1)$
$\color{red}{没明白已知有1到底影响了什么}$
9.14 一种字符串和数字的对应关系
数字转字符串：把字符串看成是伪 $k$ 进制数，每位的范围是 $1\sim k$ ，先用目标数依次减去 $k$ 、 $k^2$ 、 $k^3$ 等，算出字符串需要的位数，再用剩下的数从高位到低位依次赋值
字符串转数字：第 $i$ 位的值表示有多少个 $k^i$ ，所有位求和
9.15 $1$ 到 $n$ 中 $1$ 出现的次数
找规律，分别算每一位上 $1$ 出现的次数，取右数第 $i$ 位左边的数字(没有就是0)，乘以 $10^{i−1}$ ，得到基础值 $a$ ，取第 $i$ 位数字，计算修正值：
如果大于 $1$ ，则结果为 $a+10^{i−1}$
如果小于 $1$ ，则结果为 $a$
如果等 $1$ ，则取第 $i$ 位右边数字，设为 $b$ ，最后结果为 $a+b+1$
9.16 从 $N$ 个数中等概率打印 $M$ 个数
随机打印 $[0,N-1]$ 的一个位置 $a$ 上的 $arr[a]$ ，把 $arr[a]$ 和 $arr[N-1]$ 交换，再随机打印 $[0,N-2]$ 的一个位置 $b$ 上的 $arr[b]$ ，循环该过程直到打印出 $N$ 个数，可以推出来每个数打印的概率都是 $1/N$
9.17 判断一个数是否是回文数
左右比较，剥洋葱法
9.18 在有序旋转数组中找到最小值
递增数组旋转过的数组中间有断点，如果子数组左小右大说明不包含断点，左大右小说明一定包含断点，左右相等时不确定，如 $[3,1,2,3]$ ，此时需要对子数组进行查找，整个过程尽量使用二分查找，最优情况 $O(logN)$ ，最坏情况 $O(N)$
9.19 在有序旋转数组中找到一个数
二分查找，根据子数组左中右的值，判断断点可能的位置以及需要继续搜索的子数组
9.20 数字的英文表达和中文表达
英文三位一组(个十百)，中文四位一组(个十百千)
9.21 分糖果问题
从左到右遍历，每找到一个上下坡的组合就开始赋值，两个坡最低处都是 $1$ ，两侧上坡都是递增加一，直到两个坡交汇，交汇处的值由坡长的一侧决定
9.22 一种消息接受并打印的结构设计
创建长度为 $N$ 的数组，接受的数字对号入座，当打印到 $k$ 时就把 $k+1$ 当做下一次打印的标志，一旦接收到就向后打印连续区间值
9.23 设计一个没有扩容负担的堆结构
二叉树
9.24 随时找到数据流的中位数
一个大根堆存较小的一半数，一个小根堆存较大的一半数，新的数通过比较堆顶决定加入哪个堆，每次插入后平衡两个堆的大小，保证中位数只和两个堆顶有关
9.25 在两个长度相等的排序数组中找到上中位数
两个数组分别二分查找，结果是分成了四段数组，比较 $arr1[mid]$ 和 $arr2[mid]$ ，如果二者相等说明 $arr[mid]$ 就是合并后数组的上中位数，如果 $arr1[mid]>arr2[mid]$ ，说明合并后的数组中， $arr1[mid:right]$ 在最右边， $arr2[left:mid]$ 在最左边，把这两部分排除，对 $arr1[left:mid]$ 和 $arr2[mid:right]$ 继续做二分查找，最终时间 $O(logN)$
9.26 在两个排序数组中找到第 $K$ 小的数
仿照上题，看第 $K$ 小的数出现在哪部分里，每次对新的子数组二分查找要让 $K$ 减去左边排除掉的部分，最终时间 $O(log(min{M,N}))$ ，因为分别在两个数组上二分查找，复杂度由短的决定
9.27 两个有序数组间相加和的 $TOPK$ 问题
维护一个大根堆，先把 $arr1[M-1]+arr2[N-1]$ 插入堆，重复以下操作，弹出堆顶，假设是 $arr1[i]+arr2[j]$ ，同时把 $arr1[i-1]+arr2[j]$ 和 $arr1[i]+arr2[j-1]$ 插入堆，也就是每次从堆里弹出一个元素，同时保证还在堆里的元素是数组间相加和最大的几个，每次堆的大小加一，最终大小是 $K$ ，堆插入时间是 $O(logK)$ ，所以总时间 $O(KlogK)$
9.28 出现次数的 $TOPK$ 问题
先用哈希表统计词频，再建立小根堆，堆的节点存储字符串和出现次数，遍历哈希表，依次把每条记录插入堆，当堆的大小是 $K$ 时，只有出现次数比堆顶元素多时才插入，最终堆里的元素就是出现次数 $TOPK$ ，时间 $O(NlogK)$
没有数组，字符串动态添加，实时打印：也是维护一个大小为 $K$ 的小根堆，用一个哈希表 $A$ 存储字符串和节点的映射，再用一个哈希表 $B$ 存储节点到堆中位置的映射，每次添加字符串时，先更新 $A$ 中节点的频次属性，如果是新节点直接插入堆，否则然后通过 $B$ 找到节点在堆中的位置，更新节点的频次属性，调整节点的位置，期间保证哈希表和堆的修改同步，最终添加操作 $O(logK)$ ，打印操作直接按位置顺序打印，时间 $O(K)$
9.29 $Manacher$ 算法
单独写
9.30 $KMP$ 算法
单独写
9.31 丢棋子问题
方法一： $P(N,K)$ 表示 $N$ 层楼有 $K$ 个棋子在最差情况下扔的最少次数，显然 $P(0,K)=0$ ， $P(N,1)=N$ ，一般情况时，当在第 $i$ 层扔下，如果碎了，结果就是 $1+P(i-1,K-1)$ ，如果没碎，结果就是 $1+P(N-i,K)$ ，最差情况是二者的最大值，所以用递归的方法， $P(N,K)=min{max{P(i-1,K-1),P(N-i,K)}}(1\leq i\leq N)+1$ ，时间复杂度 $O(N!)$
方法二：动态规划， $dp[i][j]=P(i,j)$ ，遍历数组时间 $O(N\times K)$ ，求 $min-max$ 过程 $O(N)$ ，所以总时间 $O(N^2\times K)$
优化一：压缩空间， $P(N,K)$ 的子问题只遍历 $N$ ，所以对于每个 $dp[i][j]$ 只需要维护左边一列和上边一行空间
优化二：用四边形不等式优化枚举，楼层数相同时，棋子少越少，第一个棋子扔的层数就越高，棋子数相同时，楼层数越多，第一个棋子扔的层数就越高，所以第一个棋子扔的位置可以作为边界来减少枚举
$\color{red}{四边形不等式的原理没太看懂}$
最优解： $map[i][j]$ 表示 $i$ 个棋子扔 $j$ 次最多能判断多高的楼层，第一行第一列直接赋值，扔了第一个棋子后，如果碎了就剩 $i-1$ 个棋子扔 $j-1$ 次，如果没碎就剩 $i$ 个棋子扔 $j-1$ 次，再加上第一次扔的这层，有 $map[i][j]=map[i-1][j-1]+map[i][j-1]+1$ ，之所以不需要 $min-max$ 的过程是因为 $map$ 表示能力的上限，第一次扔完以后要么只向下搜索要么只向上搜索，所以能力值应该是两个方向上的总和，而 $P(N,K)$ 表示运气最差的一种情况，所以必须要通过遍历确定唯一的子问题。在棋子数给定时，只需遍历 $map$ 的一行就能搜索到答案
9.32 画匠问题
方法一： $dp[i][j]$ 表示 $i$ 个画家画 $j$ 幅画的最少时间，有 $dp[i][j]=min{max{dp[i-1][k]+sum[k+1..j]}}(0\leq k\leq j)$ ，时间 $O(N^2\times K)$
优化：四边形不等式减少枚举，时间 $O(N^2)$
最优解：规定每个画匠最大工作时间 $limit$ ，遍历一遍数组可以知道至少需要几个画匠， $limit$ 的范围是 $[0,sum(arr)]$ ，比较 $limit$ 限定下画匠人数与题目给出的人数，用二分法确定 $limit$ 的大小，时间 $O(NlogSum(arr))$
9.33 邮局选址问题
方法一：假设 $arr[i,j]$ 上只能建一个邮局，一定是建在中点上总距离最小， $w[i][j]$ 表示这个总距离，因为 $arr[i,j-1]$ 变成 $arr[i,j]$ 后中点位置不变，所以有 $w[i][j]=w[i][j-1]+arr[j]-arr[(i+j)/2]$ ，多的就是新增的点到中点的距离。 $dp[i][j]$ 表示在 $arr[0,j]$ 上建 $i+1$ 个邮局的最小总距离，首先有 $dp[0][j]=w[0][j]$ ，一般情况下 $dp[i][j]=min{dp[i-1][k]+w[k+1][j]}(0\leq k\leq N)$ ，表示在 $arr[0,k]$ 建 $i-1$ 个，在 $arr[k+1,j]$ 建 $1$ 个，枚举所有情况选择总距离最小的，时间 $O(N^2\times Num)$
优化：四边形不等式，时间 $O(N^2)$
