常用算法总结

迭代算法(Iteration)

递归算法(Recursion)

• 二叉树的遍历算法

回溯算法(Backtrack)

• 八皇后问题

深度优先(Depth First Search, DFS)

• 全排列问题

广度优先(Breadth First Search, BFS)

类型

• 不需要确定当前深度
• 需要确定当前深度

动态规划(Dynamic Programming, DP)

• 斐波那契数列
• 爬楼梯问题
• 背包问题
• 最长公共子序列
• 最优二叉搜索树

分治算法(二分法, Binary Algorithm)

• 二分排序
• 二分查找

贪心算法(Greedy Algorithm)

• 霍夫曼编码

滑动窗口(Slipping Window)

双指针(Double Pointer)

位运算(Bit)

要点

• 异或运算（xor）
• 任何数与 0 做异或运算，结果仍为原来的数。即：

a⊕0=a

• 任何数和其自身做异或运算，结果为 0。即：

a⊕a=0

• 异或运算满足交换律和结合律。即：

a⊕b=b⊕a
a⊕b⊕c=a⊕(b⊕c)

自动机

• 搜索/排序算法
• 快速排序
• 希尔排序
• 插入排序
• 拓扑排序
• 二分排序
• 堆排序

关于链表(List)

• 单向链表
• 双向链表
• 广义表

关于树(Tree)

• 二叉树遍历
  • 前序遍历
  • 中序遍历
  • 后序遍历
  • 层序遍历
• 二叉搜索树
• 红黑树
• kd 树
• B 树
• 堆
• 极大堆

关于图(Graph)

• 最小生成树
• 最短路径问题

关于栈、队列、散列表(queue, stack, hashlist)

• 栈对于二叉树层序遍历的实现
• 最大优先级队列