[需要重復遍歷結點多次的解法，簡單但不足以打動面試官](144.md)
[每個結點只遍歷一次的解法，正是面試官喜歡的](145.md)
- 目錄
- 扉頁
- 版權頁
- 推薦序一
- 推薦序二
- 前言
- 第1章 面試的流程
- 1.1 面試官談面試
- 1.2 面試的三種形式
- 1.2.1 電話面試
- 1.2.2 共享桌面遠程面試
- 1.2.3 現場面試
- 1.3 面試的三個環節
- 1.3.1 行為面試環節
- 1．應聘者的項目經驗
- 2．應聘者掌握的技能
- 3．回答“為什么跳槽”
- 1.3.2 技術面試環節
- 1．扎實的基礎知識
- 2．高質量的代碼
- 3．清晰的思路
- 4．優化效率的能力
- 5．優秀的綜合能力
- 1.3.3 應聘者提問環節
- 1.4 本章小結
- 第2章 面試需要的基礎知識
- 2.1 面試官談基礎知識
- 2.2 編程語言
- 2.2.1 C++
- 面試題1：賦值運算符函數
- 經典的解法，適用于初級程序員
- 考慮異常安全性的解法，高級程序員必備
- 2.2.2 C#
- 面試題2：實現Singleton模式
- 不好的解法一：只適用于單線程環境
- 不好的解法二：雖然在多線程環境中能工作但效率不高
- 可行的解法：加同步鎖前后兩次判斷實例是否已存在
- 強烈推薦的解法一：利用靜態構造函數
- 強烈推薦的解法二：實現按需創建實例
- 解法比較
- 2.3 數據結構
- 2.3.1 數組
- 面試題3：二維數組中的查找
- 2.3.2 字符串
- 面試題4：替換空格
- 時間復雜度為O（n2）的解法，不足以拿到Offer
- 時間復雜度為O（n）的解法，搞定Offer就靠它了
- 2.3.3 鏈表
- 面試題5：從尾到頭打印鏈表
- 2.3.4 樹
- 面試題6：重建二叉樹
- 2.3.5 棧和隊列
- 面試題7：用兩個棧實現隊列
- 2.4 算法和數據操作
- 2.4.1 查找和排序
- 面試題8：旋轉數組的最小數字
- 2.4.2 遞歸和循環
- 面試題9：斐波那契數列
- 效率很低的解法，挑剔的面試官不會喜歡
- 面試官期待的實用解法
- 時間復雜度O（logn）但不夠實用的解法
- 解法比較
- 2.4.3 位運算
- 面試題10：二進制中1的個數
- 可能引起死循環的解法
- 常規解法
- 能給面試官帶來驚喜的解法
- 2.5 本章小結
- 第3章 高質量的代碼
- 3.1 面試官談代碼質量
- 3.2 代碼的規范性
- 3.3 代碼的完整性
- 1．從3方面確保代碼的完整性
- 2．3種錯誤處理的方法
- 面試題11：數值的整數次方
- 自以為題目簡單的解法
- 全面但不夠高效的解法，我們離Offer已經很近了
- 全面又高效的解法，確保我們能拿到Offer
- 面試題12：打印1到最大的n位數
- 跳進面試官陷阱
- 在字符串上模擬數字加法的解法，繞過陷阱才能拿到Offer
- 把問題轉換成數字排列的解法，遞歸讓代碼更簡潔
- 面試題13：在O（1）時間刪除鏈表結點
- 面試題14：調整數組順序使奇數位于偶數前面
- 只完成基本功能的解法，僅適用于初級程序員
- 考慮可擴展性的解法，能秒殺Offer
- 3.4 代碼的魯棒性
- 面試題15：鏈表中倒數第k個結點
- 面試題16：反轉鏈表
- 面試題17：合并兩個排序的鏈表
- 面試題18：樹的子結構
- 3.5 本章小結
- 第4章 解決面試題的思路
- 4.1 面試官談面試思路
- 4.2 畫圖讓抽象問題形象化
- 面試題19：二叉樹的鏡像
- 面試題20：順時針打印矩陣
- 4.3 舉例讓抽象問題具體化
- 面試題21：包含min函數的棧
- 面試題22：棧的壓入、彈出序列
- 面試題23：從上往下打印二叉樹
- 面試題24：二叉搜索樹的后序遍歷序列
- 面試題25：二叉樹中和為某一值的路徑
- 4.4 分解讓復雜問題簡單化
- 面試題26：復雜鏈表的復制
- 面試題27：二叉搜索樹與雙向鏈表
- 面試題28：字符串的排列
- 4.5 本章小結
- 第5章 優化時間和空間效率
- 5.1 面試官談效率
- 5.2 時間效率
- 面試題29：數組中出現次數超過一半的數字
- 解法一：基于Partition函數的O（n）算法
- 解法二：根據數組特點找出O（n）的算法
- 解法比較
- 面試題30：最小的k個數
- 解法一：O（n）的算法，只有當我們可以修改輸入的數組時可用
- 解法二：O（nlogk）的算法，特別適合處理海量數據
- 解法比較
- 面試題31：連續子數組的最大和
- 解法一：舉例分析數組的規律
- 解法二：應用動態規劃法
- 面試題32：從1到n整數中1出現的次數
- 不考慮時間效率的解法，靠它想拿Offer有點難
- 從數字規律著手明顯提高時間效率的解法，能讓面試官耳目一新
- 面試題33：把數組排成最小的數
- 5.3 時間效率與空間效率的平衡
- 面試題34：丑數
- 逐個判斷每個整數是不是丑數的解法，直觀但不夠高效
- 創建數組保存已經找到的丑數，用空間換時間的解法
- 面試題35：第一個只出現一次的字符
- 面試題36：數組中的逆序對
- 面試題37：兩個鏈表的第一個公共結點
- 5.4 本章小結
- 第6章 面試中的各項能力
- 6.1 面試官談能力
- 6.2 溝通能力和學習能力
- 1．溝通能力
- 2．學習能力
- 3．善于學習、溝通的人也善于提問
- 6.3 知識遷移能力
- 面試題38：數字在排序數組中出現的次數
- 面試題39：二叉樹的深度
- 需要重復遍歷結點多次的解法，簡單但不足以打動面試官
- 每個結點只遍歷一次的解法，正是面試官喜歡的
- 面試題40：數組中只出現一次的數字
- 面試題41：和為s的兩個數字VS和為s的連續正數序列
- 面試題42：翻轉單詞順序VS左旋轉字符串
- 6.4 抽象建模能力
- 面試題43：n個骰子的點數
- 解法一：基于遞歸求骰子點數，時間效率不夠高
- 解法二：基于循環求骰子點數，時間性能好
- 面試題44：撲克牌的順子
- 面試題45：圓圈中最后剩下的數字
- 經典的解法，用環形鏈表模擬圓圈
- 創新的解法，拿到Offer不在話下
- 6.5 發散思維能力
- 面試題46：求1＋2＋…＋n
- 解法一：利用構造函數求解
- 解法二：利用虛函數求解
- 解法三：利用函數指針求解
- 解法四：利用模板類型求解
- 面試題47：不用加減乘除做加法
- 面試題48：不能被繼承的類
- 常規的解法：把構造函數設為私有函數
- 新奇的解法：利用虛擬繼承，能給面試官留下很好的印象
- 6.6 本章小結
- 第7章 兩個面試案例
- 7.1 案例一：（面試題49）把字符串轉換成整數
- 7.2 案例二：（面試題50）樹中兩個結點的最低公共祖先