Some Tips

拿到一个问题，如何下手？

画图

想暴力解以及对应复杂度，再看有什么地方能优化

每个算法都有特别适用的场合，把这些场合熟记于心。

1. 对于index queue或stack的应用, 如果还要记录index可以再建一个index queue或stack与它同步执行(Print Binary Tree)

2. 配对用+1, -1 (valid parentheses, meeting rooms)

递归时间复杂度分析:

1. master theorem

2. 排列组合(出现和不出现的2^O(N), N!等)

3. T(n)=aT(n-b)+f(n), n>1 for some constants c,a>0,b>0,k>=0 and function f(n) and could be solved using Subtract and Conquer Recurrence method.

   If f(n) is of the form n^k then,

   T(n)={O(n^k), if a<1

       O(n^(k+1)),if a=1
       O(n^ka^(n/b)), if a >1}

区分subarray 和subsequence

max/min subsequence 一般用dp, 除了LIS和LCS(用set) subarray/substring/continuous subsequence 用窗口 max/min subarray sum == k, 用hashmap记录index find range sum given i, j, 用dp

BFS和DFS

当有target时, BFS能快速确定到达target的最短路径. DFS常用于find all possible solutions的情况.

Circular

相当于把原数组再粘一次.

检测环

1. Floyd Algorithm: linear data structure (list, array)

2. Union Find: non-linear data structure (tree, graph)