no message

wuduhren · wuduhren · commit a20b61a56f8e · 2021-12-11T19:51:31.000+08:00
diff --git a/problems/convert-sorted-array-to-binary-search-tree.py b/problems/convert-sorted-array-to-binary-search-tree.py
@@ -49,4 +49,18 @@ def helper(i, j):
             if rightLength>0: node.right = helper(m+1, j)
             return node
         
-        return helper(0, len(nums))
+        return helper(0, len(nums))
+
+
+
+
+class Solution(object):
+    def sortedArrayToBST(self, nums):
+        def helper(s, e):
+            if s>e: return None
+            m = (s+e)/2
+            node = TreeNode(nums[m])
+            node.left = helper(s, m-1)
+            node.right = helper(m+1, e)
+            return node
+        return helper(0, len(nums)-1)
diff --git a/problems/design-in-memory-file-system.py b/problems/design-in-memory-file-system.py
@@ -0,0 +1,46 @@
+"""
+self.dirs is a nested hashmap to store the file structure.
+self.files is a hashmap, mainly used to determine if the path is a "file", also used to store the content of the file.
+
+Time: 
+ls O(K)
+mkdir O(K)
+addContentToFile O(K)
+readContentFromFile O(1)
+K is the path count, for example /a/b/c/d, K=4.
+
+Space:
+O(N), N is the dir counts.
+"""
+class FileSystem(object):
+
+    def __init__(self):
+        self.files = {}
+        self.dirs = {}
+
+    def ls(self, path):
+        if path in self.files:
+            return [path.split('/')[-1]]
+        else:
+            if path=='/': return sorted(self.dirs.keys())
+            curr = self.dirs
+            for d in path.split('/')[1:]:
+                curr = curr[d]
+            return sorted(curr.keys())
+        
+    def mkdir(self, path):
+        curr = self.dirs
+        for d in path.split('/')[1:]:
+            if d not in curr:
+                curr[d] = {}
+            curr = curr[d]
+        
+    def addContentToFile(self, filePath, content):
+        if filePath not in self.files:
+            self.mkdir(filePath)
+            self.files[filePath] = content
+        else:
+            self.files[filePath] += content
+            
+    def readContentFromFile(self, filePath):
+        return self.files[filePath]
diff --git a/problems/find-mode-in-binary-search-tree.py b/problems/find-mode-in-binary-search-tree.py
@@ -1,3 +1,8 @@
+"""
+Time: O(N). For we traverse every node recursively.
+Space: O(N). Becuase we store all element's val and count in `counter`.
+Note that, we do not use the feature of BST.
+"""
 from collections import Counter
 class Solution(object):
     def findMode(self, root):
@@ -14,11 +19,21 @@ def count(node):
         return [val for val, count in counter.items() if count==max_count]
 
 """
-Time: O(N). For we traverse every node recursively.
-Space: O(N). Becuase we store all element's val and count in `counter`.
-Note that, we do not use the feature of BST.
-"""
+To use the feature of BST, we are going to inorder traverse the BST.
+So it will be like we are iterating a sorted array.
+
+[1]
+While iterating, we can put only the element count that is greater or equal than `max_count` to `ans`.
+If we encounter a new element with larger `curr_count`, we reset the `ans`.
 
+[0]
+With the help of `prev_val` we can know that `curr_node` is the same to the previous or not.
+If not, its a new element, we need to reset the `curr_count`.
+
+Time: O(N). Space: O(LogN)
+
+For better understanding, below is a template for inorder traverse.
+"""
 class Solution(object):
     def findMode(self, root):
         if not root: return []
@@ -54,23 +69,6 @@ def findMode(self, root):
                 
         return ans
 
-"""
-To use the feature of BST, we are going to inorder traverse the BST.
-So it will be like we are iterating a sorted array.
-
-[1]
-While iterating, we can put only the element count that is greater or equal than `max_count` to `ans`.
-If we encounter a new element with larger `curr_count`, we reset the `ans`.
-
-[0]
-With the help of `prev_val` we can know that `curr_node` is the same to the previous or not.
-If not, its a new element, we need to reset the `curr_count`.
-
-Time: O(N). Space: O(LogN)
-
-For better understanding, below is a template for inorder traverse.
-"""
-
 #inorder traversal of BST
 def inorder_traverse(root):
     curr = root
@@ -85,3 +83,28 @@ def inorder_traverse(root):
         print curr.val
         
         curr = curr.right
+
+
+
+
+"""
+Time: O(N)
+Space: O(N)
+"""
+class Solution(object):
+    def findMode(self, root):
+        def helper(node):
+            if not node: return
+            counter[node.val] += 1
+            counter['maxCount'] = max(counter['maxCount'], counter[node.val])
+            helper(node.left)
+            helper(node.right)
+        
+        ans = []
+        counter = collections.Counter()
+        helper(root)
+        for v in counter:
+            if v!='maxCount' and counter[v]==counter['maxCount']:
+                ans.append(v)
+        
+        return ans
diff --git a/problems/insert-into-a-binary-search-tree.py b/problems/insert-into-a-binary-search-tree.py
@@ -1,3 +1,7 @@
+"""
+Time complexity: O(LogN)
+Space complexity: O(1)
+"""
 class Solution(object):
     def insertIntoBST(self, root, val):
         if not root: return TreeNode(val)
@@ -19,8 +23,26 @@ def insertIntoBST(self, root, val):
         
         return None
 
-
 """
 Time complexity: O(LogN)
-Space complexity: O(1)
-"""
+Space complexity: O(LogN)
+"""
+class Solution(object):
+    def insertIntoBST(self, root, val):
+        def helper(node, val):
+            if not node: return
+            if val<node.val:
+                if node.left:
+                    helper(node.left, val)
+                else:
+                    node.left = TreeNode(val)
+            else:
+                if node.right:
+                    helper(node.right, val)
+                else:
+                    node.right = TreeNode(val)
+        
+        if not root: return TreeNode(val)
+        helper(root, val)
+        return root
+        
