目录

配套资源

第1章算法和计算思维1

1.1算法基本概念及效率分析1

1.1.1什么是算法1

1.1.2算法设计的基本过程2

1.1.3算法效率分析的基本方法3

1.2算法与计算思维11

第2章分治法13

2.1分治法概述13

2.2分治法中的计算思维15

2.3分治法的实践案例16

2.3.1求第k个数16

2.3.2粉刷问题21

2.3.3棋盘覆盖问题24

2.3.4数组的反转计数27

2.3.5天际线问题32

2.3.6凸包问题36

第3章回溯法45

3.1回溯法概述45

3.2剪枝48

3.3回溯法与寻优问题49

3.4回溯法与分支界限法50

3.5回溯法中的计算思维51

3.6回溯法的实践案例52

3.6.1数独问题52

3.6.2骑士巡游问题55

3.6.3子集划分问题58

3.6.4括号生成问题61

3.6.5地图填色问题62

3.6.6运算表达式优先级66

第4章动态规划68

4.1动态规划概述68

4.2动态规划中的计算思维71

4.3动态规划的实践案例72

4.3.1最长等差子序列72

4.3.2子系列和最大问题74

4.3.3股票获益最大问题76

4.3.4图像编码问题80

4.3.5最长不重叠子串问题83

4.3.6粉刷问题85

4.3.7树的最大高度问题87

4.3.8分割等和子集问题92

4.3.9跳跃问题96

4.3.10最长严格递增子序列100

4.3.11回文串划分问题102

4.3.12括号生成问题110

4.3.13作业调度问题112

第5章贪心法115

5.1贪心法概述115

5.2贪心法中的计算思维117

5.3贪心法的实践案例117

5.3.1最少站台问题117

5.3.2最短超级字符串121

5.3.3重排字符串问题124

5.3.4图顶点填色问题127

5.3.5奶茶找零问题129

5.3.6将整数n变成1131

第6章图论算法134

6.1图论基本算法134

6.1.1图的基本概念134

6.1.2图的数据结构表示136

6.1.3广度优先搜索136

6.1.4深度优先搜索138

6.1.5图搜索算法应用140

6.1.6连通性141

6.1.7最小生成树算法145

6.1.8最大流算法149

6.2图论算法应用实例155

6.2.1蛇梯问题155

6.2.2桥问题157

6.2.3查找超级节点162

6.2.4二分图匹配问题165

6.2.5点连通度和边连通度166

6.2.6边不相交问题170

6.2.7环流问题171

6.2.8机场调度问题174

6.2.9项目选择问题178

6.2.10棒球比赛问题180

第7章摊还分析184

7.1摊还分析与渐进分析184

7.1.1栈操作185

7.1.2二进制计数185

7.2聚合分析186

7.2.1栈操作186

7.2.2二进制计数186

7.2.3字典187

7.3核算法188

7.3.1栈操作188

7.3.2二进制计数189

7.3.3动态表189

7.3.4234树190

7.4势能法192

7.4.1栈操作193

7.4.2二进制计数194

7.4.3动态表195

7.4.4234树195

7.4.5笛卡儿树197

参考文献201