added problems

AlveeM · AlveeM · commit 0196e445e6b4 · 2020-12-08T11:41:40.000-05:00
diff --git a/leetcode/patterns/09-two-heaps/01_find_median_from_data_stream.py b/leetcode/patterns/09-two-heaps/01_find_median_from_data_stream.py
@@ -0,0 +1,26 @@
+from heapq import heappush, heappop
+
+class MedianFinder:
+
+    def __init__(self):
+        """
+        initialize your data structure here.
+        """
+        self.max_heap = []
+        self.min_heap = []
+
+    def addNum(self, num: int) -> None:
+        if not self.max_heap or -self.max_heap[0] >= num:
+            heappush(self.max_heap, -num)
+        else:
+            heappush(self.min_heap, num)
+            
+        if len(self.max_heap) > len(self.min_heap) + 1:
+            heappush(self.min_heap, -heappop(self.max_heap))
+        elif len(self.max_heap) < len(self.min_heap):
+            heappush(self.max_heap, -heappop(self.min_heap))
+
+    def findMedian(self) -> float:
+        if len(self.max_heap) == len(self.min_heap):
+            return (-self.max_heap[0] + self.min_heap[0]) / 2.0
+        return -self.max_heap[0]
diff --git a/leetcode/patterns/10-subsets/01_subsets.py b/leetcode/patterns/10-subsets/01_subsets.py
@@ -0,0 +1,8 @@
+class Solution:
+    def subsets(self, nums):
+        subsets = [[]]
+        for num in nums:
+            n = len(subsets)
+            for i in range(n):
+                subsets.append(subsets[i].copy() + [num])
+        return subsets
diff --git a/leetcode/patterns/10-subsets/02_subsets_II.py b/leetcode/patterns/10-subsets/02_subsets_II.py
@@ -0,0 +1,18 @@
+class Solution:
+    def subsetsWithDup(self, nums):
+        nums.sort()
+        subsets = [[]]
+        endIdx = 0
+        
+        for i in range(len(nums)):
+            startIdx = 0
+            if i > 0 and nums[i] == nums[i-1]:
+                startIdx = endIdx + 1
+            
+            endIdx = len(subsets) - 1
+            for j in range(startIdx, endIdx+1):
+                subset = subsets[j][:]
+                subset.append(nums[i])
+                subsets.append(subset)
+                
+        return subsets
diff --git a/leetcode/patterns/10-subsets/03_permutations.py b/leetcode/patterns/10-subsets/03_permutations.py
@@ -0,0 +1,32 @@
+class Solution:        
+    def permute(self, nums):
+        self.res = []
+        self.backtrack(nums, [])
+        return self.res
+    
+    def backtrack(self, nums, path):
+        if len(nums) == len(path):
+            self.res.append(path[:])
+            return
+        
+        for num in nums:
+            if num in path:
+                continue
+            
+            path.append(num)
+            self.backtrack(nums, path)
+            path.pop()
+
+class Solution2:
+    def permute(self, nums):
+        self.res = []
+        self.backtrack(nums, [])
+        return self.res
+    
+    def backtrack(self, nums, path):
+        if not nums:
+            self.res.append(path)
+            return
+        
+        for i in range(len(nums)):
+            self.backtrack(nums[:i] + nums[i+1:], path + [nums[i]])
diff --git a/leetcode/patterns/10-subsets/04_letter_case_permutation.py b/leetcode/patterns/10-subsets/04_letter_case_permutation.py
@@ -0,0 +1,10 @@
+class Solution:
+    def letterCasePermutation(self, S):
+        res = [S]
+        for i in range(len(S)):
+            if S[i].isalpha():
+                n = len(res)
+                for j in range(n):
+                    string = res[j]
+                    res.append(string[:i] + string[i].swapcase() + string[i+1:])
+        return res
diff --git a/leetcode/patterns/10-subsets/05_generate_parenthesis.py b/leetcode/patterns/10-subsets/05_generate_parenthesis.py
@@ -0,0 +1,41 @@
+from collections import deque
+
+class Solution:
+    def generateParenthesis(self, n):
+        res = []
+        q = deque()
+        q.append({'s': '', 'open': 0, 'close': 0})
+        while q:
+            cur = q.popleft()
+            if cur['open'] == n and cur['close'] == n:
+                res.append(cur['s'])
+            else:
+                if cur['open'] < n:
+                    new_s = cur['s'] + '('
+                    new_open_c = cur['open'] + 1
+                    q.append({'s': new_s, 
+                              'open': new_open_c, 
+                              'close': cur['close']})
+                if cur['open'] > cur['close']:
+                    new_s = cur['s'] + ')'
+                    new_close_c = cur['close'] + 1
+                    q.append({'s': new_s,
+                             'open': cur['open'],
+                             'close': new_close_c})  
+        return res
+
+class Solution2:
+    def generateParenthesis(self, n):
+        self.res = []
+        self.n = n
+        self.backtrack('', 0, 0)
+        return self.res
+    
+    def backtrack(self, s, left, right):
+        if len(s) == self.n * 2:
+            self.res.append(s)
+            return
+        if left < self.n:
+            self.backtrack(s + '(', left+1, right)
+        if left > right:
+            self.backtrack(s + ')', left, right+1)
