算法小白努力刷题找实习

题量只有一百出头，今年感受到了寒气，要认真刷题了

547
因为需要计算城市块个数，所以需要理清楚城市之间的链接关系。
- 基于graph theory，a path to b， b path to c。使用经典unionfind
- 同时使用另一个定理，设x为path上一点，path上其他任意一点都与连同

unionfind本质上是add，merge（union）， find
unordered_map 既记录城市 也记录 连接关系
add：每次看到新城市，就add
merge：每次看到两点的connection，就看他们是否连同一个点（root），如果可以就在map上串联两点
find：在map内部，通过串联关系，查找是否连同一个点（root）

自此题目就在每个城市vector时add
每个vector内部的连接时merge
    merge内部需要find

1143
dp

因为需要求subsequence，所以要有dp来算区间最优解。
用2d vector 中 i，j 来分别存储text1，2的index（1-based），之所以1-based是为了防止index out of bounds
求出转换函数，得当两个来自text1，2的char不一样时，区间count为max(dp[j], dp[j-1])
当一样时，dp[j] = max(dp[j], dp[i-1][j-1] + 1);

最后进行压缩，把2d vector变成1d

1926
走迷宫算步数，经典bfs

用vsisited 2d vector来避免回头路
用queue来存起始位置

只要queue不空就while
为保证每次处理最周边的位置，记录下queue size之后在里面for loop
每pop一个位置，check 是否道出口（在边界位置上），检测周边的位置（是否out of bounds，是否撞墙，是否走过）再enqueue

1162
bfs

每次grid碰到算最近、最远距离的就用dfs
queue起始点先enqueue所有island
bfs 直到empty
剩下distance-1 就是真实距离（一开始的island也被计算了距离）

1091 同上
不过这次direction vetor里存了八个方向

841
dfs

trace并且记录visited，如果最后全部visited 那就return true

797
dfs，backtracking
同上，但这次多出一个2d vector存result，一个1d vector用来backtracking

542
bfs
记录距离的普遍用bfs
用一个2d vector grid记录result以及visited

547
定期复习