书籍简介
第一章 字符串
1.0 本章导读
1.1 旋转字符串
1.2 字符串包含
1.3 字符串转换成整数
1.4 回文判断
1.5 最长回文子串
1.6 字符串的全排列
1.10 本章习题
第二章 数组
2.0 本章导读
2.1 寻找最小的 k 个数
2.2 寻找和为定值的两个数
2.3 寻找和为定值的多个数
2.4 最大连续子数组和
2.5 跳台阶
2.6 奇偶排序
2.7 荷兰国旗
2.8 矩阵相乘
2.9 完美洗牌
2.10 K个最小和 (UVA 11997 K Smallest Sums)
2.15 本章习题
第三章 树
3.0 本章导读
3.1 红黑树
3.2 B树
3.3 最近公共祖先LCA
3.5 R树：处理空间存储问题
3.10 本章习题
第四章 查找匹配
4.1 有序数组的查找
4.2 行列递增矩阵的查找
4.3 出现次数超过一半的数字
第五章 动态规划
5.0 本章导读
5.1 最大连续乘积子串
5.2 字符串编辑距离
5.3 格子取数
5.4 交替字符串
5.6 最长递增子序列
5.10 本章习题
第六章 海量数据处理
6.0 本章导读
6.1 关联式容器
6.2 分而治之
6.3 simhash算法
6.4 外排序
6.5 MapReduce
6.6 多层划分
6.7 Bitmap
6.8 Bloom filter
6.9 Trie树
6.10 数据库
6.11 倒排索引
6.15 本章习题
第七章 机器学习
7.1 K 近邻算法
7.2 支持向量机
附录 更多题型
附录A 语言基础
附录B 概率统计
附录C 智力逻辑
附录D 系统设计
附录E 操作系统
附录F 网络协议
2.0 本章导读 - 《程序员编程艺术：面试和算法心得》 - IT书包
网站首页
2.0 本章导读
笔试和面试中，除了字符串，另一类出现频率极高的问题便是与数组相关的问题。在阅读完第1章和本第二章后，读者会慢慢了解到解决面试编程题的有几种常用思路。首先一般考虑“万能的”暴力穷举（递归、回溯），如求n个数的全排列或八皇后（N皇后问题）。但因为穷举时间复杂度通常过高，所以需要考虑更好的方法，如分治法（通过分而治之，然后归并），以及空间换时间（如活用哈希表）。 此外，选择合适的数据结构可以显著提升效率，如寻找最小的k个数中，用堆代替数组。 再有，如果题目允许排序，则可以考虑排序。比如，寻找和为定值的两个数中，先排序，然后用前后两个指针往中间扫。而如果如果已经排好序了（如杨氏矩阵查找中），则想想有无必要二分。但是，如果题目不允许排序呢？这个时候，我们可以考虑不改变数列顺序的贪心算法（如最小生成树Prim、Kruskal及最短路dijkstra），或动态规划（如 01背包问题，每一步都在决策）。 最后，注意细节处理，不要忽略边界条件，如字符串转换成整数。
上一篇：
第二章 数组
下一篇：
2.1 寻找最小的 k 个数
