在职宝妈打卡刷题

不管是电面还是VO，我很容易会写着code聊着聊着思路断掉，忘记考虑一些corner case，发现一个方法很有用，在理解完题意之后，先不要开始写code，先写psudo code + 注释，列出来1，2，3需要考虑的，也可以把主要的框架写出来，尤其是corner case边界考虑，先写出来就不会忘记了。比如 different way to add parenthese这道题：
1. 每一层 for循环，找到symbol
2.base case: nil 返回 / 1 number，添加到list，返回
3. calculate the final value at each layer, add all result to list on the top layer.

1. Word Search II 这道题真的做了超久，差不多两个小时，一开始没思路，后来看了答案用trie + dfs，又想看看最优解剪枝，这个trie其实已经很优化了，但是有个更优化的做法是把所有已经找到的词从trie里面移除，这样就不会重复遍历trie。2. Different Ways to Add Parentheses 用+ - * 来划分level，每层的结果存在map里面，来避免重复提高效率。



补充内容 (2020-5-13 14:16):
3. Minimum Remove to Make Valid Parentheses
4. Find All Anagrams in a String //sliding window
5.Add Strings
6.Add Binary
7.Move 0s To The End I
8.Move 0s To The End II

补充内容 (2020-5-13 16:02):
9.Remove Invalid Parentheses这道题也是调试了两个小时，终于搞完了，corner case特别多，还是需要拆分问题，dfs有两个地方很tricky，一个是先移除右括号，再移除左括号。一个是移除时注意去重，相同元素跳过。

补充内容 (2020-5-13 16:42):
其实还做了一道hard K Closest Points to Origin，但是调试的时候quick sort一直有问题, corner case太多，郁闷的时答案居然也不对，因为quick sort时间上是最快的，但是面试有时候也不需要最优解，差不多jiu xin...

补充内容 (2020-5-13 16:47):
碰到hard的题，corner case还是完全靠调试。。。。

补充内容 (2020-5-13 17:33):
10.Find All Duplicates in an Array
11.Remove Duplicates from Sorted Array II
12.Remove Duplicates from Sorted List

膜拜你...带娃一天还这么高效！楼主之前学过cs吗

我觉得lz真的牛逼。在职带孩子还能每天刷这么多题？我每天啥也不干也刷不到32道

beyondR 发表于 2020-5-13 09:54
我觉得lz真的牛逼。在职带孩子还能每天刷这么多题？我每天啥也不干也刷不到32道

我不是第一次刷了，以前没娃的时候最多的时候四天可以过完前200道，现在每天下班要带娃带2-3个小时，所以只能白天或者半夜刷题。

第八天 今天上午没有刷题，有五个HR phone screen联系安排时间，没消息一起没消息，最后都撞在一起，不过好在都是跟HM对接的hr，拿到phone的几率又大了一点，昨天还有点崩溃拿不到phone，今天突然觉得时间有点来不及了。
今天补一下进度，大部分easy medium没有写，只是过一下思路,只写了几道比较难的medium或者最优解
1. Array Deduplication III
2. Remove Duplicates from Sorted List II/Array Deduplication IV
3.Array Deduplication V
4. Interleave Positive And Negative Elements
5. 2 Sum All Pair II
6. 2 Sum Closest
7. 2 Sum Smaller 这个题很好，先排序，右指针从后往前找到第一个比target小的数，之前的元素相加都满足条件，左指针往后一位，右指针在开始找满足条件的第一个数字，然后循环
8. Two Sum III - Data structure design 用hashmap存count
9.Two Sum IV - Input is a BST
10.3Sum Smaller
11.2 Sum 2 Arrays
12. 3 Sum 3 Arrays
13.Number Of Pairs Diff To Target
14.Different Elements In Two Sorted Arrays
15.Minimum Three Array Distance //这道题也很好，实际上虽然要求找三个数，但事实上不用关心中间值，找大最大最小值差最小的组合就是答案
16.Common Numbers Of Two Sorted Arrays
17.Smallest Range 和15很像，不同的是因为有K个list，需要一个priority queue来实现最小元素的剔除，siliding window的方法展示没想到怎么解
18.Number Of Negative Numbers In Sorted Matrix
19.Common Elements In Three Sorted Array
20. Max Sum Of Two Indices
21. String Distance
22. Majority Number I
23.Majority Element II 空间复杂度O1，存两个值，遇到不同同时-1，最后要在检查一遍
24.Majority Number III 直接上哈希表

第九天，今天是string类型题
1. Remove Spaces
2.Reverse Words in a String II
3. Reverse Words in a String有个非常简便的写法：
var str = s.split(separator:" ")
        return str.reversed().joined(separator:" ")
4. Remove Certain Characters
5. Right Shift By N Characters
6.Reverse String
7. Reverse Only Vowels
8. Determine If One String Is Another's Substring 这道题先只做了两两对比，KMP的解法更优化但是没有写
9. One Edit Distance 这道题本身不难，但是要注意如何简化，其实两个string的长度就暗示了删减的时候只能从长的里面删除，所以只有两种情况，相同长度碰到不同字母同时跳过，不同长度碰到不同字母，长的字符串指针进1
10.String Abbreviation Matching
11. Longest Valid Parentheses非常好的题，用stack存（的位置，然后通过计算位置差来计算最大的valid parenthese
第二个方法空间复杂度更优，是从左边遍历一边string，如果右等于左，则此时更新count + 2*right，再从右往左扫一遍，当左等于右更新count，取最大结果

第九天，所以今天打得又lost了吗。。。今天看了string的几道题，一共11道，一亩三分地太容易lost了，我以后还是把做的数量发上来，具体的题就记笔记好了，今天又有五个HR联系，大概之前发简历发的太多了，拿到了一个HM电面和一个general 电面，大概都在一个月以后，要加油了啊，感觉还不是很ready。

补充内容 (2020-5-15 14:48):
12.String Compression
13.Decompress String I

补充内容 (2020-5-15 15:03):
14. Isomorphic String I 刷完了string最后一道简单的题，明天开始全是hard。。。。

第十天
1.word pattern II //dfs
2. Remove Duplicate Letters
3. Shortest Palindrome
4. Palindrome Pairs
5. Count of Smaller Numbers After Self
6.Find Smallest Common Element in All Rows

补充内容 (2020-5-16 05:36):
今天又收到某厂发的面试，某厂这个面试体系，一周面一次都够了，职位都在ca，准备拿来练练手，已经面了一个组了，还有两个组的电面排在剩下的两周。第一次的确面的不好，但是感觉第二次再去聊就好很多了。

补充内容 (2020-5-16 06:31):
7.Insert In Binary Search Tree
8.Search In Binary Search Tree
9.Delete In Binary Search Tree

补充内容 (2020-5-16 07:08):
10.Closest Number In Binary Search Tree
11.Largest Number Smaller In Binary Search Tree
12.Second Largest In Binary Search Tree
13.Kth Smallest Element in a BST

补充内容 (2020-5-16 07:38):
14.Closest Number In Binary Search Tree II 这个题只看懂了暴力解，two stack的时间复杂度并不觉得有优化，空间复杂度有一定优化。
15.Get Keys In Binary Search Tree In Given Range

补充内容 (2020-5-16 14:28):
KMP的解法作为最优解，KMP table的code很难在面试的时候写出来，所以打算暂时用暴力解来解找word pattern的题，如果需要优化就提一下如何用KMP table来进行优化

第十一天
今早起床考虑了一下，发现昨天14题的comment十分反智，又考虑了一下two stack的解法，发现就是morris traverse，于是重新又看了一遍，时间复杂度和空间复杂度的确最优。
又一道hard题调试了半天，打算刷完hard去找娃玩一会，晚上再回来继续刷。

补充内容 (2020-5-17 11:34):
我发现hard的题有的时候看了答案，写一遍，调试完，也不能说就完全吃透理解了这道题。而且随着以后hard越刷越多，前面的hard解法也许慢慢就忘了，尤其是一些corner case

补充内容 (2020-5-17 11:35):
所以今天花了一些时间，总结了一些自己做过的hard的题，录成讲解视频发在自己的youtube里面，作为学习笔记，尽量精简，把重点和需要注意的corner case提出来，方便以后复习。

补充内容 (2020-5-17 13:21):
1. Transform Binary Search Tree To Greater Sum Tree
2. Reconstruct Binary Search Tree With Preorder Traversal
3. Reconstruct Binary Search Tree With Postorder Traversal

补充内容 (2020-5-17 13:22):
4. Reconstruct Binary Search Tree With Level Order Traversal

补充内容 (2020-5-17 13:23):
今天把BST看完了，BST是面试当中的重点，所以需要看的仔细一些，另外用two stack重写了下昨天的14题