本章导读
笔试和面试中,除了字符串,另一类出现频率极高的问题便是与数组相关的问题。在阅读完第1章和本第二章后,读者会慢慢了解到解决面试编程题的有几种常用思路。首先一般考虑“万能的”暴力穷举(递归、回溯),如求n个数的全排列或八皇后(N皇后问题)。但因为穷举时间复杂度通常过高,所以需要考虑更好的方法,如分治法(通过分而治之,然后归并),以及空间换时间(如活用哈希表)。
此外,选择合适的数据结构可以显著提升效率,如寻找最小的k个数中,用堆代替数组。
再有,如果题目允许排序,则可以考虑排序。比如,寻找和为定值的两个数中,先排序,然后用前后两个指针往中间扫。而如果如果已经排好序了(如杨氏矩阵查找中),则想想有无必要二分。但是,如果题目不允许排序呢?这个时候,我们可以考虑不改变数列顺序的贪心算法(如最小生成树Prim、Kruskal及最短路dijkstra),或动态规划(如 01背包问题,每一步都在决策)。
最后,注意细节处理,不要忽略边界条件,如字符串转换成整数。
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「IT平头哥联盟」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程