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

Day 19 三道题

赞一个，给你点个赞， 棒棒哒

2020年6月19日 第十八天发帖：

今天面试了开花堡第二轮电面，面经随后会发：

除此之外今天刷了6题，因为下周二电面易北，全部是地里他们的面经及衍生题：

107. Binary Tree Level Order Traversal II。DFS配合map，可以用任意order traverse树，然后按照level从底到顶输出。这个题也可以用BFS做。
102. Binary Tree Level Order Traversal。这个题只是把输出顺序反过来，于是拿着道题试了一下BFS。
103. Binary Tree Zigzag Level Order Traversal。这个题我的想法是：用一个变种的BFS，只不过在奇数层的时候从队列尾开始输出而把新节点加在队列首，同时优先输出右子节点而非左子节点，偶数层照常输出。这个题也可以用DFS根据层数来选择把新节点放在list首还是尾。高票答案中有一个用两个stack的方法，其实本质上很BFS没啥区别，只是他一个while loop会处理两行node。
137. Single Number II。常规用O(N)的方法不难，设置一个total，用set来track一个数字是否出现过，如果是就给total加上两倍的数，否则减掉这个数，最后剩下的数除以二就是答案。位运算的做法我真的是想不出来了，我甚至觉得如果面试时一上来就给这个解法肯定会被面试官认为我背了题。
260. Single Number III。常规做法就是用一个hashset，没出现过的数加入，出现过的数拿走，剩下的两个数就是答案。位运算的解法我表示也是打死都想不出来。
238. Product of Array Except Self。这个题目让我瞬间想到了验证左括号右括号的那道题和presum这种策略，于是自己用一个数做preprod，从左向右乘一遍，再从右向左乘一遍就可以了。

总结一下：
1. BFS遍历树可以逐层渐进。
2. 一些位运算的小技巧：x & (-x) = (x 最低的一位1为1，其他位为0的一个数）；x的相反数：~x + 1；计算一个二进制数x里有多少个1：不断操作x = x & (x - 1) 直到为0，统计操作次数；只有异或运算同时满足交换律及结合律，或、与运算都只满足交换律。
3. 面试时除非面试官特别要求，只在followup的时候上非常tricky的位运算，以避免背题嫌疑。

action item：
继续刷一些位运算的题目。

Day 18, 刷5道题，3道新题：

Longest Duplicate Substring        LC 1044
Add Strings        LC 415
Valid Word Square        LC 422

1. Longest Duplicate Substring和LC 1062是一样的，二分答案 + Rabin Karp。一定要记得在初始化h的时候就module 2 ** 32！这个bug导致我调了好久。LC 1062也是有问题的，少了一个测试用例，错误的代码也能通过。

2. 正则表达式匹配的两道题。区别在于，通配符匹配中的*是独立存在的，可以不依赖于之前的字符串代表任意字符串，所以dp[i][j] = dp[i - 1][j] or dp[i][j - 1]。正则表达式matching，*是依赖于前面的字符，不能独立存在，所以都是和j - 2比较。

3. Valid Word Square，记住有可能缺位的情况，要判断一下len(words[j]) > i。

打卡第一天~

2020年6月18日 第十七天发帖：

因为连续两天面试时间比较紧，于是刷题数量变少了。这一天刷了3题：

694. Number of Distinct Islands。本题和200的区别在于要记住岛的形状，于是就需要记录BFS或者DFS的路径。我一开始的想法是用BFS同时记录下相对的坐标位置来表示岛的形状，当然也写出来了，不过一个单元格要用至少两个数字来表示。后来看了答案，最佳方法是用DFS，而且只记录方向，这样每个单元格只需要用一个表示方向的字母就可以了。
1247. Minimum Swaps to Make Strings Equal。这个题我在做的时候我并不知道它是greedy，但是我却总结出来了这个规律然后用它把答案做出来了。
1094. Car Pooling。又是一个interval系列题。这个问题难点在于我们需要同时知道一个排好序的上车点和一个排好序的下车点，所以这个时候两个minheap其实是比较好的方法。我用的方法是：先把原数组按上车点排个序，再copy一个数组按下车点排个序（提交了一次答案之后才意识到不这样做就错了），这样有很多冗余的内存。答案则借助了上下车点数量最多1000的限制，直接用了一个长度1001的数组来记录每个点“净”上车的人数（上车人数-下车人数，可以是负的），然后从左到右依次相加，如果曾经超过了capacity就不可以。所以如果不按照interval的套路去做，才能想到这一点。

总结一下：
1. BFS和DFS通常都能解决图的遍历问题，但是BFS强调当前位置与原点的距离，而DFS强调从原点到当前位置的行走方向。
2. interval类问题自己之前做都喜欢把左右边界写成OOD然后放进一个heap里，用一个enum来区分它是左边界还是右边界，其实可以用两个heap分别保存左右边界，省去了大量创建自制object的内存。当然，如果面试官喜欢OOD的话还是要上OOD。

06/19/2020， Day 16
今天刷了4道题。

6.19 day 21
继续js
3 学习set用法
5学习string slice用法，此外又复习了一遍Manacher's ALGORITHM，非常巧妙的思想，但似乎只能用在这题，目前还没找到更多的应用
8 parseInt就很方便，同时也复习了regex

打卡第18天， 刷了3道题

21. Merge Two Sorted Lists
while l1 and l2: 比较并合并。 然后head.next=l1 or l2

85. Maximal Rectangle
dynamic programming. (right-left)*height 对每个i，j，动态更新left, right, height

138. Copy List with Random Pointer
用hash-table， map(node) = node_copy

day12  6道题
968. Binary Tree Cameras        dp, state initialization not easy to think of.  or greedy  dfs if any son not covered, then put a camera here,  if root  and not covered, set a camera
519. Random Flip Matrix          
522. Longest Uncommon Subsequence II       
523. Continuous Subarray Sum       
524. Longest Word in Dictionary through Deleting  index or two pointers       
692. Top K Frequent Words