本章导读

笔试和面试中,除了字符串,另一类出现频率极高的问题便是与数组相关的问题。在阅读完第1章和本第二章后,读者会慢慢了解到解决面试编程题的有几种常用思路。首先一般考虑“万能的”暴力穷举(递归、回溯),如求n个数的全排列或八皇后(N皇后问题)。但因为穷举时间复杂度通常过高,所以需要考虑更好的方法,如分治法(通过分而治之,然后归并),以及空间换时间(如活用哈希表)。

此外,选择合适的数据结构可以显著提升效率,如寻找最小的k个数中,用堆代替数组。

再有,如果题目允许排序,则可以考虑排序。比如,寻找和为定值的两个数中,先排序,然后用前后两个指针往中间扫。而如果如果已经排好序了(如杨氏矩阵查找中),则想想有无必要二分。但是,如果题目不允许排序呢?这个时候,我们可以考虑不改变数列顺序的贪心算法(如最小生成树Prim、Kruskal及最短路dijkstra),或动态规划(如 01背包问题,每一步都在决策)。

最后,注意细节处理,不要忽略边界条件,如字符串转换成整数。