7月缺米的来刷题/Mock interview活动

7/12 打卡第12天， 刷了3道题

29. Divide Two Integers
二分法， divisor += divisor, 或divisor <<= 1

73. Set Matrix Zeroes
用第一行和第一列记录需要清0的行和列

155. Min Stack
用两个stack, 其中一个记录最小值

今天刷的不多，不过题目都还蛮有意思
Missing Ranges ：
分成array 左边，array中间，和array右边比较好；不过需要注意处理重复元素的问题

Next Closest Time：
很奇葩的题目，dfs 四个char的位置，注意进入下一层dfs的时候剪掉在时间上不可能的就可以。比如第一位不能大于2，前两位不能大于23，第三位不能大于5，最后两位不能大于59. 虽然看起来很麻烦，要分别Integer.parsInt() 来处理。

Maximize Distance to Closest Person：
刚刚做的时候理解错误了，以为要返回应该坐的位置的Index。不过可以变成一个比较好的followup

Backspace String Compare：
几天前刚刚做完。Stack比较好想，不过followUp O（1）space的情况，还要多看几遍才能记住；

day7
今天没什么时间，先做了个word break继续之前学的backtrack，花了挺久然后该睡了明天要上班了，做几个没那么难的。果然都很快。 BST的题一般都不难，insert node题目一看discussion全都是把新node放到leaf没有人swap的

今天主要刷了跟图相关的算法。

7.12 打卡
1. Minimum Difference Between Largest and Smallest Value In Three Moves.  Sort 原数组，只有四种情况，最小的（0， 1，2，3）和最大的（3，2，1，0）个数被change，在这四种里面找最小的。
2. Range Sum of Sorted Subarray Sums. Pq记录以每个数为subarray起点的sum.
3. Find Root of N-Ary Tree. 常规图轮的入度的问题。Follow up值得注意。要求O（1） space. 因为每个数都是唯一的，从而想到所有数的和减去有入度的数的和就是没有入度的节点，也是根结点。

Day 2
1. #747. Largest Number At Least Twice of Others (a) Traverse once to find the max and secMax, then compare max with double secMax O(N) & O(1)
2. #66. Plus One (a) Simulating arithmetic computation process: loop through each digit and compute sum and carry, insert leading 1 as needed O(N) & O(1)
3. #498. Diagonal Traverse (a) Even and Odd traverse: compute stating position, push back, and change position O(M*N) & O(1)

0712 前几天忘了打卡忘了多少天了，大概是 Day 10， 把这几天的都记录一下
152. Maximum Product Subarray
dp做法，同时keep一下最大值和最小值，每次乘法之后取大的。这个题有个特殊做法，因为任意一点开始往两边乘法，左右两个正数都要，两个负数也都要，一正一负肯定要一个。所以肯定有一边到头。所以直接可以从两边做乘法比较，遇见0重新开始。


380. Insert Delete GetRandom O(1)
挺好一个题。用了hashmap存 value 到key映射，用list存了value，然后每次delete把要删除的swap到最后，然后删掉结尾。东西多了容易乱，起名字comment都写清楚一些。

356. Line Reflection
这个题第一遍自己写的很麻烦，求这个miror值搞了半天。其实keep一个最大最小值就行。然后用map按照y（key）来存很多x（set）值，每个set里找有没有对应的就行。


43. Multiply Strings
我做了个模拟我们手动算乘法的方式。写的有些麻烦。最后看答案，把每次相乘单独弄个String（这个是大数算数的精髓，随时要存成string），然后想加单独做个method，很清楚。

289. Game of Life
第一遍单独存了个matrix记录邻居数量。follow up是用 0 1 2 3 存上轮和下轮的信息。如果超大board就是一行一行来。

1110. Delete Nodes And Return Forest
好像是重写了一遍。就是postorder搞一下，recursion的时候，不用void 用treenode保持关系，用boolean isroot看加不加root

276. Paint Fence
看着是个简单，我听着歌瞎写。。。然后就懵了。道理倒是简单，其实是个dp，就是存两个dp arr一个是same 一个是dif每次往回看的时候same看dif，dif看两个。跟house robber差不多

417. Pacific Atlantic Water Flow
挺老一个题。就是从边上往中间bfs，keep两个visited，然后看都visited的加进res

381. Insert Delete GetRandom O(1) - Duplicates allowed
跟上面1110 很像，这次map里要存set因为有dup了，然后用了iterator().next()来随便找一个。。。

849. Maximize Distance to Closest Person
我写了个简单的从左一个while循环计数找到第一个1，从右一个while循环找到第一个1，然后中间的for循环找到最多的0，然后三个值比较

159. Longest Substring with At Most Two Distinct Characters
经典的sliding window，复习了一下。这个讲的时候要说清楚，是brute force，每个值都要查所有，但是发现查到一个程度就不用查了，然后发现可以用sliding window。最后出while循环要小心别弄错了

158. Read N Characters Given Read4 II - Call multiple times
题读了半天。。。其实就是用小容量buffer读string。每次要查容器里空了没，没空就先copy，空了再来四个。

269. Alien Dictionary
重做老题。topo sort做的，用了个indegreeMap，bfs减法，到0入q。

284. Peeking Iterator
就是call一次next然后存下来。每次用到next的时候看看这个存了没，存了就用存的，没存就叫next。follow up要extend成所有类型，不能用null作check了，所以用个boolean标记一下应该ok

1345. Jump Game IV
挺简单个bfs，就是检查个前后。中间用了个list.clear()清空了map里用过的list，gc做了一下才能过。

45. Jump Game II
jump game 1 用的从后往前标记谁能到最后，这个一样的方法tle。用了greedy,从前往后，keep了一个currMax，一个nextMax，一个idx指针，idx一步一步走，到currMax之前不断更新nextMax，到了currMax之后跳到nextMax，这时候step++。Greedy真是没一道能写出来的。。。

7.12 打卡  LC * 2
这几天在复习视频 刷题进度有点慢

上班写了三道题；
bucket很简单很实用的方法，总忘。。
写组合数的时候recursion效率太低，公式法要注意用long不然很容易溢出

日期: 7/13/2020
题目: [3]
100. Same Tree
1508. Range Sum of Sorted Subarray Sums
1510. Stone Game IV