课堂上的《编程之美》 (增订版)

增订说明

这是一篇旧作, 本次发布更新和补充了部分内容.

手里拿的是《编程之美》的一刷, 是刚上市的时候买的, 一直没顾得上看. 觉得给学生当参考书看很不错, 读了一些, 发现在课堂上可以用, 而且效果不错.

我采用的讲解方法是从实例到抽象, 最终是想让学生能了解更为一般化的设计技术和模式. 　
　　
下面的评注仅是抛砖引玉, 希望读者给出更多的拓展.

题目与评注

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

• 理论结合实践, 非常好的一道的问题, 是不是可以考虑能实现内存使用曲线呢?

1.15 构造数独 4.9 数独知多少

• 可以考虑数独的求解, 参考一下Dancing Links, 例如这篇.
• 关于数独的相关知识可以参考wiki.
• 我的微博里提到过, 数独中有个重要的数字是17, 这是存在唯一解的初始数字个数下界, 也就是说16个及以下初始数字不存在唯一解(无解除外).

2.1 求二进制数中1的个数

• @miloyip提到了一些拓展.

2.3 寻找发帖“水王”

• 这个问题是Majority问题(过半数), 在Voting时比较有用, 可以参考Udi Manber的Introduction to Algorithms: A Creative Approach, 是一种归纳的思路.

2.4 1的数目

• 考虑大整数(用字符串表示)情况下的解法.

2.5 寻找最大的k个数

• 这道问题有Linear Selection算法. 当然还可以推广到MultiSelection问题. 此外, 对于在外存中的海量数据, 又应该如何考虑?

2.10 寻找数组中的最大值和最小值

• 考虑此问题的下界(lower bound).

2.12 快速寻找满足条件的两个数

• 我最早在CLRS上见过此题. 关键是解法三的证明, 思路清楚了, 理解起来也就方便了.

2.17 数组循环移位

• 这个问题有一个比较复杂的解法, 就是利用“就地置换”(In-place Permutation)来做. 当然, 根据《编程珠玑》上的说法, 要思路清晰, 不要太复杂。

3.2 电话号码对应英语单词

• 讲点trie就更好不过了. 可参阅wiki.

3.4 从无头单链表中删除节点

• 我个人认为这是一道“屠龙”题. 一般来说删除时会维护前一个节点的指针, 另外要是删除链表的尾元素这个例子会出错的.

3.10 分层遍历二叉树

• 在讲树的层序遍历时候可以用. 一般采用BFS的标准思路, 即利用队列来完成. 此问题还可以用于求解决贾宪三角(很多人称其为杨辉三角, 不甚严谨). 《编程之美》给出了多种思路, 要是这样再总结一下, 学生对此问题应该非常清楚了.
• 可以将迷宫想象成多分支生长的树, 树能长到的地方就是可以到达的交叉路口, 而且最先触到的分支也是从根开始最近的路线.
• 不过, 现在的面试题已经进化到不用额外存储空间(递归栈也属于此类)去层次遍历的形态了, 注意结点的父亲指针可以更改, 此题可见stackoverflow.

4.6 桶中取黑白球

• 经典的咖啡罐问题, 可以考虑一般情况, 是理解循环不变量的一个非常好的例子.

期望

现在算法题越来越重要，国外的几本编程面试经典在不断推出新版，例如：

1. Cracking the Coding Interview: 189 Programming Questions and Solutions 第6版.
2. Programming Interviews Exposed: Secrets to Landing Your Next Job, 第3版.

除此之外, 也有很多新的站点能让大家展开讨论, 例如Codeforces和LeetCode, 在此也希望《编程之美》能不断更新, 为此类中文书籍再创一个新的高峰.