刷题记录帖子

429        N-ary Tree Level Order Traversal        Medium

还是基础的 level order traversal
因为 BFS 所以需要 queue 来记录。

101        Symmetric Tree        Easy       

Always processing two nodes each round

1. 
   
2. 
   
3. """
   
4. 
   
5. Recursive
   
6. 
   
7. """
   
8. 
   
9. # Definition for a binary tree node.
   
10. # class TreeNode:
    
11. #     def __init__(self, val=0, left=None, right=None):
    
12. #         self.val = val
    
13. #         self.left = left
    
14. #         self.right = right
    
15. class Solution:
    
16.     def isSymmetric(self, root: TreeNode) -> bool:
    
17.         
    
18.         def checkMirror(node1, node2):
    
19.             # both None
    
20.             if not node1 and not node2: return True
    
21.             # One Not None, One None
    
22.             if not node1 or not node2 : return False
    
23.             # both not None
    
24.             return node1.val == node2.val and checkMirror(node1.right, node2.left) and checkMirror(node1.left, node2.right)
    
25.         
    
26.         return checkMirror(root, root)
    
27.         
    
28. 
    
29. """
    
30. 
    
31. Iterative
    
32. 
    
33. """
    
34. 
    
35. # Definition for a binary tree node.
    
36. # class TreeNode:
    
37. #     def __init__(self, val=0, left=None, right=None):
    
38. #         self.val = val
    
39. #         self.left = left
    
40. #         self.right = right
    
41. class Solution:
    
42.     def isSymmetric(self, root: TreeNode) -> bool:
    
43.         queue = deque([root, root])
    
44.         
    
45.         while queue:
    
46.             node1 = queue.popleft()
    
47.             node2 = queue.popleft()
    
48.             
    
49.             # Both None
    
50.             if not node1 and not node2: continue
    
51.             
    
52.             # One None, One not None
    
53.             if not node1 or not node2: return False
    
54.             
    
55.             # Both not None
    
56.             if node1.val != node2.val: return False
    
57.             # Mirror
    
58.             queue.append(node1.left)
    
59.             queue.append(node2.right)
    
60.             
    
61.             queue.append(node1.right)
    
62.             queue.append(node2.left)
    
63.             
    
64.         return True
    
65.         

复制代码

120. Triangle

Bottom Up Classic

1. class Solution:
   
2.     def minimumTotal(self, triangle: List[List[int]]) -> int:
   
3.         n = len(triangle)
   
4.         if n == 1: return min(triangle[0])
   
5.         
   
6.         row_curr = triangle[n-1]
   
7.         
   
8.         for row in range(n-2, -1, -1):
   
9.             row_up = triangle[row]
   
10.             for ind in range(len(row_up)):
    
11.                 row_up[ind] = min(row_curr[ind] +  triangle[row][ind],
    
12.                                   row_curr[ind+1] + triangle[row][ind])
    
13.             row_curr = row_up
    
14.         return row_up[0]

复制代码

554        Brick Wall

真题目还是很经典的，统计 freq of wall index。

1. class Solution:
   
2.     def leastBricks(self, wall: List[List[int]]) -> int:
   
3.         freq = defaultdict(int)
   
4.         n = len(wall)
   
5.         ending = sum(wall[0])
   
6.         
   
7.         for row in wall:
   
8.             c0 = 0
   
9.             for c in row:
   
10.                 ind = c0 + c
    
11.                 if ind != ending: freq[ind] += 1
    
12.                 c0 = ind
    
13. 
    
14.         if not freq:
    
15.             return n
    
16.         else:
    
17.             return n - max(freq.values())

复制代码

326. Power of Three

return n > 0 and 1162261467 % n == 0

34        Find First and Last Position of Element in Sorted Array        Medium        5        bisect_right - 1 / bisect_left
970        Powerful Integers         Medium               

1480        Running Sum of 1d Array        Easy

816        Ambiguous Coordinates        Medium        5        边界条件        for i in range(1, len(x)): if (x[:i] == "0" or x[0] != "0") and x[-1] != "0":

LeetCode 114. Flatten Binary Tree to Linked List (Python)

好经典的题目，真是太漂亮了。如何解决移动的问题，在移动的同时保持 preorder 的结构。

参考这个画图解释， https://leetcode.com/problems/fl ... tremely-Intuitive-O(1)-Space-solution-with-Simple-explanation-Python

609. Find Duplicate File in System

感觉这道题目的 follow up 特别有意思。

BFS vs DFS
BFS explores neighbors first. This means that files which are located close to each other are also accessed one after another. This is great for space locality and that's why BFS is expected to be faster. Also, BFS is easier to parallelize (more fine-grained locking). DFS will require a lock on the root node.

Very large files and false positives
For very large files we should do the following comparisons in this order:

compare sizes, if not equal, then files are different and stop here!
hash them with a fast algorithm e.g. MD5 or use SHA256 (no collisions found yet), if not equal then stop here!
compare byte by byte to avoid false positives due to collisions.
Have you used an IDE in remote development mode?
For example, CLion has some options on how to compare the local files with the remote server files and then decides to synchronize or not.

Complexity
Runtime - Worst case (which is very unlikely to happen): O(N^2 * L) where L is the size of the maximum bytes that need to be compared
Space - Worst case: all files are hashed and inserted in the hashmap, so O(H^2*L), H is the hash code size and L is the filename size