劍指Offer：名企面試官精講典型編程題

第1章  面試的流程 1
1.1  面試官談面試 1
1.2  面試的三種形式 2
1.2.1  電話面試 2
1.2.2  共享桌面遠程面試 3
1.2.3  現(xiàn)場面試 4
1.3  面試的三個環(huán)節(jié) 5
1.3.1  行為面試環(huán)節(jié) 5
應(yīng)聘者的項目經(jīng)驗 6
應(yīng)聘者掌握的技能 7
回答“為什么跳槽” 8
1.3.2  技術(shù)面試環(huán)節(jié) 10
扎實的基礎(chǔ)知識 10
高質(zhì)量的代碼 11
清晰的思路 14
優(yōu)化效率的能力 15
優(yōu)秀的綜合能力 16
1.3.3  應(yīng)聘者提問環(huán)節(jié) 17
1.4  本章小結(jié) 18
第2章  面試需要的基礎(chǔ)知識 20
2.1  面試官談基礎(chǔ)知識 20
2.2  編程語言 22
2.2.1  C++ 22
面試題1：賦值運算符函數(shù) 24
經(jīng)典的解法，適用于初級程序員 25
考慮異常安全性的解法，高級程序員必備 26
2.2.2  C# 27
面試題2：實現(xiàn)Singleton模式 31
不好的解法一：只適用于單線程 31
不好的解法二：可用于多線程但效率不高 32
可行的解法：同步鎖前后兩次判斷 33
推薦的解法一：利用靜態(tài)構(gòu)造函數(shù) 34
推薦的解法二：按需創(chuàng)建實例 34
解法比較 35
2.3  數(shù)據(jù)結(jié)構(gòu) 36
2.3.1  數(shù)組 36
面試題3：二維數(shù)組中的查找 38
2.3.2  字符串 42
面試題4：替換空格 44
O(n2)的解法，不足以拿到Offer 45
O(n)的解法，搞定Offer就靠它 46
2.3.3  鏈表 49
面試題5：從尾到頭打印鏈表 51
2.3.4  樹 53
面試題6：重建二叉樹 55
2.3.5  棧和隊列 58
面試題7：用兩個棧實現(xiàn)隊列 59
2.4  算法和數(shù)據(jù)操作 62
2.4.1  查找和排序 63
面試題8：旋轉(zhuǎn)數(shù)組的最小數(shù)字 66
2.4.2  遞歸和循環(huán) 71
面試題9：斐波那契數(shù)列 73
效率很低的解法，面試官不會喜歡 73
面試官期待的實用解法 74
O(logn)但不夠?qū)嵱玫慕夥?nbsp;74
解法比較 75
2.4.3  位運算 77
面試題10：二進制中1的個數(shù) 78
可能引起死循環(huán)的解法 79
常規(guī)解法 79
能給面試官帶來驚喜的解法 80
2.5  本章小結(jié) 82
第3章  高質(zhì)量的代碼 84
3.1  面試官談代碼質(zhì)量 84
3.2  代碼的規(guī)范性 86
3.3  代碼的完整性 87
從3方面確保代碼的完整性 87
3種錯誤處理的方法 88
面試題11：數(shù)值的整數(shù)次方 90
自以為題目簡單的解法 90
全面但不夠高效的解法，離Offer已經(jīng)很近了 90
全面又高效的解法，確保能拿到Offer 92
面試題12：打印1到最大的n位數(shù) 94
跳進面試官陷阱 94
在字符串上模擬數(shù)字加法 94
把問題轉(zhuǎn)換成數(shù)字排列 97
面試題13：在O(1)時間刪除鏈表結(jié)點 99
面試題14：調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面 102
只完成基本功能的解法，僅適用于初級程序員 102
考慮可擴展性的解法，能秒殺Offer 104
3.4  代碼的魯棒性 106
面試題15：鏈表中倒數(shù)第k個結(jié)點 107
面試題16：反轉(zhuǎn)鏈表 112
面試題17：合并兩個排序的鏈表 114
面試題18：樹的子結(jié)構(gòu) 117
3.5  本章小結(jié) 121
第4章  解決面試題的思路 123
4.1 面試官談面試思路 123
面試題19：二叉樹的鏡像 125
4.2 畫圖讓抽象問題形象化 125
面試題20：順時針打印矩陣 127
4.3 舉例讓抽象問題具體化 131
面試題21：包含min函數(shù)的棧 132
面試題22：棧的壓入、彈出序列 134
面試題23：從上往下打印二叉樹 137
面試題24：二叉搜索樹的后序遍歷序列 140
面試題25：二叉樹中和為某一值的路徑 143
4.4 分解讓復(fù)雜問題簡單化 146
面試題26：復(fù)雜鏈表的復(fù)制 147
面試題27：二叉搜索樹與雙向鏈表 151
面試題28：字符串的排列 154
4.5 本章小結(jié) 158
第5章  優(yōu)化時間和空間效率 160
5.1 面試官談效率 160
5.2 時間效率 162
面試題29：數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字 163
基于Partition函數(shù)的O(n)算法 163
利用數(shù)組特點的O(n)算法 165
解法比較 166
面試題30：最小的k個數(shù) 167
O(n)的算法，只當可以修改輸入數(shù)組時可用 167
O(nlogk)的算法，適合處理海量數(shù)據(jù) 168
解法比較 169
面試題31：連續(xù)子數(shù)組的最大和 171
舉例分析數(shù)組的規(guī)律 171
應(yīng)用動態(tài)規(guī)劃法 173
面試題32：從1到n整數(shù)中1出現(xiàn)的次數(shù) 174
不考慮效率的解法，想拿Offer有點難 174
明顯提高效率的解法，讓面試官耳目一新 175
面試題33：把數(shù)組排成最小的數(shù) 177
5.3 時間效率與空間效率的平衡 181
面試題34：丑數(shù) 182
逐個判斷整數(shù)是不是丑數(shù)的解法 182
創(chuàng)建數(shù)組保存已經(jīng)找到的丑數(shù)的解法 183
面試題35：第一個只出現(xiàn)一次的字符 186
面試題36：數(shù)組中的逆序?qū)?nbsp;189
面試題37：兩個鏈表的第一個公共結(jié)點 193
5.4 本章小結(jié) 196
第6章  面試中的各項能力 198
6.1  面試官談能力 198
6.2  溝通能力和學(xué)習(xí)能力 200
溝通能力 200
學(xué)習(xí)能力 200
善于學(xué)習(xí)、溝通的人也善于提問 201
6.3  知識遷移能力 203
面試題38：數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù) 204
面試題39：二叉樹的深度 207
重復(fù)遍歷結(jié)點的解法，不足以打動面試官 209
只遍歷結(jié)點一次的解法，正是面試官喜歡的 209
面試題40：數(shù)組中只出現(xiàn)一次的數(shù)字 211
面試題41：和為s的兩個數(shù)字VS和為s的連續(xù)正數(shù)序列 214
面試題42：翻轉(zhuǎn)單詞順序 VS左旋轉(zhuǎn)字符串 218
6.4  抽象建模能力 222
面試題43：n個骰子的點數(shù) 223
基于遞歸求骰子點數(shù)，時間效率不夠高 223
基于循環(huán)求骰子點數(shù)，時間性能好 224
面試題44：撲克牌的順子 226
面試題45：圓圈中最后剩下的數(shù)字 228
經(jīng)典的解法，用循環(huán)鏈表模擬圓圈 229
創(chuàng)新的解法，拿到Offer不在話下 230
6.5  發(fā)散思維能力 232
面試題46：求1+2+…+n 233
利用構(gòu)造函數(shù)求解 234
利用虛函數(shù)求解 234
利用函數(shù)指針求解 235
利用模板類型求解 236
面試題47：不用加減乘除做加法 237
面試題48：不能被繼承的類 239
常規(guī)的解法：把構(gòu)造函數(shù)設(shè)為私有函數(shù) 239
新奇的解法：利用虛擬繼承 240
6.6  本章小結(jié) 241
第7章  兩個面試案例 243
7.1  案例一：（面試題49）把字符串轉(zhuǎn)換成整數(shù) 244
7.2  案例二：（面試題50）樹中兩個結(jié)點的最低公共祖先 252