> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/some_tips.md).

# 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)