*Find Median from Data Stream Employee Free Time Word Break II *Flatten a Multilevel Doubly Linked List Kth Largest Element in an Array
Restore IP Addresses Basic Calculator II Subtree of Another Tree *Word Search II Fizz Buzz
Beta
EQ-1
Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
defaddNum(self, num: int) -> None: small, large = self.heaps heappush(small, -heappushpop(large, num)) if len(large) < len(small): heappush(large, -heappop(small))
deffindMedian(self) -> float: small, large = self.heaps if len(large) > len(small): return float(large[0]) return (large[0] - small[0]) / 2.0
classMedianFinder1: def__init__(self): self.small = [] # the smaller half of the list, max heap (invert min-heap) self.large = [] # the larger half of the list, min heap
We are given a list schedule of employees, which represents the working time for each employee. Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order. Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.
class Interval: def __init__(self, start:int = None, end: int = None): self.start = start self.end = end """
class Solution: def employeeFreeTime(self, schedule: List[List[List[int]]]) -> List[List[int]]: a = [i for s in schedule for i in s] ints = sorted(a, key=lambda x: x.start)
res, pre = [], ints[0] for i in ints[1:]: if i.start <= pre.end and i.end > pre.end: pre.end = i.end elif i.start > pre.end: res.append(Interval(pre.end, i.start)) pre = i
returnres
EQ-3
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.
The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.
class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> List[str]: cache = {} wordDict = set(wordDict) if len(wordDict) == 0: return [] max_len = float('-inf') for word in wordDict: max_len = max(max_len, len(word))
def dp(i): if i in cache: return cache[i]
ans = [] j = i while j < len(s) and j - i <= max_len: if s[i:j] in wordDict: suffixes = dp(j) for suffix in suffixes: ans.append(s[i:j] + " " + suffix) j += 1 if s[i:] in wordDict: ans.append(s[i:])
def find(self, s, wordDict, record): if s in record: return record[s] result = [] if not s: result.append('') return result for word in wordDict: if s.startswith(word): for ss in self.find(s[len(word):], wordDict, record): if ss: result.append(word +' ' + ss) else: result.append(word) record[s] = result return result
def sentences(i): if i not in memo: memo[i] = [s[i:j] + (tail and' ' + tail) for j in range(i+1, len(s)+1) if s[i:j] in wordDict for tail in sentences(j)] return memo[i]
return sentences(0)
EQ-4
You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below. Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.
""" # Definition for a Node. class Node: def __init__(self, val, prev, next, child): self.val = val self.prev = prev self.next = next self.child = child """ classSolution: defflatten(self, head: 'Node') -> 'Node': ifnot head: return head
# pseudo head to ensure the `prev` pointer is never none pseudoHead = Node(None, None, head, None) self.flatten_dfs(pseudoHead, head)
# detach the pseudo head from the real head pseudoHead.next.prev = None return pseudoHead.next
defflatten_dfs(self, prev, curr): """ return the tail of the flatten list """ ifnot curr: return prev
curr.prev = prev prev.next = curr
# the curr.next would be tempered in the recursive function tempNext = curr.next tail = self.flatten_dfs(curr, curr.child) curr.child = None return self.flatten_dfs(tail, tempNext)
classSolution1: # @param {integer[]} nums # @param {integer} k # @return {integer} deffindKthLargest(self, nums, k): # QuickSelect idea: AC in 52 ms # --------------------------- # pivot = nums[0] left = [l for l in nums if l < pivot] equal = [e for e in nums if e == pivot] right = [r for r in nums if r > pivot]
if k <= len(right): returnself.findKthLargest(right, k) elif (k - len(right)) <= len(equal): return equal[0] else: returnself.findKthLargest(left, k - len(right) - len(equal))
EQ-6
Given a string containing only digits, restore it by returning all possible valid IP address combinations. Input: "25525511135" Output: ["255.255.11.135", "255.255.111.35"]
classSolution1: defrestoreIpAddresses(self, s: str) -> List[str]: res = [] self.dfs(s, 0, "", res) return res
defdfs(self, s, index, path, res): if index == 4: ifnots: res.append(path[:-1]) return# backtracking
for i in range(1, 4): # the digits we choose should no more than the length of s if i <= len(s): #choose one digit if i == 1: self.dfs(s[i:], index+1, path+s[:i]+".", res) #choose two digits, the first one should not be "0" elif i == 2and s[0] != "0": self.dfs(s[i:], index+1, path+s[:i]+".", res) #choose three digits, the first one should not be "0", and should less than 256 elif i == 3and s[0] != "0"and int(s[:3]) <= 255: self.dfs(s[i:], index+1, path+s[:i]+".", res)
EQ-7
Implement a basic calculator to evaluate a simple expression string. The expression string contains only non-negative integers, +, -, \*, / operators and empty spaces ``. The integer division should truncate toward zero.
class Solution: # O(N) and O(N) def calculate(self, s: str) -> int: num, stack, pre_op = 0, [], '+' for c in s + '+': if c.isdigit(): num = num * 10 + int(c) elif not c.isspace(): if pre_op == '+': stack.append(num) elif pre_op == '-': stack.append(-num) elif pre_op == '*': stack.append(stack.pop() * num) elif pre_op == '/': stack.append(int(stack.pop() / num)) pre_op, num = c, 0 returnsum(stack)
class Solution1: def calculate(self, s: str) -> int: ifnot s: return"0" stack, num, sign = [], 0, "+" for i inrange(len(s)): if s[i].isdigit(): num = num*10+ord(s[i])-ord("0") if (not s[i].isdigit() andnot s[i].isspace()) or i == len(s)-1: ifsign == "-": stack.append(-num) elif sign == "+": stack.append(num) elif sign == "*": stack.append(stack.pop()*num) else: tmp = stack.pop() if tmp//num < 0and tmp%num != 0: stack.append(tmp//num+1) else: stack.append(tmp//num) sign = s[i] num = 0 returnsum(stack)
EQ-8
Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None
class Solution: def isSubtree(self, s: TreeNode, t: TreeNode, check: bool = False) -> bool: if not s and not t: return True if not s or not t: return False if s.val == t.val: check = True cond1 = self.isSubtree(s.left, t.left, check) cond2 = self.isSubtree(s.right, t.right, check) if cond1 and cond2: return True else: return self.isSubtree(s.left, t)or self.isSubtree(s.right, t) if check: return False return self.isSubtree(s.left, t)or self.isSubtree(s.right, t)
class Solution1: def isSubtree(self, s: TreeNode, t: TreeNode) -> bool: if self.isMatch(s, t): return True if not s: return False return self.isSubtree(s.left, t)or self.isSubtree(s.right, t)
def isMatch(self, s, t): if not(s and t): return s is t return (s.val == t.valand self.isMatch(s.left, t.left)and self.isMatch(s.right, t.right))
EQ-9
Given a 2D board and a list of words from the dictionary, find all words in the board. Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
class Solution: def findWords(self, board: List[List[str]], words: List[str]) -> List[str]: root = {} for word in words: node = root for c in word: node = node.setdefault(c, {}) node[None] = True board = {i + 1j*j: c for i, row in enumerate(board) for j, c in enumerate(row)}
found = [] def search(node, z, word): if node.pop(None, None): found.append(word) c = board.get(z) if c in node: board[z] = None for k in range(4): search(node[c], z + 1j**k, word + c) board[z] = c for z in board: search(root, z, '')
return found
class Solution: def findWords(self, board, words): def dfs(i, j, parent): letter = board[i][j]
node = parent[letter]
if '$' in node: ret.append(node.pop('$'))
board[i][j] = ''
i > 0 and board[i-1][j] in node and dfs(i-1, j, node) j + 1 < n and board[i][j+1] in node and dfs(i, j+1, node) i + 1 < m and board[i+1][j] in node and dfs(i+1, j, node) j > 0 and board[i][j-1] in node and dfs(i, j-1, node)
board[i][j] = letter if not node: parent.pop(letter)
alphabet = ''.join({''.join(row) for row in board}) match = re.compile('[' + alphabet + ']{1,}').fullmatch
words = {word.strip() for word in words if match(word)}
root = {} for word in words: curr = root for letter in word: if letter not in curr: curr[letter] = {} curr = curr[letter] curr['$'] = word
ret = [] m, n = len(board), len(board[0]) for i in range(m): for j in range(n): if board[i][j] in root: dfs(i, j, root)
return ret
class Solution: def findWords(self, board: List[List[str]], words: List[str]) -> List[str]: if not board or not words: return []
m = len(board) n = len(board[0]) trie = {}
for w in words: temp = trie for c in w: if c not in temp: temp[c] = {} temp = temp[c] temp['\n'] = w
def search(trie,i,j): c = board[i][j] temp = trie[c] board[i][j] = '' if '\n' in temp: self.ans.append(temp.pop('\n'))
if i>0 and board[i-1][j] in temp: search(temp, i-1, j) if j>0 and board[i][j-1] in temp: search(temp, i, j-1) if i<m-1 and board[i+1][j] in temp: search(temp, i+1, j) if j<n-1 and board[i][j+1] in temp: search(temp, i, j+1)
board[i][j] = c
self.ans = [] for i in range(m): for j in range(n): if board[i][j] in trie: search(trie,i,j)
return self.ans
EQ-10
Write a program that outputs the string representation of numbers from 1 to n. But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.
1 2 3 4 5
# 412. Fizz Buzz
classSolution: deffizzBuzz(self, n: int) -> List[str]: return ['Fizz' * (not i % 3) + 'Buzz' * (not i % 5) or str(i) for i in range(1, n+1)]