常用算法总结
文章目录
常用算法总结迭代算法(Iteration)递归算法(Recursion)回溯算法(Backtrack)深度优先(Depth First Search, DFS)广度优先(Breadth First Search, BFS)动态规划(Dynamic Programming, DP)分治算法(二分法, Binary Algorithm)贪心算法(Greedy Algorithm)滑动窗口(Slipping Window)双指针(Double Pointer)位运算(Bit)自动机搜索/排序算法关于链表(List)关于树(Tree)关于图(Graph)关于栈、队列、散列表(queue, stack, hashlist)
迭代算法(Iteration)
递归算法(Recursion)
二叉树的遍历算法
回溯算法(Backtrack)
八皇后问题
深度优先(Depth First Search, DFS)
全排列问题
广度优先(Breadth First Search, BFS)
类型
不需要确定当前深度
需要确定当前深度
习题
二叉树的层序遍历
102. Binary Tree Level Order Traversal107. Binary Tree Level Order Traversal II
动态规划(Dynamic Programming, DP)
斐波那契数列爬楼梯问题背包问题最长公共子序列最优二叉搜索树
分治算法(二分法, Binary Algorithm)
二分排序
二分查找
贪心算法(Greedy Algorithm)
霍夫曼编码
滑动窗口(Slipping Window)
双指针(Double Pointer)
位运算(Bit)
要点
异或运算（xor）
任何数与0做异或运算，结果仍为原来的数。即：
a
⊕
0
=
a
a \oplus 0 = a
a⊕0=a 任何数和其自身做异或运算，结果为0。即：
a
⊕
a
=
0
a \oplus a = 0
a⊕a=0
异或运算满足交换律和结合律。即：
a
⊕
b
=
b
⊕
a
a
⊕
b
⊕
c
=
a
⊕
(
b
⊕
c
)
a\oplus b = b\oplus a \\ a \oplus b \oplus c = a\oplus (b\oplus c)
a⊕b=b⊕aa⊕b⊕c=a⊕(b⊕c)
习题
不使用额外空间进行数交换找到只出现奇数次的数字
136. Single Number137. Single Number II
自动机
搜索/排序算法
快速排序希尔排序插入排序拓扑排序二分排序堆排序
关于链表(List)
单向链表双向链表广义表
关于树(Tree)
二叉树遍历
前序遍历中序遍历后序遍历层序遍历 二叉搜索树红黑树kd 树B 树堆极大堆
关于图(Graph)
最小生成树最短路径问题
关于栈、队列、散列表(queue, stack, hashlist)
栈对于二叉树层序遍历的实现
最大优先级队列
