《算法竞赛入门经典（第2版）》的原文摘录
-
现在讨论最坏情况下也是O(n)的方案，把所有的数分为5个一堆，那么总共会有n/5堆，对于每堆我们可以很快的找到中位数（因为只有5个所以很容易嘛），之后调用当前算法找到这n/5个中位数的中位数，用这个数来做pivot，所以这个算法被叫做Median of Medians algorithm。 把中位数的中位数作为pivot的话，那么原数组中便会有3/5*1/2个也就是3/10个小于等于这个pivot的，同理会有3/10大于这个pivot的，所以最坏情况下，数组被分为30%，70%或者70%，30%的两部分。 T(n)<=T(n/5)+T(7/10*n)+O(n)<=c*n*(1+9/10+(9/10)^2....) 所以T(n)=O(n) 也就是最坏情况下是O(n)。 (查看原文) —— 引自第145页 -
有趣的是，如果把状态定义成“d(i)表示以节点i为终点的最长路径长度”，也能顺利求出最优值，却难以打印出字典序最小的方案。想一想，为什么？你能总结出一些规律吗？ (查看原文) —— 引自第163页 -
C语言中的字符型用关键字char表示，实际储存的是字符的ASCII码。字符常量可以用单引号法表示。在语法上可以当做int型使用。 (查看原文) —— 引自第49页 -
可以用sprintf把格式化信息输出到字符串，保证buffer足够大。 由于字符串的本质是数组，只能用strcpy，strcmp，strcat来执行“赋值”，“比较”，“连接”操作。不能用=，==，<=,+等运算符。它们在string.h中。 (查看原文) —— 引自第49页 -
使用fgetc可以从打开的文件读取一个字符。一般情况下应当检查不是EOF后再将其转换成char值。getchar等价于fgetc（stdin）。 fgets会读取完整的一行。就是说，它一旦读取到‘\n’，就会停止读取工作，然后在buffer后加‘\0’结束符。 头文件ctype.h中定义的isalpha，isdigit,isprint,等可以判断字符的属性，toupper,tolower等用来转换大小写。 (查看原文) —— 引自第49页 -
字符还可以直接用ASCII码来表示。如果用八进制\o,十六进制就是\xh（h为16进制数字串） (查看原文) —— 引自第49页 -
为了方便使用，往往用typedef struct {域定义；}类型名；的方式定义一个新类型名。这样，就可以像原生数据类型一样使用这个自定义类型了。 (查看原文) —— 引自第68页 -
建议用来判断某事物是否具有某种特殊性质的函数命名成“is_xxx”的形式。返回非0数为真，0为假。 (查看原文) —— 引自第68页 -
编写函数时，尽量保证它能对任何合法参数都能得到正确结果，如若不然，应在显著位置标明函数的缺陷，以避免使用。编程时，合理的利用assert宏，将给调试带来很大的方便。（assert.h） (查看原文) —— 引自第68页 -
C语言用调用栈（call stack）来描述函数之间的调用关系。调用栈由栈帧（stack frame）组成，每个栈帧对应着一个未运行完成的函数。 (查看原文) —— 引自第68页 -
记住为递归函数编写终止条件，否则无限递归，导致栈溢出。 在运行时，程序会动态创建一个堆栈段，里面存放着栈帧，因此保存着调用关系和局部变量。 在可执行文件中，文本段储存指令，数据段存储已初始化的全局变量，BSS段存储未赋值的全局变量 (查看原文) —— 引自第68页 -
有些题考虑建立常量表，打表的方式可能会更简单。 用状态变量来辅助字符串读入 对于大数高精度运算，请考虑数组存储大数，模拟手工计算。考虑万进制提高效率。 (查看原文) —— 引自第88页 -
排序的话，数据规模小的话，冒泡排序很管用的，比快排好。快排有时候分割不好，速度很慢。stdlib.h中的qsort速度就很快。 (查看原文) —— 引自第88页 -
对比测试，随机生成大规模随机数据量。考虑srand , time,rand rand生成闭区间的[0,RAND_MAX],RAND_MAX至少为32767. (查看原文) —— 引自第112页 -
二叉树的一般三种遍历：先序遍历，中序遍历，后序遍历如下： PreOrder（T）=T的根节点 + PreOrder（T的左子树） + PreOrder(T的右子树) InOrder（T）= InOrder（T的左子树） + T的根节点 + InOrder(T的右子树) PostOrder（T）=PostOrder（T的左子树） + PostOrder(T的右子树)+ T的根节点 (查看原文) —— 引自第112页 -
关于图，考虑DFS,BFS，拓扑排序。 (查看原文) —— 引自第112页 -
暴力求解，一般用在排列枚举之类的方面。 (查看原文) —— 引自第137页 -
如果某问题的解可以由多个步骤得到，而每个步骤可以由若干种选择，且可以使用递归枚举，工作方式可以用解答树来描述。 (查看原文) —— 引自第137页 -
子集生成算法：给定一个集合，枚举它所有可能的子集。一般有3种思路：增量构造，位向量法，二进制法。 用二进制表示子集，其中从右往左第i位（从0开始编号）表示元素i是否在集合中（1表示“在”，0表示“不在”）。当用二进制法表示子集时，位运算中的&， | ，^对应集合的交，并，对称差。 (查看原文) —— 引自第137页 -
在编写枚举递归需要深入分析，对模型精雕细琢。如果在回溯法中使用了辅助的全局变量，用完之后，请恢复原状。 (查看原文) —— 引自第137页
作者: 刘汝佳
isbn: 7302356289
书名: 算法竞赛入门经典（第2版）
页数: 464
定价: CNY 49.80
出版社: 清华大学出版社
出版年: 2014-6-1
装帧: 平装