程序員代碼面試指南：IT名企算法與數(shù)據(jù)結(jié)構(gòu)題目最優(yōu)解

第1章 棧和隊列 1
設(shè)計一個有g(shù)etMin功能的棧（士 ★☆☆☆） 1
由兩個棧組成的隊列（尉 ★★☆☆） 5
如何僅用遞歸函數(shù)和棧操作逆序一個棧（尉 ★★☆☆） 7
貓狗隊列（士 ★☆☆☆） 10
用一個棧實現(xiàn)另一個棧的排序（士 ★☆☆☆） 13
用棧來求解漢諾塔問題（校 ★★★☆） 14
生成窗口**值數(shù)組（尉 ★★☆☆） 19
構(gòu)造數(shù)組的MaxTree（校 ★★★☆） 22
求**子矩陣的大小（校 ★★★☆） 26
第2章 鏈表問題 32
打印兩個有序鏈表的公共部分（士 ★☆☆☆） 32
在單鏈表和雙鏈表中刪除倒數(shù)第K個節(jié)點（士 ★☆☆☆） 33
刪除鏈表的中間節(jié)點和a/b處的節(jié)點（士 ★☆☆☆） 36
反轉(zhuǎn)單向和雙向鏈表（士 ★☆☆☆） 38
反轉(zhuǎn)部分單向鏈表（士 ★☆☆☆） 40
環(huán)形單鏈表的約瑟夫問題（原問題：士 ★☆☆☆ 進(jìn)階：校 ★★★☆） 41
判斷一個鏈表是否為回文結(jié)構(gòu)（普通解法 士 ★☆☆☆）
（進(jìn)階解法 尉 ★★☆☆） 46
將單向鏈表按某值劃分成左邊小、中間相等、右邊大的形式（尉 ★★☆☆） 50
復(fù)制含有隨機(jī)指針節(jié)點的鏈表（尉 ★★☆☆） 54
兩個單鏈表生成相加鏈表（士 ★☆☆☆） 57
兩個單鏈表相交的一系列問題（將 ★★★★） 60
將單鏈表的每K個節(jié)點之間逆序（尉 ★★☆☆） 66
刪除無序單鏈表中值重復(fù)出現(xiàn)的節(jié)點（士 ★☆☆☆） 69
在單鏈表中刪除指定值的節(jié)點（士 ★☆☆☆） 71
將搜索二叉樹轉(zhuǎn)換成雙向鏈表（尉 ★★☆☆） 72
單鏈表的選擇排序（士 ★☆☆☆） 77
一種怪異的節(jié)點刪除方式（士 ★☆☆☆） 79
向有序的環(huán)形單鏈表中插入新節(jié)點（士 ★☆☆☆） 80
合并兩個有序的單鏈表（士 ★☆☆☆） 82
按照左右半?yún)^(qū)的方式重新組合單鏈表（士 ★☆☆☆） 84
第3章 二叉樹問題 86
分別用遞歸和非遞歸方式實現(xiàn)二叉樹先序、中序和后序遍歷（校 ★★★☆） 86
打印二叉樹的邊界節(jié)點（尉 ★★☆☆） 93
如何較為直觀地打印二叉樹（尉 ★★☆☆） 98
二叉樹的序列化和反序列化（士 ★☆☆☆） 101
遍歷二叉樹的神級方法（將 ★★★★） 105
在二叉樹中找到累加和為指定值的*長路徑長度（尉 ★★☆☆） 113
找到二叉樹中的**搜索二叉子樹（尉 ★★☆☆） 115
找到二叉樹中符合搜索二叉樹條件的**拓?fù)浣Y(jié)構(gòu)（校 ★★★☆） 117
二叉樹的按層打印與ZigZag打?。ㄎ?★★☆☆） 127
調(diào)整搜索二叉樹中兩個錯誤的節(jié)點（原問題：尉 ★★☆☆）
（進(jìn)階問題：將 ★★★★） 132
判斷t1樹是否包含t2樹全部的拓?fù)浣Y(jié)構(gòu)（士 ★☆☆☆） 138
判斷t1樹中是否有與t2樹拓?fù)浣Y(jié)構(gòu)完全相同的子樹（校 ★★★☆） 140
判斷二叉樹是否為平衡二叉樹（士 ★☆☆☆） 142
根據(jù)后序數(shù)組重建搜索二叉樹（士 ★☆☆☆） 144
判斷一棵二叉樹是否為搜索二叉樹和完全二叉樹（士 ★☆☆☆） 146
通過有序數(shù)組生成平衡搜索二叉樹（士 ★☆☆☆） 148
在二叉樹中找到一個節(jié)點的后繼節(jié)點（尉 ★★☆☆） 149
在二叉樹中找到兩個節(jié)點的*近公共祖先（原問題難度：士 ★☆☆☆）
（進(jìn)階問題難度：尉 ★★☆☆ 再進(jìn)階問題難度：校 ★★★☆） 151
Tarjan算法與并查集解決二叉樹節(jié)點間*近公共祖先的批量查詢問題
（校 ★★★☆） 157
二叉樹節(jié)點間的**距離問題（尉 ★★☆☆） 167
先序、中序和后序數(shù)組兩兩結(jié)合重構(gòu)二叉樹（先序與中序結(jié)合 士 ★☆☆☆）
（中序與后序結(jié)合 士 ★☆☆☆ 先序與后序結(jié)合 尉 ★★☆☆） 169
通過先序和中序數(shù)組生成后序數(shù)組（士 ★☆☆☆） 172
統(tǒng)計和生成所有不同的二叉樹（尉 ★★☆☆） 173
統(tǒng)計完全二叉樹的節(jié)點數(shù)（尉 ★★☆☆） 176
第4章 遞歸和動態(tài)規(guī)劃 179
斐波那契系列問題的遞歸和動態(tài)規(guī)劃（將 ★★★★） 179
矩陣的*小路徑和（尉 ★★☆☆） 185
換錢的*少貨幣數(shù)（尉 ★★☆☆） 189
換錢的方法數(shù)（尉 ★★☆☆） 194
*長遞增子序列（校 ★★★☆） 200
漢諾塔問題（校 ★★★☆） 204
*長公共子序列問題（尉 ★★☆☆） 208
*長公共子串問題（校 ★★★☆） 211
*小編輯代價（校 ★★★☆） 215
字符串的交錯組成（校 ★★★☆） 218
龍與地下城游戲問題（尉 ★★☆☆） 221
數(shù)字字符串轉(zhuǎn)換為字母組合的種數(shù)（尉 ★★☆☆） 223
表達(dá)式得到期望結(jié)果的組成種數(shù)（校 ★★★☆） 226
排成一條線的紙牌博弈問題（尉 ★★☆☆） 231
跳躍游戲（士 ★☆☆☆） 233
數(shù)組中的*長連續(xù)序列（尉 ★★☆☆） 234
N皇后問題（校 ★★★☆） 236
第5章 字符串問題 240
判斷兩個字符串是否互為變形詞（士 ★☆☆☆） 240
字符串中數(shù)字子串的求和（士 ★☆☆☆） 241
去掉字符串中連續(xù)出現(xiàn)k個0的子串（士 ★☆☆☆） 243
判斷兩個字符串是否互為旋轉(zhuǎn)詞（士 ★☆☆☆） 245
將整數(shù)字符串轉(zhuǎn)成整數(shù)值（尉 ★★☆☆） 246
替換字符串中連續(xù)出現(xiàn)的指定字符串（士 ★☆☆☆） 249
字符串的統(tǒng)計字符串（士 ★☆☆☆） 251
判斷字符數(shù)組中是否所有的字符都只出現(xiàn)過一次（按要求一實現(xiàn)的方法 士 ★☆☆☆）
（按要求二實現(xiàn)的方法 尉 ★★☆☆） 253
在有序但含有空的數(shù)組中查找字符串（尉 ★★☆☆） 256
字符串的調(diào)整與替換（士 ★☆☆☆） 258
翻轉(zhuǎn)字符串（士 ★☆☆☆） 260
數(shù)組中兩個字符串的*小距離（尉 ★★☆☆） 264
添加*少字符使字符串整體都是回文字符串（校 ★★★☆） 267
括號字符串的有效性和*長有效長度（原問題 士 ★☆☆☆）
（補(bǔ)充問題 尉 ★★☆☆） 271
公式字符串求值（校 ★★★☆） 274
0左邊必有1的二進(jìn)制字符串?dāng)?shù)量（校 ★★★☆） 276
拼接所有字符串產(chǎn)生字典順序*小的大寫字符串（校 ★★★☆） 279
找到字符串的*長無重復(fù)字符子串（尉 ★★☆☆） 282
找到被指的新類型字符（士 ★☆☆☆） 284
*小包含子串的長度（校 ★★★☆） 286
回文*少分割數(shù)（尉 ★★★☆） 290
字符串匹配問題（校 ★★★☆） 292
字典樹（前綴樹）的實現(xiàn)（尉 ★★☆☆） 297
第6章 大數(shù)據(jù)和空間限制 301
認(rèn)識布隆過濾器（尉 ★★☆☆） 301
只用2GB內(nèi)存在20億個整數(shù)中找到出現(xiàn)次數(shù)*多的數(shù)（士 ★☆☆☆） 306
40億個非負(fù)整數(shù)中找到?jīng)]出現(xiàn)的數(shù)（尉 ★★☆☆） 307
找到100億個URL中重復(fù)的URL以及搜索詞匯的top K問題（士 ★☆☆☆） 309
40億個非負(fù)整數(shù)中找到出現(xiàn)了兩次的數(shù)和所有數(shù)的中位數(shù)（尉 ★★☆☆） 310
一致性哈希算法的基本原理（尉 ★★☆☆） 311
第7章 位運算 315
不用額外變量交換兩個整數(shù)的值（士 ★☆☆☆） 315
不用任何比較判斷找出兩個數(shù)中較大的數(shù)（校 ★★★☆） 316
只用位運算不用算術(shù)運算實現(xiàn)整數(shù)的加減乘除運算（尉 ★★☆☆） 317
整數(shù)的二進(jìn)制表達(dá)中有多少個1（尉 ★★☆☆） 323
在其他數(shù)都出現(xiàn)偶數(shù)次的數(shù)組中找到出現(xiàn)奇數(shù)次的數(shù)（尉 ★★☆☆） 325
在其他數(shù)都出現(xiàn)k次的數(shù)組中找到只出現(xiàn)一次的數(shù)（尉 ★★☆☆） 327
第8章 數(shù)組和矩陣問題 329
轉(zhuǎn)圈打印矩陣（士 ★☆☆☆） 329
將正方形矩陣順時針轉(zhuǎn)動90°（士 ★☆☆☆） 331
“之”字形打印矩陣（士 ★☆☆☆） 333
找到無序數(shù)組中*小的k個數(shù)（O(N*logK)的方法 尉 ★★☆☆）
（O(N)的方法 將 ★★★★） 334
需要排序的*短子數(shù)組長度（士 ★☆☆☆） 340
在數(shù)組中找到出現(xiàn)次數(shù)大于N/K的數(shù)（校 ★★★☆） 341
在行列都排好序的矩陣中找數(shù)（士 ★☆☆☆） 345
*長的可整合子數(shù)組的長度（尉 ★★☆☆） 347
不重復(fù)打印排序數(shù)組中相加和為給定值的所有二元組和三元組（尉 ★★☆☆） 349
未排序正數(shù)數(shù)組中累加和為給定值的*長子數(shù)組長度（尉 ★★☆☆） 352
未排序數(shù)組中累加和為給定值的*長子數(shù)組系列問題（尉 ★★☆☆） 353
未排序數(shù)組中累加和小于或等于給定值的*長子數(shù)組長度（校 ★★★☆） 356
計算數(shù)組的小和（校 ★★★☆） 359
自然數(shù)數(shù)組的排序（士 ★☆☆☆） 362
奇數(shù)下標(biāo)都是奇數(shù)或者偶數(shù)下標(biāo)都是偶數(shù)（士 ★☆☆☆） 364
子數(shù)組的**累加和問題（士 ★☆☆☆） 365
子矩陣的**累加和問題（尉 ★★☆☆） 366
在數(shù)組中找到一個局部*小的位置（尉 ★★☆☆） 369
數(shù)組中子數(shù)組的**累乘積（尉 ★★☆☆） 371
打印N個數(shù)組整體**的Top K（尉 ★★☆☆） 372
邊界都是1的**正方形大?。ㄎ?★★☆☆） 375
不包含本位置值的累乘數(shù)組（士 ★☆☆☆） 378
數(shù)組的partition調(diào)整（士 ★☆☆☆） 380
求*短通路值（尉 ★★☆☆） 382
數(shù)組中未出現(xiàn)的*小正整數(shù)（尉 ★★☆☆） 384
數(shù)組排序之后相鄰數(shù)的**差值（尉 ★★☆☆） 386

第9章 其他題目 388
從5隨機(jī)到7隨機(jī)及其擴(kuò)展（原問題 尉 ★★☆☆ 補(bǔ)充問題 尉 ★★☆☆）
（進(jìn)階問題 校 ★★★☆） 388
一行代碼求兩個數(shù)的**公約數(shù)（士 ★★☆☆） 392
有關(guān)階乘的兩個問題（原問題 尉 ★★☆☆ 進(jìn)階問題 校 ★★★☆） 393
判斷一個點是否在矩形內(nèi)部（尉 ★★☆☆） 396
判斷一個點是否在三角形內(nèi)部（尉 ★★☆☆） 397
折紙問題（尉 ★★☆☆） 400
蓄水池算法（尉 ★★☆☆） 402
設(shè)計有setAll功能的哈希表（士 ★☆☆☆） 404
**的leftMax與rightMax之差的**值（校 ★★★☆） 406
設(shè)計可以