增订说明
这是一篇旧作, 本次发布更新和补充了部分内容.
手里拿的是《编程之美》的一刷, 是刚上市的时候买的, 一直没顾得上看. 觉得给学生当参考书看很不错, 读了一些, 发现在课堂上可以用, 而且效果不错.
我采用的讲解方法是从实例到抽象, 最终是想让学生能了解更为一般化的设计技术和模式.
下面的评注仅是抛砖引玉, 希望读者给出更多的拓展.
题目与评注
1.1 让CPU占用率曲线听你指挥
- 理论结合实践, 非常好的一道的问题, 是不是可以考虑能实现内存使用曲线呢?
1.15 构造数独 4.9 数独知多少
- 可以考虑数独的求解, 参考一下Dancing Links, 例如这篇.
- 关于数独的相关知识可以参考wiki.
- 我的微博里提到过, 数独中有个重要的数字是17, 这是存在唯一解的初始数字个数下界, 也就是说16个及以下初始数字不存在唯一解(无解除外).
2.1 求二进制数中1的个数
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 桶中取黑白球
- 经典的咖啡罐问题, 可以考虑一般情况, 是理解循环不变量的一个非常好的例子.
期望
现在算法题越来越重要，国外的几本编程面试经典在不断推出新版，例如：
- Cracking the Coding Interview: 189 Programming Questions and Solutions 第6版.
- Programming Interviews Exposed: Secrets to Landing Your Next Job, 第3版.
除此之外, 也有很多新的站点能让大家展开讨论, 例如Codeforces和LeetCode, 在此也希望《编程之美》能不断更新, 为此类中文书籍再创一个新的高峰.
