Scribbling

In this post, I am dealing with 'magic methods' to create more pythonic data models. First Example: Card Deck Card = namedtuple('Card', ['rank', 'suit']) class FrenchDeck: ranks = [str(n) for n in range(2, 11)] + list('JQKA') suits = ['Spades', 'Diamonds', 'Hearts', 'Clubs'] def __init__(self): self._cards = [Card(rank, suit) for suit in FrenchDeck.suits for rank in FrenchDeck.ranks] def __len__..

The very first thing to do is looking for matches. We don't need to use any fancy algorithms when looking for matches in this problem because it is guranteed that replacements will not overlap. Now we have matched list in the form of [index, source, target]. If you are planning to replace s directly, it will lead to bad time complexity as you will have to copy all the characters of s each time y..

1. Use deep copy list function copy() can be troublesome when the list has mutable objects. from copy import deepcopy l1 = [1, 2, [3, 4]] l2 = l1.copy() l3 = deepcopy(l1) l1[1] = 3 l1[2][0] = 4 print(l2) print(l3) 2. while--else for--else else part is executed when the loop is stopped by 'break' or when the loop wasn't executed. i = 0 while i > 10: print(i) else: print('no') for x in range(10): ..

class Solution: def calculate(self, s: str) -> int: # ' ' is intentionally added, # to mark the end of the given string s # encountering ' ' will add the last number to the stack self.s = s + ' ' self.ptr = 0 return self.calc() def calc(self): num, stack, sign = 0, [], '+' while self.ptr < len(self.s): c = self.s[self.ptr] # if met with '(', # get the evaluated number by recursion if c == '(': s..

Using double trie structures for prefix and suffix. Somewhat straightforward if one already knows about trie. If not, refer to "LeetCode prob 208. Implement Trie (Prefix Tree)". class WordFilter: def __init__(self, words: List[str]): wordDict = {} for idx, word in enumerate(words): wordDict[word] = idx self.PrefixTree = {} self.SuffixTree = {} for word, idx in wordDict.items(): node = self.Prefi..

class Solution: def getOrder(self, tasks: List[List[int]]) -> List[int]: import heapq ret = [] TaskHeap = [] WaitHeap = [] for idx, task in enumerate(tasks): heapq.heappush(TaskHeap, (task[0], idx, task[1])) curTime = 0 while True: if not WaitHeap: if not TaskHeap: break startTime, idx, processTime = heapq.heappop(TaskHeap) heapq.heappush(WaitHeap, (processTime, idx, startTime)) while TaskHeap a..

class Solution: def trapRainWater(self, heightMap: List[List[int]]) -> int: import heapq boundaries = [] m, n = len(heightMap), len(heightMap[0]) visited = [[False] * n for _ in range(m)] for y in range(m): for x in range(n): if y == 0 or y == m - 1 or x == 0 or x == n - 1: heapq.heappush(boundaries, (heightMap[y][x], y, x)) visited[y][x] = True ret = 0 dy, dx = [0, 1, 0, -1], [1, 0, -1, 0] whil..

class Solution: def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int: from math import atan2, pi from bisect import bisect_right numLoc = 0 angles = [] for point in points: x, y = point[0] - location[0], point[1] - location[1] if x == 0 and y == 0: numLoc += 1 else: val = atan2(y, x) * 180 / pi if val < 0: val += 360 angles.append(val) angles.sort() angles += ..

Key observations needed to solve this prob are as below. 1) There is no need to push the same button twice, as it doesn't make any change. 2) Sequence of buttons doesn't matter. In the provided example, a possible solution was (1,0)->(0,1)->(1,1). However, any sequences of the three buttons produce the same result. Functions we need: 1) isComplete(): checks whether matrix only has zeros or not 2..

Solution below is not very efficient, however, is seemingly intuitive and easy to understand. The core idea is to reuse solution for "57. Insert Interval". (Link: https://leetcode.com/problems/insert-interval/) The problem is about inserting an interval such that intervals are sorted in ascending order while not having any overlapping intervals. We can use exactly the same idea to implement "add..