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

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