没有合适的资源?快使用搜索试试~ 我知道了~
首页算法(algorithm)手写代码必备手册_戴方勤_非扫描专业排版完美标签
本书的目标读者是准备去北美找工作的码农,也适用于在国内找工作的码农,以及刚接触ACM 算法竞赛的新手。 本书包含了一些经典题目的范例代码,经过精心编写,编码规范良好,适合在纸上默 写。 怎么样才算是经典的算法题?一般经典的题目都有约定俗成的名称,例如“八皇后问 题”,“0-1 背包问题”等,这些名字已经固定下来了,类似于一个“成语”,一般说出名字, 大家就都知道题目意思了,不用再解释题目内容,这就是所谓的“经典”。同时,本书的 每一个题目,都至少在两本纸质书中出现过。 这本书的定位,与ACM 算法竞赛类书籍不同。全书的题目比ACM 竞赛简单,没有高 难度的题目,但每道题目,都有详细生动的解释,还给出了可以直接在OJ 上AC 的代码。 同时,题目的范围不限于算法竞赛,还包括了一些面试中常碰到的工程类题目。 全书的代码,使用“纯C + STL”的风格。本书中的代码规范,跟在公司中的工程规 范略有不同,为了使代码短(方便迅速实现)
资源详情
资源评论
资源推荐

手写代码必备手册
戴方勤 (soulmachine@gmail.com)
https://github.com/soulmachine/acm-cheat-sheet
最后更新 2013-10-20
版权声明
本作品采用“Creative Commons 署名 -非商业性使用 -相同方式共享 3.0 Unported 许可协议
(cc by-nc-sa)”进行许可。http://creativecommons.org/licenses/by-nc-sa/3.0/
内容简介
本书的目标读者是准备去北美找工作的码农,也适用于在国内找工作的码农,以及刚
接触 ACM 算法竞赛的新手。
本书包含了一些经典题目的范例代码,经过精心编写,编码规范良好,适合在纸上默
写。
怎么样才算是经典的算法题?一般经典的题目都有约定俗成的名称,例如“八皇后问
题”,“0-1 背包问题”等,这些名字已经固定下来了,类似于一个“成语”,一般说出名字,
大家就都知道题目意思了,不用再解释题目内容,这就是所谓的“经典”。同时,本书的
每一个题目,都至少在两本纸质书中出现过。
这本书的定位,与 ACM 算法竞赛类书籍不同。全书的题目比 ACM 竞赛简单,没有高
难度的题目,但每道题目,都有详细生动的解释,还给出了可以直接在 OJ 上 AC 的代码。
同时,题目的范围不限于算法竞赛,还包括了一些面试中常碰到的工程类题目。
全书的代码,使用“纯 C + STL”的风格。本书中的代码规范,跟在公司中的工程规
范略有不同,为了使代码短(方便迅速实现):
• 所有代码都是单一文件。这是因为一般 OJ 网站,提交代码的时候只有一个文本框,
如果还是按照标准做法,比如分为头文件.h 和源代码.cpp,无法在网站上提交;
• 喜欢在全局定义一个最大整数,例如 MAX。一般的 OJ 题目,都会有数据规模的限
制,所以定义一个常量 MAX 表示这个规模,可以不用动态分配内存,让代码实现更
简单;
• 经常使用全局变量。比如用几个全局变量,定义某个递归函数需要的数据,减少递
归函数的参数个数,就减少了递归时栈内存的消耗,可以说这几个全局变量是这个
递归函数的“环境”。
i

ii
• 不提倡防御式编程。不需要检查 malloc()/new 返回的指针是否为 NULL;不需要检查
内部函数入口参数的有效性;使用纯 C 基于对象编程时,调用对象的成员方法,不
需要检查对象自身是否为 NULL。
本手册假定读者已经学过《数据结构》
¬
,《算法》
这两门课,熟练掌握 C++ 或
Java。
Github 地址
本书是开源的,项目地址:https://github.com/soulmachine/acm-cheat-sheet
北美求职微博群
我和我的小伙伴们在这里:http://q.weibo.com/1312378
¬
《数据结构》,严蔚敏等著,清华大学出版社,http://book.douban.com/subject/2024655/
《Algorithms》,Robert Sedgewick, Addison-Wesley Professional, http://book.douban.com/subject/4854123/

目录
第 1 章 编程技巧 1
第 2 章 线性表 2
第 3 章 字符串 3
3.1 字符串 API . . . . . . . . . . . . 3
3.1.1 strlen . . . . . . . . . . . 3
3.1.2 strcpy . . . . . . . . . . 3
3.1.3 strstr . . . . . . . . . . . 4
3.1.4 atoi . . . . . . . . . . . . 5
3.2 字符串排序 . . . . . . . . . . . 6
3.3 单词查找树 . . . . . . . . . . . 6
3.4 子串查找 . . . . . . . . . . . . . 6
3.4.1 KMP 算法 . . . . . . . . 7
3.4.2 Boyer-Moore 算法 . . . 8
3.4.3 Rabin-Karp 算法 . . . . 11
3.4.4 总结 . . . . . . . . . . . 13
3.5 正则表达式 . . . . . . . . . . . 13
第 4 章 栈和队列 14
4.1 栈 . . . . . . . . . . . . . . . . . 14
4.1.1 汉诺塔问题 . . . . . . . 14
4.1.2 进制转换 . . . . . . . . 16
4.2 队列 . . . . . . . . . . . . . . . 18
4.2.1 打印杨辉三角 . . . . . 18
第 5 章 树 19
5.1 二叉树的遍历 . . . . . . . . . . 19
5.2 线索二叉树 . . . . . . . . . . . 22
5.3 Morris Traversal . . . . . . . . . 25
5.3.1 Morris 中序遍历 . . . . 25
5.3.2 Morris 先序遍历 . . . . 26
5.3.3 Morris 后序遍历 . . . . 27
5.3.4 C 语言实现 . . . . . . . 28
5.4 重建二叉树 . . . . . . . . . . . 32
5.5 堆 . . . . . . . . . . . . . . . . . 34
5.5.1 原理和实现 . . . . . . . 34
5.5.2 最小的 N 个和 . . . . . 38
5.6 并查集 . . . . . . . . . . . . . . 40
5.6.1 原理和实现 . . . . . . . 40
5.6.2 病毒感染者 . . . . . . . 43
5.6.3 两个黑帮 . . . . . . . . 44
5.6.4 食物链 . . . . . . . . . . 48
5.7 线段树 . . . . . . . . . . . . . . 52
5.7.1 原理和实现 . . . . . . . 52
5.7.2 Balanced Lineup . . . . 52
5.7.3 线段树练习 1 . . . . . . 55
5.7.4 A Simple Problem with
Integers . . . . . . . . . 58
5.7.5 约瑟夫问题 . . . . . . . 61
5.8 Trie 树 . . . . . . . . . . . . . . 65
5.8.1 原理和实现 . . . . . . . 65
5.8.2 Immediate Decodebility 66
5.8.3 Hardwood Species . . . 68
第 6 章 查找 73
6.1 折半查找 . . . . . . . . . . . . . 73
6.2 哈希表 . . . . . . . . . . . . . . 73
6.2.1 原理和实现 . . . . . . . 73
iii

iv 目录
6.2.2 Babelfish . . . . . . . . . 75
第 7 章 排序 79
7.1 插入排序 . . . . . . . . . . . . . 79
7.1.1 直接插入排序 . . . . . 79
7.1.2 折半插入排序 . . . . . 80
7.1.3 希尔 (Shell) 插入排序 . 80
7.2 交换排序 . . . . . . . . . . . . . 82
7.2.1 冒泡排序 . . . . . . . . 82
7.2.2 快速排序 . . . . . . . . 83
7.3 选择排序 . . . . . . . . . . . . . 85
7.3.1 简单选择排序 . . . . . 85
7.3.2 堆排序 . . . . . . . . . . 86
7.4 归并排序 . . . . . . . . . . . . . 87
7.5 基数排序 . . . . . . . . . . . . . 88
7.6 总结和比较 . . . . . . . . . . . 91
第 8 章 暴力枚举法 93
8.1 枚举排列 . . . . . . . . . . . . . 93
8.1.1 生成 1 到 n 的全排列 . 93
8.1.2 生成可重集的排列 . . . 95
8.1.3 下一个排列 . . . . . . . 97
8.2 子集生成 . . . . . . . . . . . . . 99
8.2.1 增量构造法 . . . . . . . 99
8.2.2 位向量法 . . . . . . . . 99
8.2.3 二进制法 . . . . . . . . 100
第 9 章 广度优先搜索 102
9.1 走迷宫 . . . . . . . . . . . . . . 102
9.2 八数码问题 . . . . . . . . . . . 107
9.3 四子连棋 . . . . . . . . . . . . . 118
9.4 双向 BFS . . . . . . . . . . . . . 124
9.4.1 八数码问题 . . . . . . . 124
9.5 A* 算法 . . . . . . . . . . . . . . 124
9.5.1 八数码问题 . . . . . . . 124
9.6 小结 . . . . . . . . . . . . . . . 131
9.6.1 适用场景 . . . . . . . . 131
9.6.2 思考的步骤 . . . . . . . 131
9.6.3 代码模板 . . . . . . . . 132
第 10 章 深度优先搜索 140
10.1 四色问题 . . . . . . . . . . . . . 140
10.2 全排列 . . . . . . . . . . . . . . 142
10.3 八皇后问题 . . . . . . . . . . . 144
10.4 还原 IP 地址 . . . . . . . . . . . 148
10.5 Combination Sum . . . . . . . . 149
10.6 Combination Sum II . . . . . . . 150
10.7 小结 . . . . . . . . . . . . . . . 151
10.7.1 适用场景 . . . . . . . . 151
10.7.2 思考的步骤 . . . . . . . 151
10.7.3 代码模板 . . . . . . . . 153
10.7.4 深搜与回溯法的区别 . 153
10.7.5 深搜与递归的区别 . . . 153
第 11 章 分治法 155
11.1 棋盘覆盖 . . . . . . . . . . . . . 155
11.2 循环赛日程表 . . . . . . . . . . 158
第 12 章 贪心法 162
12.1 最优装载 . . . . . . . . . . . . . 162
12.2 哈弗曼编码 . . . . . . . . . . . 162
12.3 部分背包问题 . . . . . . . . . . 164
第 13 章 动态规划 165
13.1 动规和备忘录法的区别 . . . . 165
13.2 最长公共子序列 . . . . . . . . 166
13.3 最大连续子序列和 . . . . . . . 169
13.4 最大 M 子段和 . . . . . . . . . 172
13.5 背包问题 . . . . . . . . . . . . . 174
13.5.1 0-1 背包问题 . . . . . . 174

目录 v
13.5.2 完全背包问题 . . . . . 178
13.5.3 多重背包问题 . . . . . 183
13.6 序列型动态规划 . . . . . . . . 186
13.6.1 最长上升子序列 . . . . 186
13.6.2 嵌套矩形 . . . . . . . . 188
13.6.3 线段覆盖 2 . . . . . . . 191
13.6.4 硬币问题 . . . . . . . . 193
13.7 区间型动态规划 . . . . . . . . 199
13.7.1 最优矩阵链乘 . . . . . 199
13.7.2 石子合并 . . . . . . . . 202
13.7.3 矩阵取数游戏 . . . . . 204
13.8 棋盘型动态规划 . . . . . . . . 210
13.8.1 数字三角形 . . . . . . . 210
13.8.2 过河卒 . . . . . . . . . . 213
13.8.3 传纸条 . . . . . . . . . . 215
13.8.4 骑士游历 . . . . . . . . 218
13.9 划分型动态规划 . . . . . . . . 220
13.9.1 乘积最大 . . . . . . . . 220
13.9.2 数的划分 . . . . . . . . 223
13.10 树型动态规划 . . . . . . . . . 225
13.10.1 访问艺术馆 . . . . . . . 225
13.10.2 没有上司的舞会 . . . . 228
13.11 最大子矩形 . . . . . . . . . . . 231
13.11.1 奶牛浴场 . . . . . . . . 231
13.11.2 最大全 1 子矩阵 . . . . 235
第 14 章 图 238
14.1 图的深搜 . . . . . . . . . . . . . 239
14.1.1 Satellite Photographs . . 239
14.1.2 John’s trip . . . . . . . . 242
14.1.3 e Necklace . . . . . . 245
14.2 图的广搜 . . . . . . . . . . . . . 249
14.3 最小生成树 . . . . . . . . . . . 249
14.3.1 Prim 算法 . . . . . . . . 249
14.3.2 Kruskal 算法 . . . . . . 256
14.3.3 Highways . . . . . . . . 260
14.3.4 最优布线问题 . . . . . 263
14.4 最短路径 . . . . . . . . . . . . . 265
14.4.1 单源最短路径——Di-
jkstra 算法 . . . . . . . 265
14.4.2
每 点 最 短 路 径 ——
Floyd 算法 . . . . . . . . 269
14.4.3 HDU 2544 最短路 . . . 273
14.4.4 POJ 1125 Stockbroker
Grapevine . . . . . . . . 275
14.5 拓扑排序 . . . . . . . . . . . . . 279
14.5.1 POJ 1094 Sorting It All
Out . . . . . . . . . . . . 282
14.6 关键路径 . . . . . . . . . . . . . 286
第 15 章 数学方法与常见模型 292
15.1 数论 . . . . . . . . . . . . . . . 292
15.1.1 欧几里德算法 . . . . . 292
15.1.2 扩展欧几里德算法 . . . 293
15.1.3 素数判定 . . . . . . . . 295
15.1.4 大整数取模 . . . . . . . 297
15.2 组合数学 . . . . . . . . . . . . . 299
第 16 章 大整数运算 300
16.1 大整数加法 . . . . . . . . . . . 300
16.2 大整数减法 . . . . . . . . . . . 303
16.3 大整数乘法 . . . . . . . . . . . 306
16.4 大整数除法 . . . . . . . . . . . 309
16.5 大数阶乘 . . . . . . . . . . . . . 314
16.5.1 大数阶乘的位数 . . . . 314
16.5.2 大数阶乘 . . . . . . . . 315
第 17 章 基础功能 318
17.1 下一个排列 . . . . . . . . . . . 318
17.2 数组循环右移 . . . . . . . . . . 320
剩余328页未读,继续阅读
















安全验证
文档复制为VIP权益,开通VIP直接复制

评论0