leetcode 382

Partho Biswas · Partho Biswas · commit 3c0714670e81 · 2019-11-08T23:11:21.000+06:00
diff --git a/leetcode.com/python/392_Is_Subsequence.py b/leetcode.com/python/392_Is_Subsequence.py
@@ -0,0 +1,58 @@
+from collections import defaultdict
+from bisect import bisect_left
+
+# Using Binary search
+class Solution(object):
+    def createMap(self, s):
+        # create a map. key is char. value is index of apperance in acending order.
+        posMap = defaultdict(list)
+        for i, char in enumerate(s):
+            posMap[char].append(i)
+        return posMap
+
+    def isSubsequence(self, s, t):
+        """
+        :type s: str
+        :type t: str
+        :rtype: bool
+        """
+        posMap = self.createMap(t)
+        # lowBound is the minimum index the current char has to be at.
+        lowBound = 0
+        for char in s:
+            if char not in posMap: return False
+            charIndexList = posMap[char]
+            # try to find an index that is larger than or equal to lowBound
+            i = bisect_left(charIndexList, lowBound)
+            if i == len(charIndexList): return False
+            lowBound = charIndexList[i] + 1
+        return True
+
+
+# Using  Two Pointer
+# class Solution(object):
+#     def isSubsequence(self, s, t):
+#         """
+#         :type s: str
+#         :type t: str
+#         :rtype: bool
+#         """
+#         if len(s) == 0:
+#             return True
+#         if len(t) == 0:
+#             return False
+#         i, j = 0, 0
+#         while i < len(s) and j < len(t):
+#             if s[i] == t[j]:
+#                 i += 1
+#             j += 1
+#         return True if i == len(s) else False
+
+
+
+
+sol = Solution()
+s = "abc"
+t = "ahbgdca"
+out = sol.isSubsequence(s, t)
+print('Res: ', out)
diff --git a/leetcode.com/python/621_Task_Scheduler.py b/leetcode.com/python/621_Task_Scheduler.py
@@ -0,0 +1,73 @@
+from heapq import heappush, heappop
+from collections import Counter
+
+
+# Task Scheduler - https://leetcode.com/problems/task-scheduler/
+
+class Solution:
+    def inverse(self, num):
+        return -1 * num
+
+    def leastInterval(self, tasks, n):
+        """
+        :type tasks: List[str]
+        :type n: int
+        :rtype: int
+        """
+        # What are the inputs here
+        #   - tasks - a list of strings the represent information we're processing
+        #   - n - the time between tasks of the exact same time. This would leave us room to process other tasks
+        # we asking for here?
+        #   - We're looking for an int as an output. That's because we're returning a count
+        #   - We're looking for the minimum number of intervals that we're going to use for the problem
+
+        # How I think we're going to solve the problem
+        # 1. We process the most important tasks often
+        #   - That's because we want to process everything quickly, and processing it quickly means processing the most frequent tasks immediately after the cooldown time is over is necessary.
+        # 2. Determine my interval
+        #   - I want to be able to determine what step I'm at
+        # 3. Create a dict of counts since I last processed my task
+
+        # Task map to store if we've seen the item before
+        task_count = Counter(tasks)
+        current_time = 0
+        current_heap = []
+
+        # Sorting from least to greatest inside of the heap current_heap
+        for k, v in task_count.items():
+            heappush(current_heap,
+                     (self.inverse(v), k))  # Pushes item from least to greatest (hence the negative values)
+
+        # Here we're running through the entire heap and processing the sorted tasks
+        while current_heap:  # We're running until this list runs out because we intend to pop elements from it
+            index, temp = 0, []
+            while index <= n:
+                current_time += 1  # We're counting the interval time here
+                if current_heap:
+                    timing, taskid = heappop(current_heap)
+                    # We're checking to see if it's at the end of the overall count.
+                    # Remember that it was negative at the beginning
+                    if timing != -1:
+                        temp.append((timing + 1, taskid))
+                # Checking to see if we're out of tasks. Exit the inner loop if both are true.
+                # This will automatically exit out of the overall tasks
+                if not current_heap and not temp:
+                    break
+                else:
+                    index += 1
+            # Because we transfered all of the items from the heap to temp, we're transferring them back to know if we should continue
+            # heap -> If we're not out of tasks -> temp
+            # temp -> Because we're not out -> heap
+            for item in temp:
+                heappush(current_heap, item)
+            # We only stop if we're out of tasks
+            # (Constantly checking the current_heap for if it's empty)
+        return current_time
+
+
+
+sol = Solution()
+tasks = ["A","A","A","B","B","B"]
+n = 2
+output = sol.leastInterval(tasks, n)
+print('Res: ', output)
