筆試和面試中,除了字符串,另一類出現頻率極高的問題便是與數組相關的問題。在閱讀完第1章和本第二章后,讀者會慢慢了解到解決面試編程題的有幾種常用思路。首先一般考慮“萬能的”暴力窮舉(遞歸、回溯),如求n個數的全排列或八皇后(N皇后問題)。但因為窮舉時間復雜度通常過高,所以需要考慮更好的方法,如分治法(通過分而治之,然后歸并),以及空間換時間(如活用哈希表)。
此外,選擇合適的數據結構可以顯著提升效率,如尋找最小的k個數中,用堆代替數組。
再有,如果題目允許排序,則可以考慮排序。比如,尋找和為定值的兩個數中,先排序,然后用前后兩個指針往中間掃。而如果如果已經排好序了(如楊氏矩陣查找中),則想想有無必要二分。但是,如果題目不允許排序呢?這個時候,我們可以考慮不改變數列順序的貪心算法(如最小生成樹Prim、Kruskal及最短路dijkstra),或動態規劃(如 01背包問題,每一步都在決策)。
最后,注意細節處理,不要忽略邊界條件,如字符串轉換成整數。
- 關于
- 第一部分 數據結構
- 第一章 字符串
- 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.15 本章習題
- 第三章 樹
- 3.0 本章導讀
- 3.1 紅黑樹
- 3.2 B樹
- 3.3 最近公共祖先LCA
- 3.10 本章習題
- 第二部分 算法心得
- 第四章 查找匹配
- 4.1 有序數組的查找
- 4.2 行列遞增矩陣的查找
- 4.3 出現次數超過一半的數字
- 第五章 動態規劃
- 5.0 本章導讀
- 5.1 最大連續乘積子串
- 5.2 字符串編輯距離
- 5.3 格子取數
- 5.4 交替字符串
- 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 網絡協議