Java常用算法手冊（含盤）

第1篇  算法基礎(chǔ)篇
第1章  算法和實(shí)現(xiàn)算法的Java語法
1.1  建立算法初步概念 1
1.1.1  什么是算法 1
1.1.2  算法的發(fā)展歷史 3
1.1.3  算法的分類 3
1.2  算法相關(guān)概念的區(qū)別 3
1.2.1  算法與公式的關(guān)系 4
1.2.2  算法與程序的關(guān)系 4
1.2.3  算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系 4
1.3  算法的表示 5
1.3.1  自然語言表示 5
1.3.2  流程圖表示 5
1.3.3  N-S圖表示 6
1.3.4  偽代碼表示 7
1.4  算法的性能評價 8
1.4.1  時間復(fù)雜度 8
1.4.2  空間復(fù)雜度 8
1.5  一個算法實(shí)例 8
1.5.1  查找數(shù)字 9
1.5.2  創(chuàng)建項(xiàng)目 10
1.5.3  編譯執(zhí)行 12
1.6  Java程序的基本結(jié)構(gòu) 13
1.6.1  類是一個基本單元 14
1.6.2  main方法 15
1.6.3  自定義方法 15
1.6.4  System.out.println的使用 16
1.6.5  一個簡單而完整的程序 16
1.7  順序結(jié)構(gòu) 17
1.8  分支結(jié)構(gòu) 18
1.8.1  if...else分支結(jié)構(gòu) 18
1.8.2  if...else嵌套 19
1.8.3  switch語句 20
1.8.4  編程實(shí)例 21
1.9  循環(huán)結(jié)構(gòu) 22
1.9.1  while循環(huán) 23
1.9.2  do…while循環(huán) 24
1.9.3  for循環(huán) 24
1.9.4  編程實(shí)例 25
1.10  跳轉(zhuǎn)結(jié)構(gòu) 29
1.10.1  break 29
1.10.2  continue 29
1.10.3  編程實(shí)例 29
1.11  小結(jié) 31
第2章  數(shù)據(jù)結(jié)構(gòu)
2.1  數(shù)據(jù)結(jié)構(gòu)概述 32
2.1.1  什么是數(shù)據(jù)結(jié)構(gòu) 32
2.1.2  數(shù)據(jù)結(jié)構(gòu)中的基本概念 33
2.1.3  數(shù)據(jù)結(jié)構(gòu)的內(nèi)容 33
2.1.4  數(shù)據(jù)結(jié)構(gòu)的分類 35
2.1.5  數(shù)據(jù)結(jié)構(gòu)的幾種存儲方式 35
2.1.6  數(shù)據(jù)類型 36
2.1.7  常用的數(shù)據(jù)結(jié)構(gòu) 37
2.1.8  選擇合適的數(shù)據(jù)結(jié)構(gòu)解決實(shí)際問題 38
2.2  線性表 38
2.2.1  什么是線性表 38
2.2.2  線性表的基本運(yùn)算 39
2.3  順序表結(jié)構(gòu) 40
2.3.1  準(zhǔn)備數(shù)據(jù) 40
2.3.2  初始化順序表 41
2.3.3  計(jì)算順序表長度 41
2.3.4  插入結(jié)點(diǎn) 41
2.3.5  追加結(jié)點(diǎn) 42
2.3.6  刪除結(jié)點(diǎn) 42
2.3.7  查找結(jié)點(diǎn) 43
2.3.8  顯示所有結(jié)點(diǎn) 43
2.3.9  順序表操作實(shí)例 44
2.4  鏈表結(jié)構(gòu) 48
2.4.1  什么是鏈表結(jié)構(gòu) 48
2.4.2  準(zhǔn)備數(shù)據(jù) 49
2.4.3  追加結(jié)點(diǎn) 49
2.4.4  插入頭結(jié)點(diǎn) 50
2.4.5  查找結(jié)點(diǎn) 51
2.4.6  插入結(jié)點(diǎn) 52
2.4.7  刪除結(jié)點(diǎn) 52
2.4.8  計(jì)算鏈表長度 53
2.4.9  顯示所有結(jié)點(diǎn) 54
2.4.10  鏈表操作實(shí)例 54
2.5  棧結(jié)構(gòu) 59
2.5.1  什么是棧結(jié)構(gòu) 59
2.5.2  準(zhǔn)備數(shù)據(jù) 60
2.5.3  初始化棧結(jié)構(gòu) 60
2.5.4  判斷空棧 61
2.5.5  判斷滿棧 61
2.5.6  清空棧 61
2.5.7  釋放空間 62
2.5.8  入棧 62
2.5.9  出棧 62
2.5.10  讀結(jié)點(diǎn)數(shù)據(jù) 63
2.5.11  棧結(jié)構(gòu)操作實(shí)例 63
2.6  隊(duì)列結(jié)構(gòu) 66
2.6.1  什么是隊(duì)列結(jié)構(gòu) 66
2.6.2  準(zhǔn)備數(shù)據(jù) 67
2.6.3  初始化隊(duì)列結(jié)構(gòu) 68
2.6.4  判斷空隊(duì)列 68
2.6.5  判斷滿隊(duì)列 68
2.6.6  清空隊(duì)列 69
2.6.7  釋放空間 69
2.6.8  入隊(duì)列 69
2.6.9  出隊(duì)列 70
2.6.10  讀結(jié)點(diǎn)數(shù)據(jù) 70
2.6.11  計(jì)算隊(duì)列長度 71
2.6.12  隊(duì)列結(jié)構(gòu)操作實(shí)例 71
2.7  樹結(jié)構(gòu) 75
2.7.1  什么是樹結(jié)構(gòu) 75
2.7.2  樹的基本概念 75
2.7.3  二叉樹 76
2.7.4  準(zhǔn)備數(shù)據(jù) 79
2.7.5  初始化二叉樹 80
2.7.6  添加結(jié)點(diǎn) 80
2.7.7  查找結(jié)點(diǎn) 82
2.7.8  獲取左子樹 82
2.7.9  獲取右子樹 83
2.7.10  判斷空樹 83
2.7.11  計(jì)算二叉樹深度 84
2.7.12  清空二叉樹 84
2.7.13  顯示結(jié)點(diǎn)數(shù)據(jù) 84
2.7.14  遍歷二叉樹 85
2.7.15  樹結(jié)構(gòu)操作實(shí)例 87
2.8  圖結(jié)構(gòu) 94
2.8.1  什么是圖結(jié)構(gòu) 94
2.8.2  圖的基本概念 94
2.8.3  準(zhǔn)備數(shù)據(jù) 98
2.8.4  創(chuàng)建圖 100
2.8.5  清空圖 101
2.8.6  顯示圖 101
2.8.7  遍歷圖 102
2.8.8  圖結(jié)構(gòu)操作實(shí)例 103
2.9  小結(jié) 106
第3章  基本算法思想
3.1  常用算法思想概述 107
3.2  窮舉算法思想 107
3.2.1  窮舉算法基本思想 108
3.2.2  窮舉算法實(shí)例 108
3.3  遞推算法思想 109
3.3.1  遞推算法基本思想 110
3.3.2  遞推算法實(shí)例 110
3.4  遞歸算法思想 111
3.4.1  遞歸算法基本思想 112
3.4.2  遞歸算法實(shí)例 112
3.5  分治算法思想 113
3.5.1  分治算法基本思想 113
3.5.2  分治算法實(shí)例 114
3.6  概率算法思想 117
3.6.1  概率算法基本思想 118
3.6.2  概率算法實(shí)例 118
3.7  小結(jié) 120
第2篇  算法應(yīng)用篇 
第4章  排序算法
4.1  排序算法概述 121
4.2  冒泡排序法 122
4.2.1  冒泡排序算法 122
4.2.2  冒泡排序算法實(shí)例 123
4.3  選擇排序法 125
4.3.1  選擇排序算法 125
4.3.2  選擇排序算法實(shí)例 126
4.4  插入排序法 128
4.4.1  插入排序算法 128
4.4.2  插入排序算法實(shí)例 130
4.5  Shell排序法 131
4.5.1  Shell排序算法 131
4.5.2  Shell排序算法實(shí)例 132
4.6  快速排序法 134
4.6.1  快速排序算法 134
4.6.2  快速排序算法實(shí)例 136
4.7  堆 排 序 法 138
4.7.1  堆排序算法 138
4.7.2  堆排序算法實(shí)例 142
4.8  合并排序法 144
4.8.1  合并排序算法 145
4.8.2  合并排序算法實(shí)例 147
4.9  排序算法的效率 150
4.10  排序算法的其他應(yīng)用 151
4.10.1  反序排序 151
4.10.2  字符串?dāng)?shù)組的排序 153
4.10.3  字符串的排序 156
4.11  小結(jié) 158
第5章  查找算法
5.1  查找算法概述 159
5.2  順序查找 160
5.2.1  順序查找算法 160
5.2.2  順序查找操作實(shí)例 160
5.3  折半查找 162
5.3.1  折半查找算法 162
5.3.2  折半查找操作實(shí)例 164
5.4  數(shù)據(jù)結(jié)構(gòu)中的查找算法 166
5.4.1  順序表結(jié)構(gòu)中的查找算法 167
5.4.2  鏈表結(jié)構(gòu)中的查找算法 170
5.4.3  樹結(jié)構(gòu)中的查找算法 173
5.4.4  圖結(jié)構(gòu)中的查找算法 174
5.5  小結(jié) 175
第6章  基本數(shù)學(xué)問題
6.1  判斷閏年 176
6.2  多項(xiàng)式計(jì)算 178
6.2.1  一維多項(xiàng)式求值 178
6.2.2  二維多項(xiàng)式求值 180
6.2.3  多項(xiàng)式乘法 182
6.2.4  多項(xiàng)式除法 183
6.3  隨機(jī)數(shù)生成算法 186
6.3.1  Java語言中的隨機(jī)方法 186
6.3.2  [0，1]之間均勻分布的隨機(jī)數(shù)算法 188
6.3.3  產(chǎn)生任意范圍的隨機(jī)數(shù) 189
6.3.4  [m，n]之間均勻分布的隨機(jī)整數(shù)算法 190
6.3.5  正態(tài)分布的隨機(jī)數(shù)生成算法 192
6.4  復(fù)數(shù)運(yùn)算 193
6.4.1  簡單的復(fù)數(shù)運(yùn)算 194
6.4.2  復(fù)數(shù)的冪運(yùn)算 196
6.4.3  復(fù)指數(shù)運(yùn)算 197
6.4.4  復(fù)對數(shù)運(yùn)算 199
6.4.5  復(fù)正弦運(yùn)算 200
6.4.6  復(fù)余弦運(yùn)算 201
6.5  階乘 202
6.5.1  使用循環(huán)來計(jì)算階乘 202
6.5.2  使用遞歸來計(jì)算階乘 203
6.6  計(jì)算π的近似值 204
6.6.1  割圓術(shù) 205
6.6.2  蒙特卡羅算法 207
6.6.3  級數(shù)公式 210
6.7  矩陣運(yùn)算 212
6.7.1  矩陣加法 212
6.7.2  矩陣減法 213
6.7.3  矩陣乘法 215
6.8  方程求解 217
6.8.1  線性方程求解——高斯消元法 217
6.8.2  非線性方程求解——二分法 221
6.8.3  非線性方程求解——牛頓迭代法 224
6.9  小結(jié) 227
第7章  數(shù)據(jù)結(jié)構(gòu)問題
7.1  動態(tài)數(shù)組排序 228
7.1.1  動態(tài)數(shù)組的存儲和排序 228
7.1.2  動態(tài)數(shù)組排序?qū)嵗?nbsp;229
7.2  約瑟夫環(huán) 231
7.2.1  簡單約瑟夫環(huán)算法 232
7.2.2  簡單約瑟夫環(huán)求解 233
7.2.3  復(fù)雜約瑟夫環(huán)算法 235
7.2.4  復(fù)雜約瑟夫環(huán)求解 236
7.3  城市之間的最短總距離 239
7.3.1  最短總距離算法 239
7.3.2  最短總距離求解 241
7.4  最短路徑 246
7.4.1  最短路徑算法 246
7.4.2  最短路徑求解 248
7.5  括號匹配 253
7.5.1  括號匹配算法 254
7.5.2  括號匹配求解 255
7.6  小結(jié) 258
第8章  數(shù)論問題
8.1  數(shù)論概述 259
8.1.1  數(shù)論概述 259
8.1.2  數(shù)論的分類 260
8.1.3  初等數(shù)論 261
8.1.4  本章用到的基本概念 261
8.2  完全數(shù) 262
8.2.1  什么是完全數(shù) 262
8.2.2  計(jì)算完全數(shù)算法 263
8.3  親密數(shù) 265
8.3.1  什么是親密數(shù) 265
8.3.2  計(jì)算親密數(shù)算法 266
8.4  水仙花數(shù) 269
8.4.1  什么是水仙花數(shù) 269
8.4.2  計(jì)算水仙花數(shù)算法 270
8.5  自守?cái)?shù) 272
8.5.1  什么是自守?cái)?shù) 272
8.5.2  計(jì)算自守?cái)?shù)算法 273
8.6  最大公約數(shù) 276
8.6.1  計(jì)算最大公約數(shù)算法——輾轉(zhuǎn)相除法 277
8.6.2  計(jì)算最大公約數(shù)算法——Stein算法 277
8.6.3  計(jì)算最大公約數(shù)示例 279
8.7  最小公倍數(shù) 280
8.8  素?cái)?shù) 282
8.8.1  什么是素?cái)?shù) 282
8.8.2  計(jì)算素?cái)?shù)算法 282
8.9  回文素?cái)?shù) 284
8.9.1  什么是回文素?cái)?shù) 284
8.9.2  計(jì)算回文素?cái)?shù)算法 284
8.10  平方回文數(shù) 287
8.10.1  什么是平方回文數(shù) 287
8.10.2  計(jì)算平方回文數(shù)算法 287
8.11  分解質(zhì)因數(shù) 290
8.12  小結(jié) 292
第 9章  算法經(jīng)典趣題
9.1  百錢買百雞 293
9.1.1  百錢買百雞算法 293
9.1.2  百錢買百雞求解 294
9.2  五家共井 295
9.2.1  五家共井算法 295
9.2.2  五家共井求解 296
9.3  雞兔同籠 298
9.3.1  雞兔同籠算法 298
9.3.2  雞兔同籠求解 298
9.4  猴子吃桃 299
9.4.1  猴子吃桃算法 300
9.4.2  猴子吃桃求解 300
9.5  舍罕王賞麥 301
9.5.1  舍罕王賞麥問題 302
9.5.2  舍罕王賞麥求解 302
9.6  漢諾塔 303
9.6.1  漢諾塔算法 304
9.6.2  漢諾塔求解 305
9.7  竊賊問題 307
9.7.1  竊賊問題算法 307
9.7.2  竊賊問題求解 309
9.8  馬踏棋盤 312
9.8.1  馬踏棋盤算法 312
9.8.2  馬踏棋盤求解 314
9.9  八皇后問題 317
9.9.1  八皇后問題算法 317
9.9.2  八皇后問題求解 318
9.10  尋找假銀幣 320
9.10.1  尋找假銀幣算法 320
9.10.2  尋找假銀幣求解 322
9.11  青蛙過河 325
9.11.1  青蛙過河算法 325
9.11.2  青蛙過河求解 326
9.12  三色旗 330
9.12.1  三色旗算法 330
9.12.2  三色旗求解 331
9.13  漁父捕魚 333
9.13.1  漁父捕魚算法 333
9.13.2  漁父捕魚求解 334
9.14  愛因斯坦的階梯 335
9.14.1  愛因斯坦的階梯算法 336
9.14.2  愛因斯坦的階梯求解 336
9.15  兔子產(chǎn)仔 337
9.15.1  兔子產(chǎn)仔算法 337
9.15.2  兔子產(chǎn)仔求解 338
9.16  常勝將軍 339
9.16.1  常勝將軍算法 339
9.16.2  常勝將軍求解 340
9.17  新郎和新娘 342
9.17.1  新郎和新娘算法 342
9.17.2  新郎和新娘求解 343
9.18  三色球 344
9.18.1  三色球算法 345
9.18.2  三色球求解 345
9.19  小結(jié) 347
第10章  游戲中的算法
10.1  洗撲克牌算法 348
10.1.1  洗撲克牌算法 348
10.1.2  洗撲克牌實(shí)例 349
10.2  取火柴游戲算法 352
10.2.1  取火柴游戲算法 352
10.2.2  取火柴游戲?qū)嵗?nbsp;353
10.3  10點(diǎn)半算法 355
10.3.1  10點(diǎn)半算法 355
10.3.2  10點(diǎn)半游戲?qū)嵗?nbsp;361
10.4  生命游戲 368
10.4.1  生命游戲的原理 368
10.4.2  生命游戲的算法 369
10.4.3  生命游戲?qū)嵗?nbsp;371
10.5  小結(jié) 376
第11章  密碼學(xué)概述
11.1  密碼學(xué)概述 377
11.1.1  密碼學(xué)的發(fā)展 377
11.1.2  密碼學(xué)的基本概念 378
11.1.3  柯克霍夫斯原則 379
11.1.4  經(jīng)典密碼學(xué)算法 379
11.2  換位加密解密算法 380
11.2.1  換位加密解密算法 380
11.2.2  換位加密解密算法實(shí)例 383
11.3  替換加密解密算法 387
11.3.1  替換加密解密算法 387
11.3.2  替換加密解密算法實(shí)例 388
11.4  位加密解密算法 390
11.4.1  位加密解密算法 390
11.4.2  位加密解密算法實(shí)例 392
11.5  一次一密加密解密算法 393
11.5.1  一次一密加密解密算法 394
11.5.2  一次一密加密解密算法實(shí)例 395
11.6  小結(jié) 397
第12章  壓縮與解壓縮算法
12.1  壓縮與解壓縮概述 398
12.1.1  壓縮與解壓縮分類 398
12.1.2  典型的壓縮解壓縮算法 398
12.2  壓縮算法 399
12.3  解壓縮算法 402
12.4  壓縮解壓縮實(shí)例 405
12.5  小結(jié) 413
第3篇  算法面試篇
第13章  數(shù)學(xué)能力測試
13.1  100盞燈 414
13.2  找出不同的球 415
13.3  用一筆劃出經(jīng)過九個點(diǎn)的
4條直線 416
13.4  在9個點(diǎn)上畫10條線 417
13.5  時、分和秒針重合問題 417
13.6  可以喝多少瓶汽水 420
13.7  怎樣拿到第100號球 421
13.8  燒繩計(jì)時 422
第14章  算法面試題
14.1  基礎(chǔ)算法 424
14.1.1  字符串匹配 424
14.1.2  哥德巴赫猜想的近似證明 427
14.1.3  將一個正整數(shù)分解質(zhì)因數(shù) 429
14.1.4  怎樣實(shí)現(xiàn)金額轉(zhuǎn)換 431
14.1.5  數(shù)字排列 436
14.1.6  數(shù)字拆解 438
14.1.7  數(shù)字組合 440
14.2  思維擴(kuò)展算法 443
14.2.1  蛇形打印 443
14.2.2  24點(diǎn)算法 445
14.2.3  雙色球隨機(jī)搖號 450
14.2.4  巧妙過橋 453
14.2.5  猴子吃桃 457
14.2.6  天平稱物 458
14.2.7  擲骰子游戲 460
14.3  小結(jié) 463