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

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