LeetCode 刷题冲刺+逐题总结

到‍‌‌‍‌‍‌‍‌‌‌‌‌‍‍‌‌‍前天正好刷了600整，不过hard的比例也就刚刚15%还是感觉有点少...现在算是个人的冲刺阶段了，建个帖子激励一下自己~
目标：暂时是每日>=7道新题（其中不少于3道hard) 加上>=5道二/三刷的题，新题随机刷老题按类型刷。如果后面剩余题少了之后再逐渐调整比例:) 另外每天做的所有题都做一个简短的总结加深印象

Don't dream your life, but live your dream.

（第一个帖子发出去才发现主贴各种问题还不能修改Orz，这里顺便求版主把上一个打卡帖删掉~

今天（0930）的话看了国庆阅兵，感觉身为一个中国人自己很自豪。不过题做的相对比较少，满打满算就三道题加上做了一下Linkedin的Python技能测评（还好通过了，不然还得等三个月zzzz）
总结的话今天跟昨天的合并在明天写好了~（差不多这两天的量能凑够一天的总结），以及明天就进入十月份了，做题要再加速了！

今天的contest出人意料的友好...在跟人约饭回来晚了十几分钟的前提下都挤进前200了hhhh
Trie刷完了今天彻底总结一下，一些落单的题（就是brainteaser或者顺手做的那些题）跟今天的contest就明天合并总结一下好了
Trie collection: 总数 - 17
一句话总结：trie能做的用hashset基本都能做，trie的优势在于对prefix/suffix大量处理时空间利用率更好。以下同难度题目以frequency高到低排列

Hard: 7
336. Palindrome Pairs
naive解法O((n^2)*k)，用trie或者hashset考虑每一个string可能的pair是什么，可以把复杂度优化为O(n*(k^2)). 看评论区似乎还有复杂度更好的方法，但是觉得以找工作为导向的刷题的话掌握到这里就可以了

212. Word Search II
dfs + trie/hashset

642. Design Search Autocomplete System
个人比较喜欢的一道题，常规TrieNode结构上还需要加入countList(countDictionary)及top3 list （这个top list答案里没有提，但是加上会省去每次单独找top3的mlogm复杂度）。想要bug free的话对代码功底有一定的要求

472. Concatenated Words
trie + dfs + memo - trie的目的是找下一个可能满足的单词；dfs不用说，memo是优化时间复杂度（因为memo一共最多只有n*k个状态，n为总单词数k为每个的长度，因为时间复杂度至多为O(nk)）.

1032. Stream of Characters
Trie + Queue/Array，每次Insert把queue里面的每一个node都向下移一个位置（不能则扔掉），最后看queue里有没有东西以及如果有的话有没有word。

425. Word Squares
这题刚开始做的时候想多了=.=过于贪心以至于钻了一阵牛角尖。其实就是更有效率的遍历 - 每一次都只考虑prefix对的上的candidate.

745. Prefix and Suffix Search
个人比较喜欢的一道题 - 这题如果按照给的条件的话并没必要用trie做 - 直接一个hashmap存prefix suffix pair - maxvalue然后每次直接O(1)取值就好了。用trie的话把part of suffix + prefix存成trie，然后每次从trie找也是比较巧妙的做法。

Medium: 8
421. Maximum XOR of Two Numbers in an Array
好题强推 - 联想到用Trie来做真是很需要一定功力，评论区里的mask + bit manipulation的方式也非常经典，个人觉得属于trie分类下必看的一道题

208. Implement Trie (Prefix Tree)
没啥，trie的定义...

692. Top K Frequent Words
好题强推 - 这道题一刷的时候没去想trie的解法，直接用heap做的O(nlogk)，这次二刷意识到，bucketsort下每个bucket建一个trie，辅以合适的input (每一个节点记录一下后面有几个以及都有谁)，可以做到O（n+k）复杂度。

211. Add and Search Word - Data structure design
也是trie基本定义

648. Replace Words
trie的一个经典用例

677. Map Sum Pairs
凡是涉及prefix/suffix的可以把trie当作常规武器之一~

676. Implement Magic Dictionary
trie + dfs，把犯错次数当作一个变量。注意必须替换一个，完全一致也不可以。

1023. Camelcase Matching
这道题是真的没什么用trie的必要，two pointer就行了，注意一下第二个string是可以大小写混杂的

Easy: 2
720. Longest Word in Dictionary
建trie然后找最长全True路径 （trie+dfs）.

1065. Index Pairs of a String
也是不用trie就可以做的一道题（thanks to O(1) "in" operation in Python)，如果用trie的话对每个long string里的位置在trie里找，找到就输出（自然满足sort要求），找不到就退

写这个总结写了一个多小时...又是没看SQL的一天...明天打算暂停刷题一天，专心准备一下SQL和bq相关的东西~

今天contest那个服务器我不想说什么了...把心态搞崩了，最后一道题罚了5次时才改对...第三次错过前100zzzzz
话不多说，上题上题
（同样也是挑看过的觉得有必要总结一下的放在这里~）
Hard: 9
315. Count of Smaller Numbers After Self
327. Count of Range Sum
493. Reverse Pairs
异曲同工之妙的三道题，利用merge sort这个过程来进行计数以达到O(nlogn)复杂度，会一道=会三道

644. Maximum Average Subarray II
二分法找k (O(logn))，然后判断这个k满不满足条件（O(n)). 这题的思考过程是，直接去求这个k并不只管，但是判断这个平均值k有没有可能达得到是很直观的((num-k)>0)的sliding window解法）。说到底就是把未知问题化为已知问题，虽然这句话说起来容易做起来并不容易23333

774. Minimize Max Distance to Gas Station
这道题也是，昨天看就是秒了的，今天第一反应就是错的... 我看答案有个词用的很准确，"trial and error" - 和上题类似，也是先取个值然后看这个值行不行 - 直接算值很难但是判断取值可不可行很容易，就是这个道理

778. Swim in Rising Water
这题两种解法都不是那么直观需要一些思考 - 第一种是对下一个最低点建heapq (其实就是迪亚克斯拉)，当到达终点时遇见过的最大值即为所需时间；第二种依然是trial and error，两种都是O（N^2logN)

862. Shortest Subarray with Sum at Least K
Sliding window一个典型用例

4. Median of Two Sorted Arrays
好题强推，lc前200值得刷5遍真的名不虚传，找到中间index pair然后binary search真的经典

301. Remove Invalid Parentheses
简而言之是backtrack, 个人很推崇评论区里面dietpepsi的解法，十分推荐去学习一下（大致就是backtrack with pointer，用来避免出现重复的temp result的；另外正向一次反向一次也可以省去对于左括号和右括号的分别讨论）

Medium: 8
1011. Capacity To Ship Packages Within D Days
也是binary search possible space

1060. Missing Element in Sorted Array
这个其实重点在想到用binary search上，想到了就不难了

98. Validate Binary Search Tree
可以铺开成array来判断，也可以recursive返回最大最小值，然后和中间节点来进行判断

105. Construct Binary Tree from Preorder and Inorder Traversal
从preorder/inorder/postorder traversal构建回binary search的都是经典，recursive + global pointer的做法值得多练 - 其实弄明白了的话，这些都是literally根据定义逆推即可~

116. Populating Next Right Pointers in Each Node
学会利用上一层的next pointer为这一层提供便利是核心思路，II也是一样的

261. Graph Valid Tree
这题的一个陷阱就是，不能直接判断是否有n-1条边，必须n-1条边并且全联通才可以。

417. Pacific Atlantic Water Flow
经典的两边向中间逆推的题

513. Find Bottom Left Tree Value
bfs，关键是注意审题 - 不是最左端而是最底层的最左边的leaf

于是第一天比例其实就是有问题的=.=，好在总数还是及格了，明天继续加油！

总数：12 (10+2)

Hard: 3 (3+0)
1044.‍‌‌‍‌‍‌‍‌‌‌‌‌‍‍‌‌‍ Longest Duplicate Substring
这道题感觉和1062 （Medium, Longest Repeating Substring）没什么太大区别，在可能的字符串长度上binary search，再手动写一个hash function (1062不需要，1044需要否则MLE). 评论区有说Suffix array也可以的，不过懒得看了23333

552. Student Attendance Record II
dp就是可以的，不过一个十分巧妙的点是可以转换成0-1矩阵然后exponation by squaring，能把O(n)的运算简化成O(logn)

381. Insert Delete GetRandom O(1) - Duplicates allowed
这题没啥特别的，典型的用空间换时间

Medium:  8 (6+2)
1062上面写了就不再写一遍了

(redo) 61. Rotate List
熟练工种，no brainer... (不过似乎面试还挺爱面这种的)

(redo) 531. Lonely Pixel I
其实是见到了下面那个新题于是顺手把这题复习了一遍，O(mn)就行


533. Lonely Pixel II
很蠢的一道题...不建议浪费时间去做...把有N个'B'的行放一个hashmap/dictionary里，然后再挨列看有多少'B'就行

1120. Maximum Average Subtree
没啥说的，不太配medium，逐层返回sum/count再算就行

525. Contiguous Array
这题属于见过了就很容易没见过还真挺难的那种，技巧就是把0当作-1，然后hash prefix sum就行了

912. Sort an Array
Emmmm，更像是一个playground自己练排序算法的那种。如果想刷题量的话你写个return sorted(nums)都是能过的hhhhhh

1066. Campus Bikes II
heap + bit mask, 做的时候卡bit mask那儿（没想到用bit mask，想的别的东西）卡了好久

Easy: 1 (1+0)
917. Reverse Only Letters
一头一尾俩pointer，遇字母互换即可

又是没全部达成目标的一天...嘛还是先上题吧~

总计：10（9+1）

Hard: 2 (2+0)

218. The Skyline Problem
好题强推，对于题目分析和heap使用考察很到位，有多种做法（我自己是用分interval做的，看到一个（加上自己完善了一下）比较漂亮的解法是直接记录critical point以及到point的时候当前的rec个数，Heap方面用lazy removal处理

857. Minimum Cost to Hire K Workers
相对简单（但也不算白给）的一道hard，分析明白就不难，核心就是按性价比排序，满足性价比的条件下quality低的优先。

Medium: 5 (4+1)

(Revisit) 215. Kth Largest Element in an Array
Quickselect练习题，O(n)复杂度

841. Keys and Rooms
误入Medium的Easy题...一个BFS/DFS就没有然后了

540. Single Element in a Sorted Array
类Binary search，不过边界条件需要格外注意，挺麻烦的

734. Sentence Similarity(Easy) / 737. Sentence Similarity II (Medium)
一个细微条件的差异导致难度完全不同，前者存成一个dic然后查就完了，后者需要DFS或者Union-Find，难倒是不难不过需要熟练度

355. Design Twitter
一道design的题，重点就是把每个人的tweet存成array然后取Update的时候把所有的尾巴存成一个heap

Easy: 3 (3+0)

734上面说过了

371. Sum of Two Integers
误入easy的medium...纯bit manipulation,评论区有bit操作非常详尽的总结

703. Kth Largest Element in a Stream
建一个heap，一直update就好了

今天参加了一下weekly contest，顺便写了两个答案把脑力用光了...于是到现在都还没有一天完整的达成所有目标zzzz
今天做的全部是新题并没有做老题

总计：7

Hard: 3
1192. Critical Connections in a Network
近期亚麻高频题，DFS-Tree，开始的时候不会然后Contest的时候现学的...明白了之后发现其实并不难，但是得反复过不然很容易忘

428. Serialize and Deserialize N-ary Tree
我是用最直接的括号分割来做的，不过用记录子节点的方式做会更简洁

968. Binary Tree Cameras
DP Greedy两种做法，挺有意思的

Medium: 3
998. Maximum Binary Tree II
只要想明白了加入的节点永远在最右这一点，就是很直接的一道树的题

1191. K-Concatenation Maximum Sum
分析比代码重要，K>=2的时候俩数组拼一起找最大之后根据sum(arr)是否大于零来决定输出，挺有意思的一道题

1190. Reverse Substrings Between Each Pair of Parentheses
相对麻烦的一道题，也是分析重于代码本身，recursive相对比较直接

Easy: 1
1189. Maximum Number of Balloons
纯种easy没啥好说的

感觉不能沉迷刷新题呀，老题很多是很经典需要复习的...明天继续加油~

1190 我用的Stack感觉也很直观。

wowmomsos 发表于 2019-9-15 13:17
1190 我用的Stack感觉也很直观。

感觉stack做法和recursive应该不会有很大区别吧，相当于手动实现了一下recursive的过程

周末似乎有点怠惰=.= 接下来几周基本上是决定性的了，加油！
又是全部是新题的一天...

总计：7

Hard: 3
440. K-th Smallest in Lexicographical Order
逐层构造出最终的答案，做的时候观察到了规律但是没想到逐层构造这一点（类似DFS），值得一看

980. Unique Paths III
很莫名其妙的一道题，直接backtrack居然就是解法...

489. Robot Room Cleaner
DFS+backtracking，如果没做过的话很推荐看一下

Medium: 3
311. Sparse Matrix Multiplication
利用sparse matrix的性质hash一下就行了，考察熟练度的

1027. Longest Arithmetic Sequence
一道相对直接的dp题，别多想直接dp做就对了

825. Friends Of Appropriate Ages
看到限定range，bucket sort应该成为条件反射:)

Easy: 1
896. Monotonic Array
我居然想了半天logN的解法，然后没想出来看了眼评论区才发现不要求logN...感觉自己像个憨憨

今天身体状态不是特别好，明天会和今天合并总结~

两天放在一起写果然看起来多一些（其实并没有）
另外解释一下数字，在前面的是新题后面的是复习，比如5+3就是5道新题三道老题

总计：17 (12+5)

Hard: 4 (4+0)
732. My Calendar III （跟729. My Calendar I (Medium), 731. My Calendar II (Medium) 放在一起）
仨题用的是一个东西：segment tree.  JAVA的话有treemap会直接很多，我用的Python就自己定义一下Node，然后手动实现一下树操作。重点其实就是想到利用tree来实现O(logn)的操作复杂度

265. Paint House II （跟256. Paint House (Easy) 放在一起）
如果先做了256的话265的难度就是medium封顶，不过初见还是有一点难度的。也是比较基础的dp

1036. Escape a Large Maze
十分有意思的一道题，因为整个空间太大而block很小（max=200) 我最开始想的是对block做bfs或者dfs看是否把起点或者终点包围住，后来忽然意识到这么小的block size的话能包围的空间也十分有限，那我直接对起点和终点都做bfs，如果每个所处的空间都大于可能被包围的最大空间就说明他们没有被包围（当然提前相遇这种情况就更好了），so that's it. 需要注意如果用面积做判断条件需要算一下面积大小（近似n^2/2，n=len(block))，如果用bfs深度的话是2*n而不是n （这点非常容易错）

329. Longest Increasing Path in a Matrix
好题强推，dfs+dp和topological sort两种解法都很有意思

Medium: 6 (3+3)
837. New 21 Game
其实是一道数学题...把表达式列出来之后发现其实是就是一个dp，不过如果表达式没列出来的话复杂度会多乘一个O(n)。Observation is the key.

556. Next Greater Element III (跟503. Next Greater Element II (Medium)，496. Next Greater Element I (Easy) 一起)
这三道题也是（556不完全一样）一个重要知识点：Monotonic stack: 因为有某种单调性性质，导致在违反单调性的时候可以一直pop知道满足或为空。556的话有用到单调性性质，主要做法是从后往前扫，遇到第一个违反的（set as a）之后再扫一遍找到第一次出现的大于a的数字，然后做交换。同时需要注意判断32-bit条件。

238. Product of Array Except Self
这道做过的题居然卡了一会儿... 其实就是正着扫一遍反着扫一遍

（另外几个跟前面合并了）


Easy: 7 (5+2)
686. Repeated String Match
误入Easy的Hard题，KMP我举得放在easy过于过分了...

171. Excel Sheet Column Number
纯种EZ题，brain teaser

509. Fibonacci Number
比较正常的做法是dp入门题，不过Matrix的O(logn)解法也是挺有意思的，给个medium不过分

有两道前面说过了，还有两道best time sell stock那个系列的打算明天一起进行总结


另外说点无关的，有点意外有人会收藏我这个帖子，高兴之余也是一种激励吧~另外也非常希望投出去还没信儿的几家赶紧给个面试呀>.<

太厉害了，跟着你刷