手写代码必备手册

也是从网上下到的，借花献佛吧，我觉得不错，看这本书的前提是已经学过数据结构和算法了，我觉得挺全的，希望对大家有帮助，觉得有用的帮我加点分吧~
手写代码必备手册_C.pdf (2.89 MB, 下载次数: 1201)

2014-3-16 22:02 上传

点击文件名下载附件
手写代码必备手册
下载积分: 大米 -1 颗

版权归： 戴方勤(soulmachine@gmail.com)
https://github.com/soulmachine/acm-cheat-sheet

最后更新2014-1-7
版权声明
本作品采用“Creative Commons 署名-非商业性使用-相同方式共享3.0 Unported 许可协议
(cc by-nc-sa)”进行许可。http://creativecommons.org/licenses/by-nc-sa/3.0/

目录
第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 栈的C 语言实现. . . . 14
4.1.2 汉诺塔问题. . . . . . . 16
4.1.3 进制转换. . . . . . . . 18
4.2 队列. . . . . . . . . . . . . . . 20
4.2.1 队列的C 语言实现. . 20
4.2.2 打印杨辉三角. . . . . 22
第5 章树24
5.1 二叉树的遍历. . . . . . . . . . 24
5.2 线索二叉树. . . . . . . . . . . 27
5.3 Morris Traversal . . . . . . . . . 30
5.3.1 Morris 中序遍历. . . . 30
5.3.2 Morris 先序遍历. . . . 31
5.3.3 Morris 后序遍历. . . . 32
5.3.4 C 语言实现. . . . . . . 33
5.4 重建二叉树. . . . . . . . . . . 37
5.5 堆. . . . . . . . . . . . . . . . . 39
5.5.1 原理和实现. . . . . . . 39
5.5.2 最小的N 个和. . . . . 43
5.6 并查集. . . . . . . . . . . . . . 45
5.6.1 原理和实现. . . . . . . 45
5.6.2 病毒感染者. . . . . . . 48
5.6.3 两个黑帮. . . . . . . . 50
5.6.4 食物链. . . . . . . . . . 53
5.7 线段树. . . . . . . . . . . . . . 57
5.7.1 原理和实现. . . . . . . 57
5.7.2 Balanced Lineup . . . . 57
5.7.3 线段树练习1 . . . . . . 60
5.7.4 A Simple Problem with
Integers . . . . . . . . . 63
5.7.5 约瑟夫问题. . . . . . . 67
5.8 Trie 树. . . . . . . . . . . . . . 70
5.8.1 原理和实现. . . . . . . 70
5.8.2 Immediate Decodebility 71
5.8.3 Hardwood Species . . . 74
iii
iv 目录
第6 章查找78
6.1 折半查找. . . . . . . . . . . . . 78
6.2 哈希表. . . . . . . . . . . . . . 78
6.2.1 原理和实现. . . . . . . 78
6.2.2 Babelfish . . . . . . . . . 80
第7 章排序84
7.1 插入排序. . . . . . . . . . . . . 84
7.1.1 直接插入排序. . . . . 84
7.1.2 折半插入排序. . . . . 85
7.1.3 希尔(Shell) 插入排序. 85
7.2 交换排序. . . . . . . . . . . . . 87
7.2.1 冒泡排序. . . . . . . . 87
7.2.2 快速排序. . . . . . . . 88
7.3 选择排序. . . . . . . . . . . . . 90
7.3.1 简单选择排序. . . . . 90
7.3.2 堆排序. . . . . . . . . . 91
7.4 归并排序. . . . . . . . . . . . . 92
7.5 基数排序. . . . . . . . . . . . . 93
7.6 总结和比较. . . . . . . . . . . 96
第8 章暴力枚举法98
8.1 枚举排列. . . . . . . . . . . . . 98
8.1.1 生成1 到n 的全排列. 98
8.1.2 生成可重集的排列. . . 100
8.1.3 下一个排列. . . . . . . 102
8.2 子集生成. . . . . . . . . . . . . 104
8.2.1 增量构造法. . . . . . . 104
8.2.2 位向量法. . . . . . . . 104
8.2.3 二进制法. . . . . . . . 105
第9 章广度优先搜索107
9.1 走迷宫. . . . . . . . . . . . . . 107
9.2 八数码问题. . . . . . . . . . . 112
9.3 四子连棋. . . . . . . . . . . . . 124
9.4 双向BFS . . . . . . . . . . . . . 130
9.4.1 八数码问题. . . . . . . 130
9.5 A* 算法. . . . . . . . . . . . . . 130
9.5.1 八数码问题. . . . . . . 130
9.6 小结. . . . . . . . . . . . . . . 137
9.6.1 适用场景. . . . . . . . 137
9.6.2 思考的步骤. . . . . . . 138
9.6.3 代码模板. . . . . . . . 138
第10 章深度优先搜索147
10.1 四色问题. . . . . . . . . . . . . 147
10.2 全排列. . . . . . . . . . . . . . 149
10.3 八皇后问题. . . . . . . . . . . 151
10.4 还原IP 地址. . . . . . . . . . . 155
10.5 Combination Sum . . . . . . . . 156
10.6 Combination Sum II . . . . . . . 157
10.7 小结. . . . . . . . . . . . . . . 158
10.7.1 适用场景. . . . . . . . 158
10.7.2 思考的步骤. . . . . . . 158
10.7.3 代码模板. . . . . . . . 160
10.7.4 深搜与回溯法的区别. 160
10.7.5 深搜与递归的区别. . . 160
第11 章分治法162
11.1 棋盘覆盖. . . . . . . . . . . . . 162
11.2 循环赛日程表. . . . . . . . . . 165
第12 章贪心法169
12.1 最优装载. . . . . . . . . . . . . 169
12.2 哈弗曼编码. . . . . . . . . . . 169
12.3 部分背包问题. . . . . . . . . . 171
目录v
第13 章动态规划172
13.1 动规和备忘录法的区别. . . . 172
13.2 最长公共子序列. . . . . . . . 173
13.3 最大连续子序列和. . . . . . . 176
13.4 最大M 子段和. . . . . . . . . 179
13.5 背包问题. . . . . . . . . . . . . 181
13.5.1 0-1 背包问题. . . . . . 181
13.5.2 完全背包问题. . . . . 185
13.5.3 多重背包问题. . . . . 190
13.6 序列型动态规划. . . . . . . . 193
13.6.1 最长上升子序列. . . . 193
13.6.2 嵌套矩形. . . . . . . . 195
13.6.3 线段覆盖2 . . . . . . . 198
13.6.4 硬币问题. . . . . . . . 200
13.7 区间型动态规划. . . . . . . . 206
13.7.1 最优矩阵链乘. . . . . 206
13.7.2 石子合并. . . . . . . . 209
13.7.3 矩阵取数游戏. . . . . 211
13.8 棋盘型动态规划. . . . . . . . 217
13.8.1 数字三角形. . . . . . . 217
13.8.2 过河卒. . . . . . . . . . 220
13.8.3 传纸条. . . . . . . . . . 222
13.8.4 骑士游历. . . . . . . . 225
13.9 划分型动态规划. . . . . . . . 227
13.9.1 乘积最大. . . . . . . . 227
13.9.2 数的划分. . . . . . . . 230
13.10 树型动态规划. . . . . . . . . 232
13.10.1 访问艺术馆. . . . . . . 232
13.10.2 没有上司的舞会. . . . 235
13.11 最大子矩形. . . . . . . . . . . 238
13.11.1 奶牛浴场. . . . . . . . 238
13.11.2 最大全1 子矩阵. . . . 242
第14 章图245
14.1 图的深搜. . . . . . . . . . . . . 245
14.1.1 Satellite Photographs . . 246
14.1.2 John’s trip . . . . . . . . 249
14.1.3 ?e Necklace . . . . . . 252
14.2 图的广搜. . . . . . . . . . . . . 256
14.3 最小生成树. . . . . . . . . . . 256
14.3.1 Prim 算法. . . . . . . . 256
14.3.2 Kruskal 算法. . . . . . 263
14.3.3 Highways . . . . . . . . 267
14.3.4 最优布线问题. . . . . 271
14.4 最短路径. . . . . . . . . . . . . 272
14.4.1 单源最短路径——Dijkstra
算法. . . . . . . 272
14.4.2 每点最短路径——
Floyd 算法. . . . . . . . 277
14.4.3 例题：HDU 2544 最短路282
14.4.4 例题：POJ 1125 Stockbroker
Grapevine . . . . 284
14.5 拓扑排序. . . . . . . . . . . . . 288
14.5.1 例题：POJ 1094 Sorting
It All Out . . . . . . . . 291
14.6 关键路径. . . . . . . . . . . . . 295
第15 章数学方法与常见模型301
15.1 数论. . . . . . . . . . . . . . . 301
15.1.1 欧几里德算法. . . . . 301
15.1.2 扩展欧几里德算法. . . 302
15.1.3 素数判定. . . . . . . . 304
15.1.4 大整数取模. . . . . . . 306
15.2 组合数学. . . . . . . . . . . . . 308
第16 章大整数运算309
16.1 大整数加法. . . . . . . . . . . 309
16.2 大整数减法. . . . . . . . . . . 312




内容简介
本书的目标读者是准备去北美找工作的码农，也适用于在国内找工作的码农，以及刚
接触ACM 算法竞赛的新手。
本书包含了一些经典题目的范例代码，经过精心编写，编码规范良好，适合在纸上默
写。
怎么样才算是经典的算法题？一般经典的题目都有约定俗成的名称，例如“八皇后问
题”，“0-1 背包问题”等，这些名字已经固定下来了，类似于一个“成语”，一般说出名字，
大家就都知道题目意思了，不用再解释题目内容，这就是所谓的“经典”。同时，本书的
每一个题目，都至少在两本纸质书中出现过。
这本书的定位，与ACM 算法竞赛类书籍不同。全书的题目比ACM 竞赛简单，没有高
难度的题目，但每道题目，都有详细生动的解释，还给出了可以直接在OJ 上AC 的代码。
同时，题目的范围不限于算法竞赛，还包括了一些面试中常碰到的工程类题目。
全书的代码，使用“纯C + STL”的风格。本书中的代码规范，跟在公司中的工程规
范略有不同，为了使代码短（方便迅速实现）:
• 所有代码都是单一文件。这是因为一般OJ 网站，提交代码的时候只有一个文本框，
如果还是按照标准做法，比如分为头文件.h 和源代码.cpp，无法在网站上提交；
• 喜欢在全局定义一个最大整数，例如MAX。一般的OJ 题目，都会有数据规模的限
制，所以定义一个常量MAX 表示这个规模，可以不用动态分配内存，让代码实现更
简单；
• 经常使用全局变量。比如用几个全局变量，定义某个递归函数需要的数据，减少递
归函数的参数个数，就减少了递归时栈内存的消耗，可以说这几个全局变量是这个
递归函数的“环境”。
ii不提倡防御式编程。不需要检查malloc()/new 返回的指针是否为NULL；不需要检查
内部函数入口参数的有效性；使用纯C 基于对象编程时，调用对象的成员方法，不
需要检查对象自身是否为NULL。
本手册假定读者已经学过《数据结构》¬，《算法》- 这两门课，熟练掌握C++ 或
Java。
Github 地址
本书是开源的，项目地址：https://github.com/soulmachine/acm-cheat-sheet
北美求职微博群
我和我的小伙伴们在这里：http://q.weibo.com/1312378

最近在学习算法，正在寻找好的算法文档目录，楼主给了点补充的内容，thanks

题目不错！突然有种搞一个java版本的冲动，有同样想法的同学请联系我

非常感谢楼主的分享！申请接近尾声，准备好好刷题了！Fighting～！

这份代码被leetcode警告过，我还以为加private了。
看过这份代码，还不错。思路可借鉴，写法上最好还是自己来，太多人看过这份PDF了。

chopper 发表于 2014-3-16 23:10
这份代码被leetcode警告过，我还以为加private了。
看过这份代码，还不错。思路可借鉴，写法上最好还是自己 ...

谢谢提醒！ 看来只能借鉴思路了

chopper 发表于 2014-3-16 23:10
这份代码被leetcode警告过，我还以为加private了。
看过这份代码，还不错。思路可借鉴，写法上最好还是自己 ...

这份代码被leetcode警告过是什么意思？

sanguine 发表于 2014-3-17 14:59
这份代码被leetcode警告过是什么意思？

同问！                  

sanguine 发表于 2014-3-17 14:59
这份代码被leetcode警告过是什么意思？

因为这个PDF是以电子书的形式发布，里面的题来自leetcode，而leetcode并不同意这个电子书引用它里面的题目。听起来有点扯，不过确实是这样。
所以有人建议把题目改成中文的。。这样就不涉及到版权的问题了。

EroicaCMCS 发表于 2014-3-17 15:12
同问！

因为这个PDF是以电子书的形式发布，里面的题来自leetcode，而leetcode并不同意这个电子书引用它里面的题目。听起来有点扯，不过确实是这样。
所以有人建议把题目改成中文的。。这样就不涉及到版权的问题了。

chopper 发表于 2014-3-17 15:54
因为这个PDF是以电子书的形式发布，里面的题来自leetcode，而leetcode并不同意这个电子书引用它里面的题目 ...

thx~
原来是版权的问题，我还以为是里面的内容有问题。

谢谢分享~收藏个~

chopper 发表于 2014-3-17 15:54
因为这个PDF是以电子书的形式发布，里面的题来自leetcode，而leetcode并不同意这个电子书引用它里面的题目 ...

哦哦~~~我还以为是里面的代码有什么问题=。=