NG转码小白刷题打卡

6/17 Fri: (Day 20, total new 169) 这周的weekly challenge是Trie相关，今天daily challenge又是，正好学以致用了，快乐
- Daily Challenge:
- 745. Prefix and Suffix Search (Hard) (Trie) https://leetcode.com/problems/prefix-and-suffix-search/
- Data Structure II:
- 334. Increasing Triplet Subsequence (Medium) https://leetcode.com/problems/increasing-triplet-subsequence/
- 560. Subarray Sum Equals K (Medium) https://leetcode.com/problems/subarray-sum-equals-k/
- 415. Add Strings: https://leetcode.com/problems/add-strings/solution/
- Algorithm II:
- 547. Number of Provinces (Medium) (can practice union find but didn't do) https://leetcode.com/problems/number-of-provinces/
- Graph Theory I:
- 1091. Shortest Path in Binary Matrix (Medium) (A search with heap not tried yet) https://leetcode.com/problems/shortest-path-in-binary-matrix/
- 934. Shortest Bridge (Medium) https://leetcode.com/problems/shortest-bridge/
- 1567. Maximum Length of Subarray With Positive Product (Medium) https://leetcode.com/problems/ma ... h-positive-product/
- Bed-time easy questions:
- 66. Plus One https://leetcode.com/problems/plus-one/
- 67. Add Binary (redo for practice) https://leetcode.com/problems/add-binary/
- 69. Sqrt(x) https://leetcode.com/problems/sqrtx/

6/18 Sat: (Day 21, total new 180) 周赛可惜了还是差一些4题
- Data Strucutre II:
- 290. Word Pattern https://leetcode.com/problems/word-pattern/
- 763. Partition Labels (Medium) https://leetcode.com/problems/partition-labels/
- Algorithm II:
- 117. Populating Next Right Pointers in Each Node II (Medium) https://leetcode.com/problems/po ... rs-in-each-node-ii/
- 572. Subtree of Another Tree https://leetcode.com/problems/subtree-of-another-tree/
- Dynamic Programming I:
- 122. Best Time to Buy and Sell Stock II (Medium) https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
- 714. Best Time to Buy and Sell Stock with Transaction Fee (Medium) https://leetcode.com/problems/be ... th-transaction-fee/
- Weekly Contest 298:
- 2309. Greatest English Letter in Upper and Lower Case https://leetcode.com/problems/gr ... per-and-lower-case/
- 2310. Sum of Numbers With Units Digit K (Medium) https://leetcode.com/problems/sum-of-numbers-with-units-digit-k/
- 2311. Longest Binary Subsequence Less Than or Equal to K (Medium) https://leetcode.com/problems/lo ... than-or-equal-to-k/
- 2312. Selling Pieces of Wood (Hard) https://leetcode.com/problems/selling-pieces-of-wood/
- 157. Read N Characters Given Read4 https://leetcode.com/problems/read-n-characters-given-read4/

6/19 Sun: (Day 22, total new 190) 稳步向前
- Daily Challenge
- [1268. Search Suggestions System](https://leetcode.com/problems/search-suggestions-system/) (Medium) (prefix trie)
- [820. Short Encoding of Words](https://leetcode.com/problems/short-encoding-of-words/) (Medium) (prefix trie)
- Data Structure II:
- [49. Group Anagrams](https://leetcode.com/problems/group-anagrams/) (Medium)
- [43. Multiply Strings](https://leetcode.com/problems/multiply-strings/) (Medium)
- Algorithm II:
- [130. Surrounded Regions](https://leetcode.com/problems/surrounded-regions/) (Medium) (dfs/bfs)
- [797. All Paths From Source to Target](https://leetcode.com/problems/all-paths-from-source-to-target/) (Medium) (backtrack or dp)
- Having fun with easy ones:
- [100. Same Tree](https://leetcode.com/problems/same-tree/)
- [108. Convert Sorted Array to Binary Search Tree](https://leetcode.com/problems/co ... binary-search-tree/)
- [111. Minimum Depth of Binary Tree](https://leetcode.com/problems/minimum-depth-of-binary-tree/)
- [163. Missing Ranges](https://leetcode.com/problems/missing-ranges/)

今天写了个Tree Traversal模板的note。也贴在这吧(md的贴在这可能排版会很乱？)：
### Tree Traversals
- pre-order, in-order, post-order, level-order
- DFS (depth first search) and BFS (breadth first search)
- ![image](Tree Traversal.png）

##### pre-order (cur->left->right)
- DFS recursion:
```python
def dfs_preorder(root):
    if not root: return
    root.val # or other action on node
    dfs_preorder(root.left)
    dfs_preorder(root.right)
```

- DFS iteration via stack:
```python
def dfs_preorder(root):
    if not root: return
    stack = [root]
    while stack:
      node=stack.pop()
      node.val
      if node.right:
        stack.append(node.right) # right first bc stack
      if node.left:
        stack.append(node.left)
```

##### in-order (left->cur->right)
- DFS recursion:
```python
def dfs_inorder(root):
    if not root: return
    dfs_inorder(root.left)
    root.val
    dfs_inorder(root.right)
```
- DFS iteration via stack:
```python
def dfs_inorder(root):
    if not root:
      return None
    stack = []
    node = root
    while node or stack:
      while node:
        stack.append(node)
        node=node.left
      node=stack.pop()
      node.val
      node=node.right
```

#### post-order (right-left-cur)
- DFS recursion:
```python
def dfs_postorder(root):
    if not root: return
    dfs_postorder(root.right)
    dfs_postorder(root.left)
    root.val
```
- DFS iteration via stack:
(pre-order but right first, records all nodes, in the end reverse the result)
```python
def dfs_postorder(root):
    ret=[]
    if not root: return []
    stack=[root]
    while stack:
      node=stack.pop()
      if not node: continue
      ret.append(node.val)
      if node.left:
        stack.append(node.left) #note different from pre-order
      if node.right:
        stack.append(node.right)
    return ret[::-1]
```

##### level-order (left->right->next)
- DFS pre-order, store level info, return with nested list [[lv0],[lv1..],[lv2....]]
- DFS recursion:
```python
def dfs_levelorder(root):
    if not root: return []

    def dfs_preorder(node,level):
      if len(ret)==level:
        ret.append([])
      ret[level].append(node.val)
      if node.left:
        dfs_preorder(node.left,level+1)
      if node.right:
        dfs_preorder(node.right,level+1)

    ret=[]
    dfs_preorder(root,0)
    return ret
```
- DFS iteration via stack:
```python
def dfs_levelorder(root):
  if not root: return []
  stack=list()
  stack.append((root,0))
  ret = []
  while stack:
    node,level=stack.pop()
    if level == len(ret):
      ret.append([])
    ret[level].append(node.val)
    if node.left:
      stack.append((node.left,level+1))
    if node.right:
      stack.append((node.right,level+1))
  return ret
```

- BFS iteration with Queue:
```python
def bfs(root):
    if not root: return []
    que = collections.deque()
    que.append(root)
    ret = []
    while que:
      cur_level = []
      for _ in range(len(que)): # needed to count step in shortest path etc
        node=que.popleft() #important, not pop()
        cur_level.append(node.val)
        if node.left:
          que.append(node.left)
        if node.right:
          que.append(node.right)
      ret.append(cur_level)
    return ret
```

6/20 Mon: (Day 23, total new 197)发现又把heap给忘了…写下note以后看
- Daily Challenge:
- [1642. Furthest Building You Can Reach](https://leetcode.com/problems/furthest-building-you-can-reach/) (Medium) (heap)
- Data Strucutre II:
- [187. Repeated DNA Sequences](https://leetcode.com/problems/repeated-dna-sequences/) (Medium) (Robin-Karp)
- Algorithm II:
- [78. Subsets](https://leetcode.com/problems/subsets/) (Medium)
- [90. Subsets II](https://leetcode.com/problems/subsets-ii/) (Medium)
- LeetCode 75 II:
- [202. Happy Number](https://leetcode.com/study-plan/leetcode-75/?progress=zw5r4ig)
- [54. Spiral Matrix](https://leetcode.com/problems/spiral-matrix/) (Medium)
- [1706. Where Will the Ball Fall](https://leetcode.com/problems/where-will-the-ball-fall/) (Medium)
- Redo old question:
- [5. Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring/) (Medium)

看到楼主每天都记录自己的刷题内容，感觉很受鼓舞！我也在刷题，感觉没有楼主那么效率高，但我会再逼一逼自己的！加油

MartinZhao 发表于 2022-06-21 07:17:23
看到楼主每天都记录自己的刷题内容，感觉很受鼓舞！我也在刷题，感觉没有楼主那么效率高，但我会再逼一逼自己的！加油

一起加油！

6/21 Tue: (Day 24, total new 207) 两百罗，好耶，但是越刷越觉得重复做经典题比无限刷新题重要了，到300题时最好要开始系统性复习整理了，多做序号小的题吧。
- Daily Challenge:
- [215. Kth Largest Element in an Array](https://leetcode.com/problems/kt ... -an-array/solution/) (Medium) (heap, quickselect(not done))
- Data Structure II:
- [142. Linked List Cycle II](https://leetcode.com/problems/linked-list-cycle-ii/) (Medium)
- [24. Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/submissions/) (Medium)
- [707. Design Linked List](https://leetcode.com/problems/design-linked-list/) (Medium) (super easy to get wrong! practice again later!)
- Algorithm II:
- [47. Permutations II](https://leetcode.com/problems/permutations-ii/) (Medium) (backtrack)
- [39. Combination Sum](https://leetcode.com/problems/combination-sum/) (Medium) (backtrack)
- [40. Combination Sum II](https://leetcode.com/problems/combination-sum-ii/) (Medium) (backtrack)
- Leetcode 75 II:
- [234. Palindrome Linked List](https://leetcode.com/problems/palindrome-linked-list/submissions/)
- [328. Odd Even Linked List](https://leetcode.com/problems/odd-even-linked-list/) (Medium)
- Make up easy questions with low index:
- [168. Excel Sheet Column Title](https://leetcode.com/problems/excel-sheet-column-title/)

6/22 Wed: (Day 25, total new 214) 今天新题不多，但写了linked list的一些模板，就这样吧

Leetcode 75 II:
148. Sort List (Medium) (MergeSort)
Data Structure II:
25. Reverse Nodes in k-Group (Hard) (code readability could improve)
143. Reorder List (Medium)
Related Linded List:
1721. Swapping Nodes in a Linked List (Medium)
2074. Reverse Nodes in Even Length Groups (Medium)
Make up easy questions with low number:
170. Two Sum III - Data structure design
171. Excel Sheet Column Number

6/23 Thu: (Day 26, total new 224)
- Daily/Weekly Challenge:
- [630. Course Schedule III](https://leetcode.com/problems/course-schedule-iii/) (Hard) (dp TLE, must gready, heap helps further imporve)
- [1229. Meeting Scheduler](https://leetcode.com/problems/meeting-scheduler/) (Medium)
- Algorithm II:
- [17. Letter Combinations of a Phone Number](https://leetcode.com/problems/le ... -of-a-phone-number/) (Medium) (backtrack)
- [22. Generate Parentheses](https://leetcode.com/problems/generate-parentheses/) (Medium) (backtrack)
- [79. Word Search](https://leetcode.com/problems/word-search/) (Medium) (backtrack)
- Leetcode 75 II:
- [2131. Longest Palindrome by Concatenating Two Letter Words](https://leetcode.com/problems/lo ... -words/submissions/) (Medium)
- [621. Task Scheduler](https://leetcode.com/problems/task-scheduler/submissions/) (Medium) (greedy/math)
- Make up easy questions with low number:
- [205. Isomorphic Strings](https://leetcode.com/problems/isomorphic-strings/)
- [219. Contains Duplicate II](https://leetcode.com/problems/contains-duplicate-ii/)
- [225. Implement Stack using Queues](https://leetcode.com/problems/implement-stack-using-queues/)