Java常用算法手冊（含盤）

第1篇  算法基礎篇
第1章  算法和實現(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  時間復雜度 8
1.4.2  空間復雜度 8
1.5  一個算法實例 8
1.5.1  查找數(shù)字 9
1.5.2  創(chuà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  編程實例 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  編程實例 25
1.10  跳轉(zhuǎn)結(jié)構(gòu) 29
1.10.1  break 29
1.10.2  continue 29
1.10.3  編程實例 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)解決實際問題 38
2.2  線性表 38
2.2.1  什么是線性表 38
2.2.2  線性表的基本運算 39
2.3  順序表結(jié)構(gòu) 40
2.3.1  準備數(shù)據(jù) 40
2.3.2  初始化順序表 41
2.3.3  計算順序表長度 41
2.3.4  插入結(jié)點 41
2.3.5  追加結(jié)點 42
2.3.6  刪除結(jié)點 42
2.3.7  查找結(jié)點 43
2.3.8  顯示所有結(jié)點 43
2.3.9  順序表操作實例 44
2.4  鏈表結(jié)構(gòu) 48
2.4.1  什么是鏈表結(jié)構(gòu) 48
2.4.2  準備數(shù)據(jù) 49
2.4.3  追加結(jié)點 49
2.4.4  插入頭結(jié)點 50
2.4.5  查找結(jié)點 51
2.4.6  插入結(jié)點 52
2.4.7  刪除結(jié)點 52
2.4.8  計算鏈表長度 53
2.4.9  顯示所有結(jié)點 54
2.4.10  鏈表操作實例 54
2.5  棧結(jié)構(gòu) 59
2.5.1  什么是棧結(jié)構(gòu) 59
2.5.2  準備數(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é)點數(shù)據(jù) 63
2.5.11  棧結(jié)構(gòu)操作實例 63
2.6  隊列結(jié)構(gòu) 66
2.6.1  什么是隊列結(jié)構(gòu) 66
2.6.2  準備數(shù)據(jù) 67
2.6.3  初始化隊列結(jié)構(gòu) 68
2.6.4  判斷空隊列 68
2.6.5  判斷滿隊列 68
2.6.6  清空隊列 69
2.6.7  釋放空間 69
2.6.8  入隊列 69
2.6.9  出隊列 70
2.6.10  讀結(jié)點數(shù)據(jù) 70
2.6.11  計算隊列長度 71
2.6.12  隊列結(jié)構(gòu)操作實例 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  準備數(shù)據(jù) 79
2.7.5  初始化二叉樹 80
2.7.6  添加結(jié)點 80
2.7.7  查找結(jié)點 82
2.7.8  獲取左子樹 82
2.7.9  獲取右子樹 83
2.7.10  判斷空樹 83
2.7.11  計算二叉樹深度 84
2.7.12  清空二叉樹 84
2.7.13  顯示結(jié)點數(shù)據(jù) 84
2.7.14  遍歷二叉樹 85
2.7.15  樹結(jié)構(gòu)操作實例 87
2.8  圖結(jié)構(gòu) 94
2.8.1  什么是圖結(jié)構(gòu) 94
2.8.2  圖的基本概念 94
2.8.3  準備數(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)操作實例 103
2.9  小結(jié) 106
第3章  基本算法思想
3.1  常用算法思想概述 107
3.2  窮舉算法思想 107
3.2.1  窮舉算法基本思想 108
3.2.2  窮舉算法實例 108
3.3  遞推算法思想 109
3.3.1  遞推算法基本思想 110
3.3.2  遞推算法實例 110
3.4  遞歸算法思想 111
3.4.1  遞歸算法基本思想 112
3.4.2  遞歸算法實例 112
3.5  分治算法思想 113
3.5.1  分治算法基本思想 113
3.5.2  分治算法實例 114
3.6  概率算法思想 117
3.6.1  概率算法基本思想 118
3.6.2  概率算法實例 118
3.7  小結(jié) 120
第2篇  算法應用篇 
第4章  排序算法
4.1  排序算法概述 121
4.2  冒泡排序法 122
4.2.1  冒泡排序算法 122
4.2.2  冒泡排序算法實例 123
4.3  選擇排序法 125
4.3.1  選擇排序算法 125
4.3.2  選擇排序算法實例 126
4.4  插入排序法 128
4.4.1  插入排序算法 128
4.4.2  插入排序算法實例 130
4.5  Shell排序法 131
4.5.1  Shell排序算法 131
4.5.2  Shell排序算法實例 132
4.6  快速排序法 134
4.6.1  快速排序算法 134
4.6.2  快速排序算法實例 136
4.7  堆 排 序 法 138
4.7.1  堆排序算法 138
4.7.2  堆排序算法實例 142
4.8  合并排序法 144
4.8.1  合并排序算法 145
4.8.2  合并排序算法實例 147
4.9  排序算法的效率 150
4.10  排序算法的其他應用 151
4.10.1  反序排序 151
4.10.2  字符串數(shù)組的排序 153
4.10.3  字符串的排序 156
4.11  小結(jié) 158
第5章  查找算法
5.1  查找算法概述 159
5.2  順序查找 160
5.2.1  順序查找算法 160
5.2.2  順序查找操作實例 160
5.3  折半查找 162
5.3.1  折半查找算法 162
5.3.2  折半查找操作實例 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ù)學問題
6.1  判斷閏年 176
6.2  多項式計算 178
6.2.1  一維多項式求值 178
6.2.2  二維多項式求值 180
6.2.3  多項式乘法 182
6.2.4  多項式除法 183
6.3  隨機數(shù)生成算法 186
6.3.1  Java語言中的隨機方法 186
6.3.2  [0，1]之間均勻分布的隨機數(shù)算法 188
6.3.3  產(chǎn)生任意范圍的隨機數(shù) 189
6.3.4  [m，n]之間均勻分布的隨機整數(shù)算法 190
6.3.5  正態(tài)分布的隨機數(shù)生成算法 192
6.4  復數(shù)運算 193
6.4.1  簡單的復數(shù)運算 194
6.4.2  復數(shù)的冪運算 196
6.4.3  復指數(shù)運算 197
6.4.4  復對數(shù)運算 199
6.4.5  復正弦運算 200
6.4.6  復余弦運算 201
6.5  階乘 202
6.5.1  使用循環(huán)來計算階乘 202
6.5.2  使用遞歸來計算階乘 203
6.6  計算π的近似值 204
6.6.1  割圓術(shù) 205
6.6.2  蒙特卡羅算法 207
6.6.3  級數(shù)公式 210
6.7  矩陣運算 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  復雜約瑟夫環(huán)算法 235
7.2.4  復雜約瑟夫環(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  計算完全數(shù)算法 263
8.3  親密數(shù) 265
8.3.1  什么是親密數(shù) 265
8.3.2  計算親密數(shù)算法 266
8.4  水仙花數(shù) 269
8.4.1  什么是水仙花數(shù) 269
8.4.2  計算水仙花數(shù)算法 270
8.5  自守數(shù) 272
8.5.1  什么是自守數(shù) 272
8.5.2  計算自守數(shù)算法 273
8.6  最大公約數(shù) 276
8.6.1  計算最大公約數(shù)算法——輾轉(zhuǎn)相除法 277
8.6.2  計算最大公約數(shù)算法——Stein算法 277
8.6.3  計算最大公約數(shù)示例 279
8.7  最小公倍數(shù) 280
8.8  素數(shù) 282
8.8.1  什么是素數(shù) 282
8.8.2  計算素數(shù)算法 282
8.9  回文素數(shù) 284
8.9.1  什么是回文素數(shù) 284
8.9.2  計算回文素數(shù)算法 284
8.10  平方回文數(shù) 287
8.10.1  什么是平方回文數(shù) 287
8.10.2  計算平方回文數(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  洗撲克牌實例 349
10.2  取火柴游戲算法 352
10.2.1  取火柴游戲算法 352
10.2.2  取火柴游戲?qū)嵗?nbsp;353
10.3  10點半算法 355
10.3.1  10點半算法 355
10.3.2  10點半游戲?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章  密碼學概述
11.1  密碼學概述 377
11.1.1  密碼學的發(fā)展 377
11.1.2  密碼學的基本概念 378
11.1.3  柯克霍夫斯原則 379
11.1.4  經(jīng)典密碼學算法 379
11.2  換位加密解密算法 380
11.2.1  換位加密解密算法 380
11.2.2  換位加密解密算法實例 383
11.3  替換加密解密算法 387
11.3.1  替換加密解密算法 387
11.3.2  替換加密解密算法實例 388
11.4  位加密解密算法 390
11.4.1  位加密解密算法 390
11.4.2  位加密解密算法實例 392
11.5  一次一密加密解密算法 393
11.5.1  一次一密加密解密算法 394
11.5.2  一次一密加密解密算法實例 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  壓縮解壓縮實例 405
12.5  小結(jié) 413
第3篇  算法面試篇
第13章  數(shù)學能力測試
13.1  100盞燈 414
13.2  找出不同的球 415
13.3  用一筆劃出經(jīng)過九個點的
4條直線 416
13.4  在9個點上畫10條線 417
13.5  時、分和秒針重合問題 417
13.6  可以喝多少瓶汽水 420
13.7  怎樣拿到第100號球 421
13.8  燒繩計時 422
第14章  算法面試題
14.1  基礎算法 424
14.1.1  字符串匹配 424
14.1.2  哥德巴赫猜想的近似證明 427
14.1.3  將一個正整數(shù)分解質(zhì)因數(shù) 429
14.1.4  怎樣實現(xiàn)金額轉(zhuǎn)換 431
14.1.5  數(shù)字排列 436
14.1.6  數(shù)字拆解 438
14.1.7  數(shù)字組合 440
14.2  思維擴展算法 443
14.2.1  蛇形打印 443
14.2.2  24點算法 445
14.2.3  雙色球隨機搖號 450
14.2.4  巧妙過橋 453
14.2.5  猴子吃桃 457
14.2.6  天平稱物 458
14.2.7  擲骰子游戲 460
14.3  小結(jié) 463