刷题记录帖子

LeetCode 341. Flatten Nested List Iterator

理解数据结构，它在题目中的 input 并没有仔细说明，其实还是 List 的input，所以可以 for ele in LL 去 Loop all elements。

667. Beautiful Arrangement II

这道题目其实超出了 medium 的难度。这题非常反直觉的，利用了 compact match。也就是你其实不需要管可以随意安排的部分，你只要管能产生 k 个 difference 的部分就行了。这样的话，方便你提出公式。

其实就是观察到 k 个 difference 只需要 k+1 个数字，别的多出来的数字，随意就行。

329. Longest Increasing Path in a Matrix

经典题目，需要记忆做法，参考了 Tommmy 的解法， https://www.youtube.com/watch?v=tBFzoRJtWjI

Classic Recursive Call with Memorization

1209. Remove All Adjacent Duplicates in String II

Clever Using of Stack to Solve Problems

1146. Snapshot Array

How to store spare array with snapshot

1. class SnapshotArray:
   
2. 
   
3.     def __init__(self, length: int):
   
4.         self.array = defaultdict(defaultdict)
   
5.         self.snapID = 0
   
6.         self.length = length
   
7. 
   
8.     def set(self, index: int, val: int) -> None:
   
9.         if index < self.length:
   
10.             self.array[self.snapID][index] = val
    
11. 
    
12.     def snap(self) -> int:
    
13.         self.snapID += 1
    
14.         return self.snapID - 1
    
15. 
    
16.     def get(self, index: int, snap_id: int) -> int:
    
17.         while snap_id >= 0:
    
18.             if index in self.array[snap_id]:
    
19.                 return self.array[snap_id][index]
    
20.             snap_id -= 1
    
21.         return 0
    
22. 
    
23. 
    
24. # Your SnapshotArray object will be instantiated and called as such:
    
25. # obj = SnapshotArray(length)
    
26. # obj.set(index,val)
    
27. # param_2 = obj.snap()
    
28. # param_3 = obj.get(index,snap_id)

复制代码

LeetCode 1813. Sentence Similarity III (Python)

简单说就是如何通过两个 deque 检查 0 和 -1 位置的元素和对应的  popleft(), pop() 操作来实现对于 prefix 和 suffix 的查找。

1. 
   
2. 
   
3. class Solution:
   
4.     def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:
   
5.         s1 = deque(sentence1.split())
   
6.         s2 = deque(sentence2.split())
   
7.         
   
8.         # check prefix
   
9.         while s1 and s2 and s1[0] == s2[0]:
   
10.             s1.popleft()
    
11.             s2.popleft()
    
12.         # check suffix
    
13.         while s1 and s2 and s1[-1] == s2[-1]:
    
14.             s1.pop()
    
15.             s2.pop()
    
16.         
    
17.         return len(s1) * len(s2) == 0
    
18. 
    

复制代码

Remove Nth Node From End of List        Medium

Two Pointers with dummy nodes

1. # Definition for singly-linked list.
   
2. # class ListNode:
   
3. #     def __init__(self, val=0, next=None):
   
4. #         self.val = val
   
5. #         self.next = next
   
6. class Solution:
   
7.     def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
   
8.         fast = slow = dummy = ListNode(0, head)
   
9.         
   
10.         for _ in range(n):
    
11.             fast = fast.next
    
12.         
    
13.         while fast.next:
    
14.             fast = fast.next
    
15.             slow = slow.next
    
16.             
    
17.         slow.next = slow.next.next
    
18.         
    
19.         return dummy.next

复制代码

377        Combination Sum IV        Medium       

DP for 1 to target

1. 
   
2. 
   
3. class Solution:
   
4.     def combinationSum4(self, nums: List[int], target: int) -> int:
   
5.         # dp[i] the # of conbinations to reach i
   
6.         # dp[i] = sum( dp[x] ) where x <= i
   
7.         # reference: [url]https://www.cnblogs.com/grandyang/p/5705750.html[/url]
   
8.         dp = [0] * (target+1)
   
9.         dp[0] = 1 # base case
   
10.         nums = sorted(nums)
    
11.         
    
12.         for i in range(1, len(dp)):
    
13.             for num in nums:
    
14.                 if num <= i:
    
15.                     dp[i] += dp[i-num]
    
16.                 else:
    
17.                     break
    
18.         return dp[-1]
    
19.         
    
20.         

复制代码

146 LRU Cache

这道题目有现实意义就是如何实现内存的页面调度，参考这个链接，https://www.cnblogs.com/grandyang/p/4587511.html

当然 Python 有神器，就是 OrderedDict 简直是为这道题目量身打造的，popitem(last = False ) 就是先进先出，这道题目要求的，反过来 last = True 就是 stack。

1. 
   
2. 
   
3. from collections import OrderedDict
   
4. 
   
5. class LRUCache:
   
6. 
   
7.     def __init__(self, capacity: int):
   
8.         self.capacity = capacity
   
9.         self.LRU = OrderedDict()
   
10. 
    
11. 
    
12.     def get(self, key: int) -> int:
    
13.         if key in self.LRU:
    
14.             val = self.LRU[key]
    
15.             del self.LRU[key]
    
16.             self.LRU[key] = val
    
17.             return val
    
18.         else:
    
19.             return -1
    
20. 
    
21.     def put(self, key: int, value: int) -> None:
    
22.         if key in self.LRU:
    
23.             del self.LRU[key]
    
24.             self.LRU[key] = value
    
25.         else:
    
26.             self.LRU[key] = value
    
27.             if len(self.LRU) > self.capacity:
    
28.                 self.LRU.popitem(last=False)
    
29.             
    
30. 
    
31. 
    
32. # Your LRUCache object will be instantiated and called as such:
    
33. # obj = LRUCache(capacity)
    
34. # param_1 = obj.get(key)
    
35. # obj.put(key,value)

复制代码

589        N-ary Tree Preorder Traversal        Easy        4        Deque + Popleft + Appendleft + Reverse

个人 感觉这道题目五路如何不能算 easy 其实是 medium 啊。特别是 iterative 的方法其实用到了很多深层次的知识。