Data-Structure

LeetCode

• 常用数据结构以及复杂度

  O(1) 位运算 常数级复杂度，一般面试中不会有
  O(logn) 二分法，倍增法，快速幂算法，辗转相除法
  O(n) 枚举法，双指针算法，单调栈算法，KMP算法，Rabin Karp，Manacher's Algorithm 又称作线性时间复杂度
  O(nlogn) 快速排序，归并排序，堆排序
  O(n^2) 枚举法，动态规划，Dijkstra
  O(n^3) 枚举法，动态规划，Floyd
  O(2^n) 与组合有关的搜索问题
  O(n!) 与排列有关的搜索问题
  

• 递归一定会耗费的空间包括

1. 参数列表(参数有多少个字节，往下递归每一次就会开辟多少个字节用于存储)
2. Return的Value
3. 中间产生的局部变量

* 递归三要素 1. 函数接受什么样的参数，返回样的值，代表什么意思 2. 递归的拆解(一个大问题如何拆解为若干个小问题去解决) 3. 递归的出口(什么时候可以直接知道答案，不用再拆解，直接 return)

• 栈空间 VS 堆空间
  1. 栈空间分为 函数的参数与返回值 和 函数的局部变量
  2. 栈空间里存储的内容，会在函数结束的时候被撤回。
  3. new出来的就放在堆空间, 其他都是栈空间