精选的一些《编程之美》相关资料

　　又要到一年的招聘季了，肯定又有很多人开始啃《编程之美》了吧。这本书从开阔视野的角度来说很好，不过限于篇幅，有的问题并没有讲清楚（甚至问题叙述模棱两可、被标榜为“鼓励同面试官交流以获得更多细节”）；或者扩展问题本身很难，没有给予解答和提示。在我看书并在网络上查到的相关资料中，有很多重复的，也有不少基本没什么价值，有价值的文章是少数。为了便于查阅，也为了方便后人不必在搜索上浪费时间，我把比较有价值的文章的链接整理在下面，并附以简单说明。另外，对于一些比较早的资料，对应的是前几版的《编程之美》；《编程之美》早起版本错误之多在勘误表上可见一斑，不过既然新版已经修正了这些问题，那就请使用新书的读者放心，并在浏览资料时注意。

　　作为定位与《编程之美》类似的《剑指Offer》，上面有不少对相同问题的解；后者读起来实战的临场感更强一些（测试用例、边界条件等），两本书都值得一读。解法相同的题就没必要重述了，而解法不同或者做了一些扩展的题目一并标在下面。

 

1.1 让CPU占用率曲线听你指挥

　　《编程之美》读书笔记23： 1.1 让CPU占用率曲线听你指挥

　　　　很多完整程序，这里取个代表。事实上对于不了解windows编程的人来说，这个问题难度要高于3星。

 

1.3 一摞烙饼的排序

　　烙饼啊烙饼{转自ITEO

　　　　对扩展问题做了详细探讨，原出处没有找到。

 

1.7  光影切割问题

　　逆序对：从插入排序到归并排序

　　　　我的拙作，介绍了逆序对的寻找方式的优化。

 

1.11 NIM（1）一排石头的游戏

1.12 NIM（2）“拈”游戏分析

1.13 NIM（3）两堆石头的游戏

　　拈及其各種變形遊戲

　　　　第五页对1.13扩展的NIM（4）游戏有很好的解释，并且全文可以看作NIM游戏的阅读材料。

　　　　我有写一篇总结NIM游戏规律的博文的计划，不过不知道时间是否允许。

　　《剑指Offer》面试题40：只出现一次的数字

　　　　又是XOR的应用。

 

1.18 挖雷游戏

4.11 扫雷游戏的概率

　　这两道题原书没有解。

　　快照/转帖

　　　　最早解答4.11的博文的百度快照，源地址我打不开。

　　编程之美扫雷篇

　　　　另一个角度解答4.11问题。

　　解答《编程之美》1.18问题1：给所有未标识方块标注有地雷概率

　　　　我的拙作之二，对于网络上没有分析的1.18问题1进行解答。

 

2.1 求二进制中1的个数

　　《编程之美》读书笔记——“求二进制数中1的个数”

　　　　这个是我买的纸质版《编程之美》这一节的读者反馈里的链接，不过翻了下电子版，似乎早期的没有，因此附在这里。

　　《剑指Offer》面试题10：二进制中1的个数

　　　　如果输入是负数，那么《编程之美》第一段代码还能运行吗？（尽管它与《剑指Offer》解一不同）

 

2.19 区间重合判断

　　编程之美2.19——区间重合判断（线段树）

　　　　扩展问题二维空间的覆盖问题的线段树解。

 

2.21 只考加法的面试题

　　《编程之美》2.21 只考加法的面试题

　　　　这个题原书也没有解，此文已经很详细了。

 

3.4 从无头链表中删除节点

　　《剑指Offer》面试题13：在O(1)时间删除链表结点

　　　　如果给定了单链表头结点和一个结点的指针，要求删除此结点（可能是头结点或尾结点），又该如何求解？

3.6 编程判断两个链表是否相交

 　　《编程之美》3.6判断链表是否相交之扩展：链表找环方法证明

 

　　　　我的拙作之三，其中原问题的解借鉴的部分请见注释，此文主要是说明怎样证明找环和找环入口算法的正确性。

　　　　同时，根据判环算法，可以解决3.11的扩展问题：链表判断是否有环的程序改错。

 

3.7 队列中取最大值操作问题

　　《剑指Offer》面试题7：用两个栈实现一个队列

　　　　介绍了另一个问题：如何用两个队列实现一个栈？ 

 

3.8 求二叉树中节点的最大距离

　　《编程之美: 求二叉树中节点的最大距离》的另一个解法

　　　　本节总结里提到的链接，其实个人认为代码比原书中漂亮多了。我转载了此文：http://www.cnblogs.com/wuyuegb2312/articles/3174476.html

 

3.10 分层遍历二叉树

　　《编程之美：分层遍历二叉树》的另外两个实现

　　　　本节节末提到的链接。其实我似乎记得当初在上严蔚敏版《数据结构》课程时，分层遍历二叉树就是借助队列实现的，思想和这个一样。

 

3.11 程序改错

　　http://www.cnblogs.com/wuyuegb2312/archive/2013/05/26/3090369.html

我的拙作之四，全方位分析二分查找这个老生常谈的问题，并不仅仅限于代码改错。有意避开陷阱要比掉入陷阱后想办法爬出来更好，虽然这并不代表我们不需要知道如何爬上来。扩展问题——判断链表是否有环的程序改错——请看3.6的链接。

 

4.2 瓷砖覆盖地板

　　poj 2411 & 编程之美 4.2 瓷砖覆盖地板

是对扩展问题1“1*2瓷砖覆盖8*8地板”的状态动态规划解法中我所看到的最简洁易懂、空间占用少的。

更可贵的是本文提供了p*q瓷砖覆盖M*N地板可行性的一般结论和阅读资料（MIT的pdf）。

《剑指Offer》面试题9：斐波那契数列

　　扩展问题中，2*M的地板覆盖问题的递推公式F(M)=F(M-1)+F(M-2)，形式上是斐波那契数列。

 

4.3 买票找零

　　从《编程之美》买票找零问题说起，娓娓道来卡特兰数——兼爬坑指南

　　　　我的拙作之五，标题说明一切。

 

4.5 磁带文件存放优化

　　《编程之美》4.5磁带文件存放优化：最优解是怎样炼成的

 

　　　　我的拙作之六，原书对于解是最优解根本没有说明白，只是举了个例子而已；这篇文章将告诉你为什么是最优解。

 

4.7 蚂蚁爬杆

　　编程之美4.7蚂蚁爬杆扩展问题附猎人抓狐狸(必胜策略)

　　　　对扩展问题很详细的探讨。

 

另外再附两个链接，请注意时效性：

　　博文视点

　　　　《编程之美》出版方，收录了一些问题的网友的解答。

　　薛迪的专栏

　　　　很多解题法被《编程之美》收录。