8月刷题/Mock interview接龙活动（缺米刷题的来）

Day 11

274. H-Index, sort or counting sort
1123. Lowest Common Ancestor of Deepest Leaves, post order traversal

8/11 打卡第8天
274. H-Index 排序的话很直观，优化到O(N)的话需要加一个count数组
819. Most Common Word 处理一下原字符串然后用hashmap存储word出现的次数就可以
937. Reorder Data in Log Files 这个题一开始真不知道怎么排，看了答案就是自己实现一个comparator，长知识了

8/11 打卡第11天， 刷了2道题

57. Insert Interval
双指针，i_small 和 i_large
i<i_small, intervals[i] 的所有数都比newInterval[0]小, intervals[i][1]<newInterval[0]
i>i_large, intervals[i] 的所有数都比newInterval[1]大, intervals[i][0]>newInterval[1]
result = intervals[:i_small] + intersection + intervals[i_large+1:]
如果i_small<=i_large, intersection = merge(intervals[i_small:i_large+1], newInterval)
否则, intersection = newInterval

274. H-Index
用了两种方法
第一种对citations排序，O(NlogN),
index从0开始，如果citations[i]>=N-i, N-i就是H-index

第二种方法用bucket sort，index 是引用数，value是有这个引用数的文章数， O(N),
然后index从N开始倒着累计引用总数，如果总数大于index，这个index就是H-index

8/12 主要dfs

5 minutes ago        All Possible Full Binary Trees        Accepted        3 ms        java
6 hours, 44 minutes ago        Longest Univalue Path        Accepted        2 ms        java
6 hours, 47 minutes ago        Longest Univalue Path        Wrong Answer        N/A        java
6 hours, 48 minutes ago        Longest Univalue Path        Wrong Answer        N/A        java
7 hours, 16 minutes ago        Trim a Binary Search Tree        Accepted        0 ms        java
7 hours, 20 minutes ago        Trim a Binary Search Tree        Wrong Answer        N/A        java
7 hours, 24 minutes ago        Trim a Binary Search Tree        Wrong Answer        N/A        java
7 hours, 28 minutes ago        Trim a Binary Search Tree        Wrong Answer        N/A        java
8 hours, 1 minute ago        Two Sum IV - Input is a BST        Accepted        3 ms        java
8 hours, 12 minutes ago        Two Sum IV - Input is a BST        Wrong Answer        N/A        java
8 hours, 23 minutes ago        H-Index        Accepted        18 ms        java

8.12 复习parentheses类题
key word: parentheses
难点：
1.判断valid parentheses -> cnt = 0, 遇到左括号加一，遇右括号减一，cnt<0 或结束迭代时cnt != 0 说明invalid parentheses
常用技巧：stack, backtracking, dfs

8/11 刷了6道题 :)

Basic Calculator I/II

day 11打卡：今天终于把binary tree的题扫了尾。明天开始下一个类型。

求加米，必回加。一起加油！

今天刷了5题 主要研究了下滑动窗口的问题