九章算法面试题42 构造MaxTree
增长序列: 从左到右扫描和从右到左，分别记录每个节点左边第一个比自己大的元素，右边第一个。。（使用栈，小于自己的弹出） O（n）。 然后把左右之间较小的那个元素作为自己的父节点。
九章算法面试题37 主元素
九章算法面试题30 最短距离和
初阶：在一个n*m的矩阵中，有k个点，求矩阵中距离这k个点的距离和最近的点。
注：这里的距离采用曼哈顿距离——|x0-x1| + |y0-y1|
进阶：如果要求这个点与所给的k个点不重合，该怎么办？
堆辅助宽搜（O（k*lgk), 取决于所给的特定点个数）， 或者线性扫描（O（n*m), 事先预处理每个行列对应的特定点个数，这样每次计算a[i][j]都是O（1）复杂度，总复杂度O（n*m) )
九章算法面试题29 子矩阵的最大公约数
给定n*n的矩阵，需要查询任意子矩阵中所有数字的最大公约数。请给出一种设计思路，对矩阵进行预处理，加速查询。额外的空间复杂度要求O(n^2)以内。
四分线段树 或横纵剖分线段树
九章算法面试题21 寻找最近单词对
初阶：有一篇包含N个单词的文章和M个单词对，对于每个单词对，如果他们在文章中都出现了，求出他们在文章中的最近距离。例如文章为：ABBCABC，那么对于单词对(A,C)的最近距离是1（最后的ABC，A必须在C的前面）
进阶：假设N和M都是海量数据，有什么好的方法可以优化？
考虑 1 AC自动机进行多个目标字符串的查找； 或map reduce对多个字符串查找位置。 2 建立索引。 3 两个索引列表之间查找最小距离。可以线性扫描或二分。
九章算法面试题20 寻找重复的URL
给定A、B两个大文件，各存放50亿个url，每个url各占256字节，内存限制是4G，让你找出同时在A和B中出现的url。
方法1：使用BloomFilter（一种类似于hash表但比hash表占用空间更小的查重数据结构），通过K个不同的hash函数，将5G个URL映射到32G个bit位上，当且仅当K个hash函数得到的bit位上都是1时，代表该url重复出现。一般来讲K取8。该方法存在精度损失。时间复杂度O(n)
方法2： 一次hash分解文件（map），再一次hash扫描处理小文件（reduce）
九章算法面试题10 赛马
有25匹马，有一个5个赛道的马场，每场比赛可以决出5匹马的排名，假设每匹马发挥稳定，且不会出现名次相同的情况。问：如果要知道25匹马中跑得最快的马，需要几场比赛？如果需要知道跑得第二快的马，需要几场比赛？第三快的呢？
九章算法面试题9 前k大的和
初阶：有两个数组A和B，每个数组有k个数，从两个数组中各取一个数加起来可以组成k*k个和，求这些和中的前k大。
进阶：有N个数组，每个数组有k个数，从N个数组中各取一个数加起来可以组成k^N个和，求这些和中的前k大。
链式计算： 先对前两个数组求前k大和，将结果与第三个数组求前k大和，然后第四个……直到第N个 ，中间用到堆辅助宽搜
代码 https://code.csdn.net/snippets/527307
九章算法面试题8 第k大的数
初阶：有两个数组A和B，假设A和B已经有序（从大到小），求A和B数组中所有数的第K大。
进阶：有N台机器，每台机器上有一个有序的大数组，需要求得所有机器上所有数中的第K大。注意，需要考虑N台机器的并行计算能力。
进阶：两层二分。首先二分n；然后在每个机器上二分统计比n大的数个数，汇总并二分调整n
九章算法面试题2 抄书问题
有n本书和k个抄写员。要求n本书必须连续的分配给这k个抄写员抄写。也就是说前a1本书分给第一个抄写员，接下来a2本书分给第二个抄写员，如此类推（a1,a2需要你的算法来决定）。给定n,k和每本书的页数p1,p2..pn，假定每个抄写员速度一样（每分钟1页），k个抄写员同时开始抄写，问最少需要多少时间能够讲所有书全部抄写完工？（提示：本题有很多种算法可以在不同的时间复杂度下解决，需要尽可能的想到所有的方法）
解法1：动态规划
解法2；动态规划+决策单调。
同上一解法，但在x的枚举上进行优化，设s[i][j]为使得f[i][j]获得最优值的x是多少。有s[i][j-1]>=s[i][j]>=s[i-1][j]。因此x这一层的枚举不再是每次都是n而是总共加起来n。
解法3： 二分法+贪心