转型刷Leetcode记录帖

double heap的套路295+480

- 10/19
    - 532E. K-diff Pairs in an Array
        - hash
    - 295H. Find Median from Data Stream
        - double heap
    - 480H. Sliding Window Median
        - a lazy remove heap design
    - 826M. Most Profit Assigning Work
        - binsearch. {buggy} notice lower cost might have higher reward
    - 901M. Online Stock Span
        - stack
    - 100E. 100. Same Tree
        - simple recursion
    - 451M. Sort Characters By Frequency
        - hash

周赛终于进了一把100

- 10/20
        - 928H. Minimize Malware Spread II
        - Dfs
    - 927H. Three Equal Parts
        - constructive
    - 926M. Flip String to Monotone Increasing
        - Prefix
    - 925E. Long Pressed Name
        - two pointers
    - 336H. Palindrome Pairs
        - Trie+Palidorme

沉了有点久，目前在整理一些模板和经典算法。明天面一个startup，也开始约起G家的电面。

- 10/22~10/23
    - 363H. Max Sum of Rectangle No Larger Than K
        - {DNF}. Binary search Tree
    - 471H. Encode String with Shortest Length
        - {DNF} recrusive. Cannot do that bottom to top.
    - 727H. Minimum Window Subsequence
        - DP. {buggy} `min` is slower than `else`
    - 702M. Search in a Sorted Array of Unknown Size
        - Bin search
    - 215M. Kth Largest Element in an Array
        - quick select

面了下tusimple，由于第一次电面太紧张了，自己原来的做法没想出来。但是面试官很好人，最后在提示下写出来了。


- 10/25
    - new:
        - 4H. Median of Two Sorted Arrays
            - binsearch. estimate the final state and binary search the answer
    - review:
        - 863M. All Nodes Distance K in Binary Tree
            - recursion. make use of the return
        - 307M. Range Sum Query - Mutable
            - BIT. SegTree
        - 285M. Inorder Successor in BST
            - Morris. BST property
        - 205E. Isomorphic Strings
            - hash

刷题刷题刷题

- 10/26
    - google:
        - 297H. Serialize and Deserialize Binary Tree
            - encoding
        - 31M. Next Permutation
            - imple
        - 139M. Word Break
            - Trie.
            - dp with hash.
        - 253M. Meeting Rooms II
            - heap.
        - 17M. Letter Combinations of a Phone Number
            - dfs
        - 23H. Merge k Sorted Lists
            - heap
        - 10H. {buggy} Regular Expression Matching
            - mem+dfs
            - bugs:
                - p_pos < m when s_pos >= n
                - s_pos>=n, cannot read s[s_pos]
                - check equality when *
                - check s_pos < n when star == False
        - 56M. Merge Intervals
            - greedy
        - 42H. Trapping Rain Water
            - prefix-sum. S(N)=O(N)
            - two pointers
        - 20E. Valid Parentheses
            - stack
        - 200M. Number of Islands
            - flood fill.
            - -followup: partition, union-find set
        - 4H. Median of Two Sorted Arrays
            - binsearch
        - 146H. LRU Cache
            - dbl link list+hash
        - 253M. Meeting Rooms II
            - heap

27的周赛最后一题做过类似的，但是当时没有想出构造方法，可惜了。这种比较没有规律的构造题很考验脑洞。
28继续刷lc上google的list，打算先刷完这些然后刷面经。

- 10/28
    - google:
        - 341M. Flatten Nested List Iterator
            - recursion. prefetch.
        - 239H. Sliding Window Maximum
            - deque. only maintain necessary elements.
        - 535M. Encode and Decode TinyURL
            - relevant hash (compression) vs irrelevant hash (key gen). System Design
        - 155E. Min Stack
            - stack
        - 224H. Basic Calculator
            - {buggy} imple
        - 128H. Longest Consecutive Sequence
            - hashing
        - 50M. Pow(x, n)
            - imple
        - 173M. Binary Search Tree Iterator
            - generator
            - manual stack
        - 289M. Game of Life
            - mix information with different bits
        - 54M. Spiral Matrix
            - imple
            - oneline (recursive)
        - 22M. Generate Parentheses
            - dfs
- 10/27
    - Weekly contest
        - 932M. Beautiful Array
            - {DNF}. constructive answer
        - 931M. Minimum Falling Path Sum
            - DP.
        - 930M. Binary Subarrays With Sum
            - imple
            - three pointer solution with O(1) space
        - 929E. Unique Email Addresses
            - hash

leetcode 336对Ptyton有剧毒，Trie+KMP写了几个小时都没过。很影响刷题节奏
406的nlogn做法很巧妙。
315和406似乎揭示了某个规律？就是除非题目是有很浓重的segtree色彩（dynamic insert/query），要不然divide-and-conquer就能解决许多segtree的问题。
merge:
关键就是(1）队列拥有的性质(2）merge的优先级，也就是两个队首先选哪个。
这里的优先级有点类似贪心，通常可以用反证法来证明其正确性（如果不这样选，会违背xx性质）
是一个divide and conquer的思路
segtree:
技巧在于怎么利用logn的sum/min/max去解决原问题
segtree通常来说是一个一个元素处理的，处理完一个就update区间，然后处理下一个

PS： 个人觉得还是比较喜欢divide and conquer，segtree有点太暴力，用久了segtree人会变傻


- 10/29+10/30
    - 735M. Asteroid Collision
        - stack
    - google
        - 406M. Queue Reconstruction by Height
            - sort and insert: O(N^2)
            - {DNF} O(Nlogn): modified merge-sort
            - {DNF} segtree?
        - 140H. Word Break II
            - DP
        - 315H. Count of Smaller Numbers After Self
            - divide and conquer
            - bit
        - 240M. Search a 2D Matrix II
            - grid divide and conquer
        - 295H. Find Median from Data Stream
            - double heap
        - 312H. Burst Balloons
            - rangeDP
        - 387E. First Unique Character in a String
            - hash

很多stack都可以变成Hard

- 10/31
    - 231E. Power of Two
        - imple. corner cases
    - 345E. Reverse Vowels of a String
        - imple
    - 421M. Maximum XOR of Two Numbers in an Array
        - Trie
    - 448M. Find All Numbers Disappeared in an Array
        - use negation as hash
    - 657E. Robot Return to Origin
        - imple
    - 316H. Remove Duplicate Letters
        - hashset + recursion
        - {DNF} stack
    - 280M. Wiggle Sort
        - imple
    - 228M. Summary Ranges
        - imple
    - 463E. Island Perimeter
        - imple
    - 832E. Flipping an Image
        - imple
    - 208M. Implement Trie (Prefix Tree)
        - Trie
    - 66E. Plus One
        - imple
    - 218H. The Skyline Problem
        - {buggy} overlapped boundary. merge
    - 162M. Find Peak Element
        - binary search
    - 739M Daily Temperatures
        - stack

楼主很强！👍

843这种脑洞题，还是蛮有趣的
开始稳定1pass一些Medium+Hard，加油加油


- 11/01~11/02
    - 857H. Minimum Cost to Hire K Workers
        - sort, heap
    - 853M. Car Fleet
        - greedy, sort
    - 855M. Exam Room
        - heap (override comparator `__lt__`)
    - 489H. Robot Room Cleaner
        - recursive
    - 498M. Diagonal Traverse
        - shifting
    - 890M. Find and Replace Pattern
        - mapping equality
    - 843M. Guess the Word
        - {DNF} Good problem. creative question.
    - 62M. Unique Paths
        - simple DP
    - 685H. Redundant Connection II
        - two in degree
    - 684M. Redundant Connection
        - union find set
    - 399M. Evaluate Division
        - DFS
    - 760E. Find Anagram Mappings
        - hash
    - 326E. Power of Three
        - mod trick
    - 388M. Longest Absolute File Path
        - stack