树
- 前中后序遍历二叉树（计算二叉树节点）
- 哈夫曼树生成
可以给候选集快排，然后选前2个节点，往后面新增一个节点。节点结构点定义好可以少写些映射关系
排序
- 冒泡排序
把最大浮到最后面，后界不断减小，一种优化策略是记录最后一个交换的位置，令其为后界（因为此位置后面的数都已有序）
- 快速排序
Partition不需要额外写个函数，用算法导论上面的非常漂亮https://www.cnblogs.com/pugang/archive/2012/06/27/2565093.html
- 堆排序
关键是heapify，然后用数组存好，父亲序号与左右儿子的序号关系是恒定的，这点很重要
- 归并排序
动态规划
- 最长上升子序列
- 最长公共子序列
这个凸显了分解成子问题的思想
- 最长公共子串
这个跟最长上升子序列极类似：以当前点为终点的XXX
图
- 拓扑排序
删除入度为0的节点，用栈储存
串
- KMP
next[i]的意思是pattern[i]失配时，下一个要测试的位置。计算next[i]时，pattern[i]是用来计算next[i + 1]的
- 字符串DP
搜索
- 二分搜索
不断改变上下界，不需要递归
链表
- 反转单链表
- 二维数组中的查找（二分搜索、特题特解）
右上角或左下角开始
网友评论