0.前言
去年碰巧在北京十一学校的图书馆里遇到这本书，当时就看的很开心，顶尖初、高中的教育水平属实让人羡慕。后来就买了一本，当作秋招刷题的入门准备书籍，看完感觉还是有一些收获的。这里主要是总结一下这本书的内容，解决一下其中提到的有意思的问题。
1.本书内容
1.1 整体思路
这本书从简单的排序讲起，桶排序、冒泡排序以及快速排序，各种经典的排序算法有必要总结并实现一下。然后讲了常见的数据结构：栈、队列和链表，其中用指针实现链表真的是C++初学者的噩梦。之后通过暴力的枚举思想引导到搜索的话题：DFS和BFS，其实搜索就是暴力枚举，不是吗？只是在枚举时涵盖了一些idea，虽然比较万能，但是效率往往比较差。然后讲到了和我地理专业有点相关的最短路径算法，这些不同算法的区别又是什么？之后讲了树，包括二叉树、堆和并查集，还有图的一些算法。
1.2 亮点
这本书给人印象最深的，其实是一些形象的比喻和思考，这里记录一下：
- 冒泡排序是走一趟让一个数据归位；快排也是走一趟让一个数据归位，但是与此同时将数据分成了基本有序的两块；
- 插入排序的过程就像打扑克插牌；
- 广度优先用队列，深度优先靠递归；
- 递归的本质就是栈；
- BFS、DFS搜索函数内的传参十分关键，传递染色/水管朝向/路径长度等；
- 并查集的关键点就在于“认爹”；
- 最短路径的Dijkstra算法与最小生成树的Prim算法异曲同工，都是逐渐找最近点对其他点进行松弛；
- 算法和数据结构是相互联系的；
2.遗留问题
2.1 快排中，如果将num[0]作为基数pivot，为什么一定要右指针先动、左指针后动？
假设如果左指针先动，找到一个大于基准值的位置，右指针再动。这样，由于右指针不能越过左指针的原因，不一定能找到小于基准值的位置，这样的交换产生的结果可能是错误的，一个大于基准值的数值被交换到了num[0]。而右指针先动，可以确保交换到左半部分的一定是小于基准值或者就是基准值本身的。
2.2 如何实现n层for循环嵌套？
我直接的想法是用递归，每调用一次递归函数相当于一层循环，很直观。而递归的本质是栈，将递归改写成递推其实是我的一个盲点，理论上借助栈应该可以把所有递归改写成递推。实际操作中，尾递归比较容易改写。尾递归指的是在函数结尾调用自己的递归方式。改写消除了递归的思想吗？并没有，只是以另一种方式呈现出来而已。
2.3 回溯是深度优先吗？
回溯是一种通常意义上的算法思想，而DFS只是其一种表现形式，后者主要在图、树的遍历中使用。
2.4 Floodfill算法计算一个图中独立子图的个数
Floodfill算法应该算是回溯的一种，找独立子图和LeetCode 200. Number of Islands 的意思大体一致。抓住一个岛屿DFS或BFS对邻居染色，整个地图上能染几次色就总共有几个独立岛屿，比较容易理解。
2.5 判断图是否为二部图/二分图
二部图，就是说将一个图的节点分成两部分，每一部分的内部不存在边，边只存在于两部分的节点之间。本书提到了染色法，其实也就是用DFS。对应到LeetCode 785. Is Graph Bipartite?，这道题用0/1代表颜色，1-color切换颜色的思路很有趣，方法仍然是标准的DFS。
2.6 Floyd-Warshall算法计算最短距离的有效性
这个方法一直因为其长度只有4行而出名，但是我始终没有理解这个算法中的动态规划思想。我的疑惑就在于，仅仅对n个点遍历了一次，以一个点作为中间点去更新所有点对的最短路径。为什么中间点的引入顺序要是从1到n呢？一般意见是这个是逐渐引入n个点作为参考，和顺序无关吗？我感觉是有关的。
《算法导论》中是用一种递归的角度来解释，假设ij两点最短路径路过的点的最大标号为k，那么ik，kj之间的路径必然也是最优的，而且这两段中的点的标号都比k小。依靠这样的观察，在计算两点之间最短距离时，可以只考虑，引入标号最大点作为中间点的结果。而ik和kj可以递归向前，走到引入k-1时的结果，这样就逐渐向前走，写成递推的形式就是Floyd算法。
2.7 满二叉树和完全二叉树的区别
面试也碰到了这个问题，满二叉树就是如果有根节点必须有左右子树，而完全二叉树是左右高度也要一致，然后最后一层不一定填满，但是叶节点必须聚集在左侧。
如何判断满二叉树？
满二叉树的定义国内、国外不同。国内的定义就是全满，必须是一个完整的三角形。而国外的满二叉树左右子树的深度不一定一样，只是说如果是根节点就必须同时有左子树和右子树，所以只需要递归确定即可。左右均为空肯定可以，左右不为空，则要求左右同时为满二叉树。
如何判断完全二叉树？
队列+广度优先，实现二叉树的层序遍历。队列不为空就接着循环，如果某个节点只有右子树，返回false，如果一个节点只有左节点或者其本身是叶节点，那么之后的节点都必须是叶节点才满足，破坏这种状态，返回false。
2.8 快速建立堆的方法和复杂度
可以在线性时间O(n)内将无序数组构造成堆。考虑用数组表示树，n/2以后就是完全二叉树的叶节点，只需要对每个叶节点进行siftup操作即可。具体证明可见《算法导论》中的建堆。
2.9 图的最小生成树是唯一的吗？
当所有边的权值都不相等时，最小生成树是唯一的。为什么？
可以用反证法：假设存在两棵最小生成树A和B。A和B的边肯定不全相同，我们拿出A和B包含的不同的边中权值最小的边k。不妨认为k来自A，将k加到B中后，会形成一个环，这个环上至少会有一条边的权值大于k（如果环上所有边的权重全都小于k，根据k的定义，这些边是AB所共有，那么A中就存在环，矛盾），将该边去掉，就得到了一个权重更低的生成树，所以B不是最小生成树，与初始条件矛盾。
如何判断最小生成树是否唯一呢？
最小生成树的算法Kruskal和Prim，前者可以用并查集+sort+贪心，后者和Dijkstra思路异曲同工。用算法生成最小生成树，记录用到的边，依次去掉边并看是否可以生成同样权值的最小生成树即可。一道相关的题目是POJ 1679，网上有很多题解，不再赘述。
2.10 寻找多数元素问题
问题：找到在一个列表中出现次数超过一半的元素。
解法：
1）走一遍，哈希表计数，时间n空间n；
2）排序取中间的数，时间nlgn空间1；
3）很有意思的思路，去掉两个不同的数，原来的多数元素仍是多数元素
对应到LeetCode 169. Majority Element，时间N空间1，还是蛮有趣的。