NG转码小白刷题打卡

今天周赛会不会是史上最简单的周赛？4题都是直接implement。 38min4题只有1100多名。
7/16 Sat: (Day 49, total new + 4 = 368+(6), redo 0 old)
- Weekly Contest (easilest ever, all directly iplementation)
- [2341. Maximum Number of Pairs in Array](https://leetcode.com/problems/maximum-number-of-pairs-in-array/)
- [2342. Max Sum of a Pair With Equal Sum of Digits](https://leetcode.com/problems/ma ... qual-sum-of-digits/) (Medium)
- [2343. Query Kth Smallest Trimmed Number](https://leetcode.com/problems/query-kth-smallest-trimmed-number/) (Medium)
- [2344. Minimum Deletions to Make Array Divisible](https://leetcode.com/problems/mi ... ke-array-divisible/) (Hard)

7/17 Sun: (Day 50, total new + 5 = 369+(10), redo 1 old)
- [629. K Inverse Pairs Array](https://leetcode.com/problems/k-inverse-pairs-array/) (Hard) (2D-dp + presum each round to reduce time)
- [LintCode only 630 · Knight Shortest Path II](https://www.lintcode.com/problem/630/) (Medium) (bfs)
- [LintCode only 1844 · subarray sum equals to k II](https://www.lintcode.com/problem ... mp;_from=collection) (Medium) (two-sum)
- [LintCode only 1840 · Matrix restoration](https://leetcode.com/problemset/ ... =Matrix+restoration) (Medium) (understanding of presum)
- [LintCode only 1565 · Modern Ludo I](https://www.lintcode.com/problem/1565/description) (Medium) (DP / bfs to build simple graph then bfs that graph / SPFA to solve complex graph)
- redo to practice:
- 33. Search in Rotated Sorted Array (Medium) (use one pass bisect，其实很简单)

7/18 Mon: (Day 51, total new + 5 = 374 +（10)， redo 1 old)

317. Shortest Distance from All Buildings (Hard) (BFS from each house) same as LintCode 573 · Build Post Office II
499. The Maze III (Hard) (SPFA or Dijkstra (to do))
773. Sliding Puzzle (Hard) (bfs, use str to store int matrix)
LintCode only- 794 · Sliding Puzzle II (Hard) (bfs same as above but better bi-direcional bfs bc state space too large)
1074. Number of Submatrices That Sum to Target (Hard) (presum then can calculate submat sum in O(1), then for fixed (x1,x2) can do 1D subarr sum count in O(n), total O(m*n^2))
practice old:
1310 · Product of Array Except Self (Medium) (two pass)

7/19 Tue: (Day 52, total new + 6 = 377 +（13)， redo 2 old)

1182. Shortest Distance to Target Color (Medium) (pre-process 2 pass or binary search)
643. Maximum Average Subarray I (easy) (sliding window / presum)
644. Maximum Average Subarray II (Hard) (presum + dp of subarr_sum>=0 of arr[i] = nums[i]-candidate + bisect answer space, real hard)
LintCode 391 · Number of Airplanes in the Sky (Medium) (pre-process+sort or sort+heap) (same as 253. Meeting Rooms II)
LintCode 194 · Find Words (Medium) (index map + binary search)
LintCode 1850 · Pick Apples (Medium) (left_max dp and right_max dp total three pass)
practice on old questions:
Best Time to Buy and Sell Stock
862. Shortest Subarray with Sum at Least K (Hard) (monotonic-queue / bisect + heap window)

7/20 Wed: (Day 53, total new +3 = 378 + (15) , redo 5 old) 今天试图整理subarr sum相关的各种various，但是太过多样没完全整理完
LintCode 1849 · Grumpy Bookstore Owner (Medium) (sliding window)
LintCode 404 · Subarray Sum II (Meidum) (three pointers)
1099. Two Sum Less Than K (easy) (need sort then two pointers)
redo old:
792. Number of Matching Subsequences (Medium) (index map + binary search) (or next letter pointes) same as LintCode 194 · Find Words
Two Sum
Two Sum II - Input Array Is Sorted
Two Sum III - Data structure design
Maximum Size Subarray Sum Equals k

7/22 Fri: (Day 55, total new +7 = 383 + (22) , redo 0 old)今天主要复习了BFS，然后学习了Dijkstra并且写了简易可用的template

LintCode 677 · Number of Big Islands (Medium) (standard BFS, can DFS but usually just bfs)
LintCode 598 · Zombie in Matrix (Medium) (BFS, label in-place) (same as rotten orange etc)
LintCode 261 · Maximum Connected Area (Medium) (BFS and label islands and record ares)
LintCode 127 · Topological Sorting (Medium) (standard topo sort)
305. Number of Islands II(Hard) (union find i.e. disjoint union)
LintCode 1828 · Lake Escape (Hard) (not asking shortest path so still a simple graph, just BFS)
743. Network Delay Time (Medium) (Dijkstra / SPFA)

Dijkstra模板真的很短，贴上来吧
```python
  minheap = [(0, start)]
  distance = dict()
  while minheap:
      dist, cur = heapq.heappop(minheap)
      if cur not in distance: # elif cur in distance, it must be a longer path, so discard
          distance[cur] = dist
          if cur == target:
              return dist
          for next_node, edge_weight in self.get_next(cur):
              heapq.heappush(minheap, (dist + edge_weight, next_node))
  return -1 # cannot reach target
```

7/23 Sat: (Day 56, total new +6 = 389 + (22) , redo 0 old)

787. Cheapest Flights Within K Stops (Medium) (pretty hard, (1) SPFA TLE but SPFA+step dict works well (2) BFS steps and record dist) (Worth to redo more times)
315. Count of Smaller Numbers After Self (Hard) (segment tree/ merge sort)
2351. First Letter to Appear Twice (easy)
2352. Equal Row and Column Pairs (Medium)
2353. Design a Food Rating System (Medium) (cross-link into minheap)
2354. Number of Excellent Pairs (Hard) (math)

7/24 Sun: (Day 57, total new +4 = 391 + (24), redo 3 old)

847. Shortest Path Visiting All Nodes (Hard) (bitmask visited + state =(cur, mask) + bfs state)
LintCode 258 · Map Jump (Hard) (bisect+bfs or directly SPFA min_heigh_diff_needed)
LintCode 1832 · Minimum Step (Medium) (BFS)
694. Number of Distinct Islands (Medium) (BFS + hash the shape of island (by tuplize relative (i,j) set or by converting to string etc))
redo old:
Reverse Bits
LintCode. 297 · Find the maximum
Number of Islands (wrap BFS into func for better coding style)

做这么多，，可以