NG转码小白刷题打卡

7/1 Fri: (Day 34, total new + 9 = 296)
- Top Google:
- [68. Text Justification](https://leetcode.com/problems/text-justification/) (Hard) (straightforward but hard to finish bug-free)
- [329. Longest Increasing Path in a Matrix](https://leetcode.com/problems/lo ... g-path-in-a-matrix/) (Hard) (dfs+memo) (pls understand how backtrack TLE here)
- [366. Find Leaves of Binary Tree](https://leetcode.com/problems/find-leaves-of-binary-tree/) (Medium) (height of tree, dfs)
- [388. Longest Absolute File Path](https://leetcode.com/problems/longest-absolute-file-path/) (Medium) (good practice for handling strings)
- [419. Battleships in a Board](https://leetcode.com/problems/battleships-in-a-board/) (Medium) (bfs/dfs)
- [2096. Step-By-Step Directions From a Binary Tree Node to Another](https://leetcode.com/problems/st ... ee-node-to-another/) (Medium) (tree path (backtrack)/lowest common ancestor)
- Make up easy questions with low number:
- [342. Power of Four](https://leetcode.com/problems/power-of-four/)
- [345. Reverse Vowels of a String](https://leetcode.com/problems/reverse-vowels-of-a-string/)
- [346. Moving Average from Data Stream](https://leetcode.com/problems/mo ... ta-stream/solution/) (some fun solution to do)

7/2 Sat: (Day 35, total new + 6 = 302) 第一次contest 4题全做出，但是好像太简单了全做出的有快两千人… 唉排名才九百多还不如之前只做出三题的两次…可惜wrong sbumit了两次不然可以前进好几百名。而且第四题是是昨天刚好做过的top google题的翻版…… 哈哈好多碎碎念_(:зゝ∠)_，就这样吧
- Daily Challenge:
- [1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts](https://leetcode.com/problems/ma ... -and-vertical-cuts/) (Medium)
- [376. Wiggle Subsequence](https://leetcode.com/problems/wiggle-subsequence/) (Medium) (dp/greedy)
- Weekly Contest:
- [2325. Decode the Message](https://leetcode.com/problems/decode-the-message/)
- [2326. Spiral Matrix IV](https://leetcode.com/problems/spiral-matrix-iv/)(Medium)
- [2327. Number of People Aware of a Secret](https://leetcode.com/problems/number-of-people-aware-of-a-secret/)(Medium)
- [2328. Number of Increasing Paths in a Grid](https://leetcode.com/problems/nu ... ng-paths-in-a-grid/) (Hard) (same as 329)

7/3 Sun: (Day 36, total new + 1  = 303) 休息两天不着急
- Daily Challenge:
- [135. Candy](https://leetcode.com/problems/candy/) (Hard) (stack/ not seen other solu yet)

7/4 Mon: (Day 37, taotal new + 5 = 308) 回到每日5题medium+，尽量有1题以上hard。放缓节奏看看旧题，不要求自己冲很多新题
- Daily Challenge:
- [128. Longest Consecutive Sequence](https://leetcode.com/problems/longest-consecutive-sequence/) (Medium) (HashSet)
- Algorithm II: (all done)
- [149. Max Points on a Line](https://leetcode.com/problems/max-points-on-a-line/) (Hard) (use coprime to represent slope)
- LeetCode 75 II:
- [416. Partition Equal Subset Sum](https://leetcode.com/problems/partition-equal-subset-sum/) (Medium) (recursion with memo/ dp like)
- [16. 3Sum Closest](https://leetcode.com/problems/3sum-closest/) (Medium) (two-sum, sort and two pointers)
- [208. Implement Trie (Prefix Tree)](https://leetcode.com/problems/implement-trie-prefix-tree/) (Medium)

7/5 Tue: (Day 38, taotal new + 6 = 314) 虽然只是6题但是4 medium，2 hard 不错的
- LeetCode 75 II:
- [76. Minimum Window Substring](https://leetcode.com/problems/minimum-window-substring/) (Hard) (two pointers)
- Top Google:
- [253. Meeting Rooms II](https://leetcode.com/problems/meeting-rooms-ii/) (Medium) (sort + gready/minheap)
- [1293. Shortest Path in a Grid with Obstacles Elimination](https://leetcode.com/problems/sh ... tacles-elimination/) (Hard) (bfs extra dimension/ A* (A start) alg)
- [1146. Snapshot Array](https://leetcode.com/problems/snapshot-array/) (Medium) (binary search)
- [1937. Maximum Number of Points with Cost](https://leetcode.com/problems/maximum-number-of-points-with-cost/) (Medium) (dp + pre-processing)
- [2034. Stock Price Fluctuation](https://leetcode.com/problems/stock-price-fluctuation/) (Medium) (heap or sortedcontainers.SortedDict)

7/6 Wed: (Day 39, taotal new + 5 = 319) 今天基于自己的binary search模板新写了通用的二分法模板， 虽然只有5题但是精做hard真得很花时间，很不错了，以后估计也按5题medium及以上的pace来。
- [862. Shortest Subarray with Sum at Least K](https://leetcode.com/problems/sh ... ith-sum-at-least-k/) (Hard) (monotonic-queue / bisect + heap window)
- Daily Challenge:
- [97. Interleaving String](https://leetcode.com/problems/interleaving-string/submissions/) (Medium)
- LeetCode 75 II:
- [735. Asteroid Collision](https://leetcode.com/problems/asteroid-collision/) (Medium)
- [227. Basic Calculator II](https://leetcode.com/problems/basic-calculator-ii/) (Medium) (stack, int operator)
- Top Google:
- [418. Sentence Screen Fitting](https://leetcode.com/problems/sentence-screen-fitting/) (Medium)

贴个自己写的二分法通用模板，md格式：
- bisect answer space (二分法):
  - consider sorted answer candidate space candidate[i], and has following properties:
    - function is_valid_answer(candidate[i]) returns 'O' (True) or 'X' (False)
    - corresponding is_valid array is 'OOOOXXXXX' (find max 'O') or 'XXXXOOOO' (find min 'O')
  - case 1: 'XXXXOOOO' (find min 'O')
  ```python
    def is_valid(candidate):
      if target <= candidate:
        return True
      else:
        return False

    def bisect(start, end, Candidates): # check candidate space: Candidates[start: end + 1]
      # find and return target
      # if no valid answer in Candidates return -1
      left, right = start, end + 1
      while left < right:
        mid = (left + right) // 2
        candidate = Candidates[mid]
        if is_valid(candidate):
          right = mid
        else:
          left = mid + 1
      # if right == end + 1 then no valid answer
      return right if right <= end else -1
  ```
  - case 2: 'OOOOXXXXX' (find max 'O')
    - find min 'X' first, i.e. use `not is_valid(candidate)` instead of `is_valid(candidate)`
  ```python
    def is_valid(candidate):
      if target <= candidate:
        return True
      else:
        return False

    def bisect(start, end, Candidates): # check candidate space: Candidates[start: end + 1]
      # find and return target
      # if no valid answer in Candidates return -1
      left, right = start, end + 1
      while left < right:
        mid = (left + right) // 2
        candidate = Candidates[mid]
        if not is_valid(candidate):
          right = mid
        else:
          left = mid + 1
      # if right == start then no valid answer
      return right - 1 if right > start else -1
  ```

补充内容 (2022-07-08 14:02 +8:00):
case 2 的 is_valid 函数有误，忘改了，应该是target >= candidate: return True。不过无所谓，反正都得按实际考虑怎么构建is_valid函数

Lyrics_2942 发表于 2022-06-03 18:06:26
2个月400新题，感觉自己刷的好慢

这个速度很快了！吃透就好，加油！

7/7 Thu: (Day 40, total new + 5 = 324) 中规中矩5道题，但是有两道hard，而且还写了union find的实用模板(w/path compression w/o union by rank)。
- [287. Find the Duplicate Number](https://leetcode.com/problems/find-the-duplicate-number/) (Medium) (binary search / two pointer(Floyd's algorithm))
- [41. First Missing Positive](https://leetcode.com/problems/first-missing-positive/) (Hard) (pigeon hole / negative mark) (index matches with answer space, then modify input arr to achieve O(1) space)
- [256. Paint House](https://leetcode.com/problems/paint-house/) (Meidum) (dp)
- Daily Challenge:
- [1473. Paint House III](https://leetcode.com/problems/paint-house-iii/) (Hard) (dp 3d)
- LeetCode 75 II:
- [947. Most Stones Removed with Same Row or Column](https://leetcode.com/problems/mo ... same-row-or-column/) (Medium) (dfs/union find)

lkz4618 发表于 2022-7-7 01:52
贴个自己写的二分法通用模板，md格式：
- bisect answer space (二分法):
  - consider sorted answer ca ...

case 2 的 is_valid 函数有误，忘改了，应该是target >= candidate: return True。不过无所谓，反正都得按实际考虑怎么构建is_valid函数