刷题几个月的自我检讨
8月份了，开始投简历和约面试了。打开job description依旧还是这么的虚。看一眼面经也不能保证立刻有思路。刷题的时候有时候会觉得思路来的很快，有时候又觉得无论怎么样都不会有思路。痛定思痛，可能是我还是太懈怠了。只注意刷题没有关注业界需要的skills，抱残守缺不愿意改变。假装自己名校毕业能找到心仪的工作，而对自己才学的欠缺视而不见，甚至垃圾博客也没更新。一边焦急于现状一边又只想要逃避。我从去年12月打定主意跳槽，2月10日开始刷题，到今天8月24日，一共提交了1176次，也就是说大概刷了300题左右，真的可以说是很懈怠了。其他想跳槽的小伙伴已经有不少人拿到了心仪的工作，是我太容易泄气和逃避了。嘴里说着想要做SDE不想做DS，却不付出实际行动去学习SDE的知识。工作没有意思又不抓紧时间滚蛋，除了随着时间推移而一天天更加自闭，难道还有什么别的结局吗？说着infra是最想要的，却毫无付出努力，简历上都是ml。Infra是我最想要的吗？我也不知道。责备自己也没什么用，错的事情多了也只能这样走下去。本来以为自己能刷两遍这些题，可是实际上呢，哪次找工作不是赶鸭子上架。痛定思痛，如果这次有幸找到心仪的工作，以后一定要好好努力。简单回顾一下自己刷的题，主要是自己觉得不太熟悉的tag的medium题。呃，tag好多总结起来好费劲。我这次从题目数量多的开始！！！我不讨厌刷题，只是拿刷题来逃避人生和麻痹自我太不应该了。以后一定努力学习好好刷题好好生活(;´༎ຶД༎ຶ`) 在生活不如意的时候坚持下去才是更难的吧。
Dynamic Programming
发现了一个叫做背包九讲的直击DP的好东西。对于状态转换和更新十分透彻。这次刷了DPtag下面所有的medium题，产生了一个疑问：DP就是DFS + memo吗？看了看小土刀的面试刷题笔记和动态规划问题总结，DP是bottom up的自底向上解决问题，DFS + memo是top down自顶向下的解决问题。动态与贪心的区别则在于DP会记录所有可能通向全局最优的局部解，而贪心只从局部最优为基础，不考虑全局最优，因此不一定是全局最优解。对于贪心算法，每一个子问题的局部最优解只取决于当前的状态，不能够用来求最大值最小值问题。这个动态规划总结也非常值得参考。
线性结构
1d - DP, 状态的排布是一个1d的数组。很多很常见和基础的dp题都是线性的。这样优化空间之后一般是O(N)的时间复杂度和O(1)的空间复杂度。这类题比较显著的特征是当前状态只与前一个状态有关，并且所求解为走到最后一步的极值。
区间结构
2d -DP，状态排布是2d的数组。优化空间后一般是O(N * N)的时间和O(N)的空间。这类题目一般是当前状态和前面的所有状态都有关，并且所求为某一种条件下的结果之和或者需要在所有的局部最优解中寻找一个全局最优解。我刷过的大部分的DP medium都是这一类。
树状结构
很多跟tree有关的更新也没有什么特殊的，左右节点分别保存状态就好。
Tricks & Math
Minimax
Minimax是DP的一种算法，叫做极小化极大算法，简而言之就是一种找到最大可能性中最小值的算法。
Greedy
局部最优子结构。Dijiksra。Two Pointer的方法也能解很多题。
Find Permutation, 突然不会了，看了讲解应该是一个简单的题orz
Binary Search
主要是明确了Binary Search要写成左闭右开的形式。这篇知乎讲的太好啦，这位答主靠这一个答案就得到了2k赞。如果搜索的第一个大于等于target的值不存在就会返回array.length，十分合理。用了这种写法之后省去了之前写成闭区间时最后一步还要判断的麻烦。
public int search(array, left, right, target) {
while(left < right) { // 左闭右开，代表搜索区间存在
int mid = left + (right - left) / 2; // 防止left + right溢出
if(array[mid] < left) { // 寻找第一个大于等于target的，寻找大于则取等
left = mid + 1;
} else {
right = mid; //
}
return left; // 此时left == right
}
有意思的题：
Find Duplicate Number, 当然可以sort，但是用Floyd算法可以O(N)完成，相当于linkedlist找环。
Median of Two Sorted Arrays, 到了边界真的太容易错了。
Kth Smallest Element in BST, 不论哪次看到我都想traversal。用Stack实现会快一点。
Sampling
这边遇到了几个以前没见过的sampling方法。
Reservoir Sampling
水塘抽样是一系列的随机算法，其目的在于从包含n个项目的集合S中选取k个样本，其中n为一很大或未知的数量，尤其适用于不能把所有n个项目都存放到内存的情况。是O(N)的算法。
Begin
define output array of size [k]
copy k first items from array to output
i = k
while i < n, do
j := randomly choose one value from 0 to i
if j < k, then
output[j] := array[i]
increase i by 1
done
End
Rejection Sampling
拒绝采样，拒绝采样基于以下观察：在一维中对随机变量进行采样，可以对二维笛卡尔图执行均匀随机采样，并将样本保持在其密度函数图下的区域中。
Begin
i = 0
while i != N, do
x_i ~ q(x)
u ~ Unif(0, 1)
if u < p(x_i) / Mq(x_i) -> M is appropriate bound M > 1
accept x_i
i = i + 1
else
reject x_i
done
End
Implement Rand10() Using Rand7()
Generate Random Point in a Circle
Union Find
我学Union Find，千千万万次。这次写并查集曾经写错过路径压缩。没什么特别的，不会并查集我不是人。有时候会不太好想到用并查集来做，比如这个Evaluate Division。
Quick Find
Root is id[i], flat tree.
public class QuickFind {
private int[] id;
public QuickFind(int N) {
id = new int[N];
for (int i = 0; i < N; i++)
id[i] = i;
}
public boolean find(int p, int q) {
return id[p] == id[q]; // O(1)
}
public void unite(int p, int q) {
int pid = id[p];
for (int i = 0; i < id.length; i++)
if (id[i] == pid) id[i] = id[q]; // O(N)
}
}
Quick Union
Root is id[id[id…]]] untile id doesn’t change. Tree is not necessary flat.
public class QuickUnion {
private int[] id;
public QuickUnion(int N) {
id = new int[N];
for (int i = 0; i < N; i++) id[i] = i;
}
private int root(int i) {
while (i != id[i]) i = id[i]; // O(depth(i))
return i;
}
public boolean find(int p, int q) {
return root(p) == root(q); // O(depth(p) + depth{q})
}
public void unite(int p, int q) {
int i = root(p); // O(depth(p) + depth{q})
int j = root(q);
id[i] = j;
}
}
Improvements
Weighted: merge small tree into larger tree. M union and find N object, O(N + MlgN).
// unite - depth is at most lgN
if(sz[i] < sz[j]) {id[i] = j; sz[j] += sz[i];}
else {id[j] = i; sz[i] += sz[j];}
Path compression
M union and find N object, O(N + MlgN). Combine with weighted get O((M + N) lg* N)
public int root(int i) {
while (i != id[i]) {
id[i] = id[id[i]]; // path compression
i = id[i];
}
return i;
}
Sort
排序算法能不会吗，不能。但是我还是忘记了，复习一下。如果有桶排序，堆排序，快选这种可能不是很熟练。
Kth Largest Element in an Array QuickSort 我一般喜欢把随机选择的数字放在末尾
Topological Sort
Tree
Tree这边大部分都是和recursion结合。以及dfs和bfs，根据遍历的要求进行实现。
Graph
Binary Indexed Tree & Segment Tree
我真的不成功便成仁。