缺大米的请参加这个刷题/Mock interview活动

打卡第四天刷了3个medium题
（版主前三天都没加米，第一天在1053楼，第二天在1111楼，第三天在1166，谢谢）

day 15
三道BST 巩固了inorder 的知识
nextLevel 这种赋值真好用

2020年6月17日，第十六天发帖，今天刷了7道题：

403. Frog Jump。这是一个DP，state定义为某一个石块所在的位置可以从前面哪些石块的位置跳过来，最后检查最后一个石块是不是对应着一个空集。虽然标记为hard，但是个人认为在DP里不算是很难的。注意这个题目比较特殊的worst case时间复杂度是O(N sqrt(N))。
399. Evaluate Division。这道题乍一看是数学问题，还想着通过强行给各个变量赋值来做，不过后来发现这样操作在引发冲突的时候不好自我纠正。所以它本质上有点像加权的图的问题，而且互相连通的几个节点里两两之间都是可以有一条边的，而且这条边的权重取决于其它边的权重。于是把图抽象为一个map：{节点 -> {节点 -> 权重}}，由input建好图，然后用dfs来寻找每个query的path，同时也计算着不存在的边的权重值，这就提供了memory。只是一开始的时候去重没做好，没有使用visited数组导致了死循环。然后用了visited数组又会发现由于从不同的起始节点开始计算的时候，可能会出现某两个节点之间的连通性由连通错误地判定为不连通，结果还被保存上了。前前后后花了一个多小时才AC。
642. Design Search Autocomplete System。用了字典树和最小堆，为了方便理解和封装还用OOD写的。题目本身并不复杂，只是OOD需要写的代码太多了，还遇到了很多小bug，最后花了快2个小时才AC。
496. Next Greater Element I。这是我在LC上见过的表述得最差劲的问题了。本质上是问一个元素在一个array之后的next greater element，并用不同的input重复多次。如果直接brute force就是O(N^2)，但是在使用了map和栈之后可以简化一部分问题，使复杂度落在O(N)和O(N^2)之间。
320. Generalized Abbreviation。这个题由于每一个字符可以相互独立地简化或者不简化，让我瞬间联想到boolean数组，同时可以用binary integer来表示。于是从0循环到2^N - 1，每一位字符由其对应位置上的bit来决定是否简化。然后把相邻的简化的字符用数字代替。
8. String to Integer (atoi)。这个题感觉就是在考人寻找edge case的能力。遂写完代码之后自己写了一些edge case：超级大的数，超级小的数，数字前面有俩正负号，数字后面紧跟着各种符号，等等。
388. Longest Absolute File Path。我的做法是先把每个namespace和每个\n及\t分割开，通过stack来跟踪当前的namespace，如果遇到了文件就更新一个maxlength变量。

总结一下：
0. 今天又复习了一下进阶级的正则表达式。
1. 由除法题想到的：对多个元素之间的相对关系建模，首先考虑无向图。而无向图可以用双向的有向图来模拟。
2. 由trie题想到的：面试时和面试官做好沟通，商量清楚如果代码量太复杂用正常速度写不完，是要牺牲代码质量还是牺牲速度。
3. 单调栈增减元素元则可以有很多：比如单调递减栈，直接忽略更大的元素可以找到数值上next greater element，而一有大元素就一直pop栈顶可以找到位置上next greater element。顺便提一句：最小堆则只能找到数值上next greater element。

Day 11

4 problems today

Day 16，刷了四道题，三道新题：

Minimize Max Distance to Gas Station        LC 774
Find the Smallest Divisor Given a Threshold        LC 1283
Recover a Tree From Preorder Traversal        LC 1028

这周集中攻克二分答案类型。发现了medium和hard二分答案题的套路。经验是，还是要跟着大神的思路多刷。本周做的题都是contest一个大神题解里列的推荐题目。

1. Recover a Tree From Preorder Traversal是每日一题，其实挺简单的，preorder serialized，就用preorder serialized回去，用stack实现。后一个节点either是前一个节点的左孩子 or [root, 前一个节点)路径上某个节点的右孩子。可以获得当前节点的深度和值，根据深度和当前stack的高度比较，确定是两种情况的哪一种。如果相等，直接给栈顶节点装上左孩子。后者，pop到深度相同，给栈顶节点装上右孩子即可。两种情况都要入栈，模拟递归时继续向下递归的操作。

2. medium和hard的二分答案是有套路的。medium一般只有一层，比较straight forward。hard的二分答案，typical signal一般是minmax value or maxmin value。看到这种除了dp，可以想下二分答案是否work。二分答案一般是用mid = 要求的答案，f(mid)和题目给定值比较，根据比较结果进行二分。hard的难点在于，minmax value要求f(mid)要满足内层极值约束(最大子数组和/最低甜度/最远距离)。思考思路一般是，找到一种分法/切割法/设置法，满足内层极值约束(最大子数组和/最低甜度/最远距离)<=或>=题目要求的外层极值约束。比如我要找maxmin甜度，就是找到一种分法使min甜度 >= x，那么对于所有y < x，可以不予考虑，即被二分掉。一般是f(mid)这个函数给出一个估计值，用这个估计值与题目给定的约束(分成m块)比较，以此判断能否满足外层约束。

3. 加油站那个题有特殊之处。一个是答案可以是小数，所以mid = (start + end) / 2。另外答案是个估计值，所以循环条件是while end - start > 1e-6

17 天 3 题

Day 1 - 6道：主要刷dfs
102        二叉树的层序遍历
107        二叉树的层次遍历 II
637        二叉树的层平均值
993        二叉树的堂兄弟节点
103        二叉树的锯齿形层次遍历
130        被围绕的区域

06/17/2020， Day14
今天刷了3道题。

求楼主看过来看过来 加米 :)

第一天   之前连刷几天结果昨天中断了