算法问题实战策略

出版日期:2015-2
ISBN:9787115384622
作者:[韩] 具宗万
页数:748页

内容概要

具宗万
毕业于韩国延世大学计算机科学系,曾在innotive公司和NHN公司任软件工程师,现在芝加哥高频交易(HFT)公司从事算法交易开发工作。2007年开始参与运营韩国程序设计竞赛参赛者网络社交平台algospot (http://algospot.com)。
获奖经历
•2002年、2003年 韩国大学生程序设计竞赛 金奖
•2003年、2004年 世界大学生程序设计竞赛 入围决赛
•2004年、2006年、2008年 Google Code Jam 入围决赛
•2007年 Top Coder Open 亚军,2006年 入围决赛
•2008年、2009年 Java算法竞赛 冠军

书籍目录

第一部分 开始解决问题
第1 章 解决问题与程序设计竞赛  4
1.1 引言  4
1.2 程序设计竞赛  4
1.3 阅读本书的方法  7
1.4 值得参加的程序设计竞赛  8
1.5 对赛前准备工作的一些建议  9
1.6 续读  12
第2 章 解决问题概述  13
2.1 引言  13
2.2 解决问题的过程  13
2.3 解决问题的策略  17
2.4 续读  26
第3 章 编码与调试  27
3.1 引言:不要忽视编码的重要性  27
3.2 编写优秀代码的原则  27
3.3 常见失误  32
3.4 调试与测试  39
3.5 变量的取值范围  42
3.6 理解实数型数据类型  46
3.7 续读  55
第二部分 算法分析
第4 章 分析算法的时间复杂度  60
4.1 引言  60
4.2 线性时间算法  62
4.3 次线性时间算法  65
4.4 指数时间算法  67
4.5 时间复杂度  70
4.6 推测执行时间  76
4.7 计算复杂度类:P、NP、NP-完备  81
4.8 续读  84
第5 章 算法正确性证明  85
5.1 引言  85
5.2 数学归纳法和循环不变式  86
5.3 归谬法  90
5.4 其他技巧  92
5.5 续读  95
第三部分 算法设计范式
第6 章 暴力解决法  99
6.1 引言  99
6.2 递归调用和穷举搜索法  100
6.3 练习题:郊游(习题 ID:PICNIC,难度:低)  106
6.4 解题:郊游  107
6.5 练习题:盖游戏板(习题 ID:BOARDCOVER,难度:低)  109
6.6 解题:盖游戏板  111
6.7 优化问题  113
6.8 练习题:时钟同步(习题 ID:CLOCKSYNC,难度:中)  116
6.9 解题:时钟同步  117
6.10 常见穷举搜索类型  119
第7 章 分治法  120
7.1 引言  120
7.2 练习题:四叉树问题(题目 ID:QUADTREE,难度:低)   130
7.3 解题:四叉树问题  131
7.4 练习题:切割篱笆(习题 ID:FENCE,难度:中)  134
7.5 解题:切割篱笆  135
7.6 练习题:粉丝见面会(题目 ID:FANMEETING,难度:高)  139
7.7 解题:粉丝见面会  141
第8 章 动态规划法  143
8.1 引言  143
8.2 练习题:通配符(习题 ID:WILDCARD,难度:中)   151
8.3 解题:通配符  152
8.4 典型优化问题  156
8.5 练习题:合并LIS(题目 ID:JLIS,难度:低)  163
8.6 解题:合并LIS  164
8.7 练习题:背诵圆周率(题目 ID:PI,难度:低)   166
8.8 解题:背诵圆周率  167
8.9 练习题:Quantization(题目 ID:QUANTIZE,难度:中)   169
8.10 解题:Quantization   170
8.11 所有可能的个数与概率  174
8.12 练习题:非对称铺设(题目 ID:ASYMTILING,难度:低)  180
8.13 解题:非对称铺设  181
8.14 练习题:多联骨牌(题目 ID:POLY,难度:中)  183
8.15 解题:多联骨牌  185
8.16 练习题:逃狱的韩尼拔博士(题目 ID:NUMB3RS,难度:中)  187
8.17 解题:逃狱的韩尼拔博士  189
第9 章 动态规划技巧  194
9.1 计算优化问题的实际答案  194
9.2 练习题:打包行李(题目 ID:PACKING,难度:中)  195
9.3 解题:打包行李   197
9.4 练习题:光学字符识别(题目 ID:OCR,难度:高)   199
9.5 解题:光学字符识别   201
9.6 计算第k个答案   204
9.7 练习题:第k个最大递增子序列(题目 ID:KLIS,难度:高)  209
9.8 解题:第k个最长递增子序列   210
9.9 练习题:龙曲线(题目 ID:DRAGON,难度:中)  214
9.10 解题:龙曲线   216
9.11 对非整数型输入的制表   219
9.12 练习题:韦布巴津(题目 ID:ZIMBABWE,难度:高)   224
9.13 解题:韦布巴津   225
9.14 练习题:恢复实验数据(题目 ID:RESTORE,难度:中)  230
9.15 解题:恢复实验数据   231
9.16 组合游戏   234
9.17 练习题:数字游戏(题目 ID:NUMBERGAME,难度:低)  239
9.18 解题:数字游戏   240
9.19 练习题:方块游戏(题目 ID:BLOCKGAME,难度:中)   242
9.20 解题:方块游戏   243
9.21 迭代动态规划法   245
9.22 练习题:回转寿司(题目 ID:SUSHI,难度:中)  249
9.23 解题:回转寿司   250
9.24 练习题:Genius(题目 ID:GENIUS,难度:中)  253
9.25 解题:Genius  254
9.26 续读   256
第10 章 贪心法   257
10.1 引言   257
10.2 练习题:加热便当(题目 ID:LUNCHBOX,难度:低)  264
10.3 解题:加热便当   265
10.4 练习题:合并字符串(题目 ID:STRJOIN,难度:中)  268
10.5 解题:合并字符串  269
10.6 练习题:米那斯雅诺(题目 ID:MINASTIRITH,难度:高)  273
10.7 解题:米那斯雅诺  275
第11 章 组合搜索  281
11.1 引言  281
11.2 组合搜索的方法  283
11.3 练习题:盖游戏板2(题目 ID:BOARDCOVER2,难度:低)  298
11.4 解题:盖游戏板2   299
11.5 练习题:患有严重过敏症的朋友们(题目 ID:ALLERGY,难度:中)  303
11.6 解题:患有严重过敏症的朋友们........304
11.7 练习题:数谜(题目 ID:KAKURO2,难度:中)  307
11.8 解题:数谜  309
11.9 续读  315
第12 章 将优化问题转换为决策问题求解  316
12.1 引言  316
12.2 练习题:南极基地(题目 ID:ARCTIC,难度:低)   320
12.3 解题:南极基地  321
12.4 练习题:加拿大旅行(题目 ID:CANADATRIP,难度:中)  323
12.5 解题:加拿大旅行  324
12.6 练习题:退选课程(题目 ID:WITHDRAWAL,难度:高)  326
12.7 解题:退选课程  327
第四部分 一些著名的算法
第13 章 数值分析  331
13.1 引言  331
13.2 二分法  331
13.3 练习题:提高获胜率(题目 ID:RATIO,难度:低)   338
13.4 解题:提高获胜率  339
13.5 三叉搜索  341
13.6 练习题:花粉化石(题目 ID:FOSSIL,难度:高)   346
13.7 解题:花粉化石  347
13.8 其他主题  351
第14 章 整数论  352
14.1 引言  352
14.2 素数  352
14.3 练习题:密码486(题目 ID:PASS486,难度:中)  357
14.4 解题:密码486   357
14.5 欧几里得算法  360
14.6 练习题:魔法药水(题目 ID:POTION,难度:中)  361
14.7 解题:魔法药水  362
14.8 模运算  364
14.9 续读  366
第15 章 计算几何  367
15.1 引言  367
15.2 计算几何的工具  367
15.3 相交、距离、面积  373
15.4 练习题:弹球模拟(题目 ID:PINBALL,难度:高)  377
15.5 解题:弹球模拟  379
15.6 多边形  383
15.7 练习题:金银岛(题目 ID:TREASURE,难度:高)   386
15.8 解题:金银岛  387
15.9 练习题:是呆子?不是呆子?(题目ID:NERDS,难度:中)   390
15.10 解题:是呆子?不是呆子?  392
15.11 计算几何算法设计范式  396
15.12 常见失误与注意事项  403
15.13 续读  404
第五部分 基本数据结构
第16 章 位掩码  410
16.1 引言  410
16.2 利用位掩码实现集合  413
16.3 位掩码应用示例  417
16.4 练习题:毕业学期(题目 ID:GRADUATION,难度:中)   420
16.5 解题:毕业学期  422
16.6 续读  424
第17 章 部分和  425
17.1 引言  425
17.2 练习题:圣诞娃娃(题目 ID:CHRISTMAS,难度:中)  429
17.3 解题:圣诞娃娃  430
17.4 其他学习内容  432
第18 章 线性数据结构  433
18.1 引言  433
18.2 动态数组  433
18.3 链表  437
18.4 动态数组和链表的比较  440
18.5 练习题:约瑟夫斯(题目 ID:JOSEPHUS,难度:低)   440
18.6 解题:约瑟夫斯  441
18.7 续读  442
第19 章 队列、栈以及双端队列  443
19.1 引言  443
19.2 队列、栈以及双端队列的实现方法  444
19.3 队列与栈的应用  445
19.4 练习题:不匹配括号(题目 ID:BRACKETS2,难度:低)  448
19.5 解题:不匹配括号  449
19.6 练习题:分析外星信号(题目 ID:ITES,难度:中)  450
19.7 解题:分析外星信号  451
第20 章 字符串  455
20.1 引言  455
20.2 字符串检索   456
20.3 练习题:宰河的保险箱(题目 ID:JAEHASAFE,难度:中)  466
20.4 解题:宰河的保险箱   467
20.5 后缀数组   468
20.6 练习题:口头禅(题目 ID:HABIT,难度:中)   476
20.7 解题:口头禅   477
20.8 续读   478
第六部分 树
第21 章 树的实现与遍历   481
21.1 引言   481
21.2 树的遍历   483
21.3 练习题:变更树的遍历顺序(题目 ID:TRAVERSAL,难度:低)  484
21.4 解题:变更树的遍历顺序   486
21.5 练习题:要塞(题目 ID:FORTRESS,难度:中)   487
21.6 解题:要塞   488
第22 章 二叉搜索树   493
22.1 引言   493
22.2 二叉搜索树的定义和操作   493
22.3 时间复杂度分析与平衡二叉搜索树  496
22.4 练习题:是呆子?不是呆子?2(题目ID:NERD2,难度:中)  496
22.5 解题:是呆子?不是呆子?2  498
22.6 直接实现平衡二叉搜索树:树堆  501
22.7 练习题:反转插入排序(题目 ID:INSERTION,难度:中)  508
22.8 解题:反转插入排序   509
第23 章 优先级队列和堆   511
23.1 引言   511
23.2 堆的定义与实现方法   512
23.3 练习题:变化的中间值(题目 ID:RUNNINGMEDIAN,难度:低)  518
23.4 解题:变化的中间值   519
第24 章 区间树  521
24.1 区间树:区间相关问题解答  521
24.2 练习题:登山路(题目 ID:MORDDR,难度:中)   527
24.3 解题:登山路  528
24.4 练习题:寻根问祖(题目 ID:FAMILYTREE,难度:高)  529
24.5 解题:寻根问祖  530
24.6 树状数组:快速而简单的区间和  533
24.7 练习题:计算插入排序的时间(题目 ID:MEASURETIME,难度:中)   536
24.8 解题:计算插入排序的时间  537
第25 章 互斥集合  541
25.1 引言  541
25.2 练习题:编辑器之争(题目 ID:EDITORWARS,难度:中)  546
25.3 解题:编辑器之争  548
第26 章 字典树  553
26.1 引言  553
26.2 练习题:再见,谢谢所有的鱼(题目 ID:SOLONG,难度:中)  557
26.3 解题:再见,谢谢所有的鱼  559
26.4 利用字典树检索多重字符串  563
26.5 练习题:安全终结者(题目 ID:NH,难度:高)  569
26.6 解题:安全终结者  570
第七部分 图
第27 章 图的表示方式及定义  576
27.1 引言  576
27.2 图的应用示例  579
27.3 隐式图结构  580
27.4 图的几种表示法  581
第28 章 图的深度优先搜索  585
28.1 引言  585
28.2 练习题:古语词典(习题 ID:DICTIONARY,难度:低)  590
28.3 解题:古语词典  591
28.4 欧拉回路  594
28.5 练习题:有限单词接龙(题目 ID:WORDCHAIN,难度:低)   597
28.6 解题:有限单词接龙  598
28.7 理论背景及应用  602
28.8 练习题:安装监控摄像头(题目 ID:GALLERY,难度:中)  613
28.9 解题:安装监控摄像头  614
28.10 练习题:安排会议室(题目 ID:MEETINGROOM,难度:高)  616
28.11 解题:安排会议室  618
第29 章 图的宽度优先搜索  625
29.1 引言  625
29.2 练习题:排序游戏(题目 ID:SORTGAME,难度:中)  629
29.3 解题:排序游戏  630
29.4 练习题:儿童节(题目 ID:CHILDRENDAY,难度:高)  633
29.5 解题:儿童节  634
29.6 最短路径策略  637
29.7 练习题:汉诺塔(题目 ID:HANOI4B,难度:中)   648
29.8 解题:汉诺塔  650
第30 章 最短路径问题  653
30.1 引言  653
30.2 迪杰斯特拉最短路径算法  654
30.3 练习题:信号路由(题目 ID:ROUTING,难度:低)  661
30.4 解题:信号路由  662
30.5 练习题:消防车(题目 ID:FIRETRUCKS,难度:中)  663
30.6 解题:消防车  664
30.7 练习题:铁人N项比赛(题目 ID:NTHLON,难度:高)   665
30.8 解题:铁人N项比赛  667
30.9 贝尔曼-福特最短路径算法  669
30.10 练习题:时间旅行(题目 ID:TIMETRIP,难度:中)   674
30.11 解题:时间旅行  675
30.12 弗洛伊德多源最短路径算法  677
30.13 练习题:检查酒驾(题目 ID:DRUNKEN,难度:中)   682
30.14 解题:检查酒驾  684
30.15 练习题:竞选承诺(题目 ID:PROMISES,难度:中)   685
30.16 解题:竞选承诺  687
第31 章 最小生成树  689
31.1 引言  689
31.2 克鲁斯克尔最小生成树算法  690
31.3 普里姆最小生成树算法  694
31.4 练习题:局域网(题目 ID:LAN,难度:低)  697
31.5 解题:局域网  698
31.6 练习题:选定旅行路线(题目 ID:TPATH,难度:高)   699
31.7 解题:选定旅行路线   700
第32 章 网络流   705
32.1 引言   705
32.2 福特-富尔克森算法   706
32.3 网络建模   713
32.4 练习题:操纵比赛(题目 ID:MATCHFIX,难度:中)  715
32.5 解题:操纵比赛   717
32.6 练习题:国家项目(题目 ID:PROJECTS,难度:高)  719
32.7 解题:国家项目   720
32.8 二分图匹配   723
32.9 练习题:象(题目 ID:BISHOPS,难度:中)  729
32.10 解题:象   730
32.11 练习题:设置陷阱(题目 ID:TRAPCARD,难度:高)  732
32.12 解题:设置陷阱   734
32.13 其他学习内容   737

作者简介

第一部分 开始解决问题
第二部分 算法分析
第三部分 算法设计范式
第四部分 一些著名的算法
第五部分 基本数据结构
第六部分 树
第七部分 图


 算法问题实战策略下载



发布书评

 
 


精彩短评 (总计4条)

  •     代码质量很高,可与算法导论对照着看。难度低于日本那本《挑战程序设计竞赛》
  •     东拉西扯大杂烩泡菜风格。大学acm刷题可以买。不然同样的钱还是买《算法》那本划算。
  •     C++代码不错
  •     写的很一般 不是因为算法课老师出期末试卷会从里头出题 还真的不会看这本书
 

外国儿童文学,篆刻,百科,生物科学,科普,初中通用,育儿亲子,美容护肤PDF图书下载,。 零度图书网 

零度图书网 @ 2024