leetcode-008

Alpha

*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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# 295. Find Median from Data Stream

from heapq import *

class MedianFinder:

def __init__(self):
self.heaps = [], []

def addNum(self, num: int) -> None:
small, large = self.heaps
heappush(small, -heappushpop(large, num))
if len(large) < len(small):
heappush(large, -heappop(small))

def findMedian(self) -> float:
small, large = self.heaps
if len(large) > len(small):
return float(large[0])
return (large[0] - small[0]) / 2.0


class MedianFinder1:
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

def addNum(self, num):
if len(self.small) == len(self.large):
heappush(self.large, -heappushpop(self.small, -num))
else:
heappush(self.small, -heappushpop(self.large, num))

def findMedian(self):
if len(self.small) == len(self.large):
return float(self.large[0] - self.small[0]) / 2.0
else:
return float(self.large[0])

EQ-2

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 759. Employee Free Time

"""
# Definition for an Interval.

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

return res

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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
# 140. Word Break II

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:])

cache[i] = ans
return ans

return dp(0)


class Solution0:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
return self.find(s, wordDict, {})

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


class Solution1:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
memo = {len(s): ['']}

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
# 430. Flatten a Multilevel Doubly Linked 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
"""

class Solution:
def flatten(self, head: 'Node') -> 'Node':
if not 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


def flatten_dfs(self, prev, curr):
""" return the tail of the flatten list """
if not 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)


class Solution1:
def flatten(self, head):
if not head:
return None

dummy = prev = Node(0, None, None, None)
stk = [head]
while stk:
node = stk.pop()
prev.next = node
node.prev = prev
if node.next:
stk.append(node.next)
if node.child:
stk.append(node.child)
node.child = None
prev = node

dummy.next.prev = None
return dummy.next

EQ-5

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 215. Kth Largest Element in an Array

class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
return sorted(nums)[-k]

class Solution1:
# @param {integer[]} nums
# @param {integer} k
# @return {integer}
def findKthLargest(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):
return self.findKthLargest(right, k)
elif (k - len(right)) <= len(equal):
return equal[0]
else:
return self.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"]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# 93. Restore IP Addresses

class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
res = []
self.helper(s, 0, [], res)
return res

def helper(self, s, length, ips, res):
if not s:
if length == 4:
res.append('.'.join(ips))
return
if length == 4:
return
self.helper(s[1:], length + 1, ips + [s[:1]], res)
if s[0] != '0':
if len(s) > 1:
self.helper(s[2:], length + 1, ips + [s[:2]], res)
if len(s) > 2 and int(s[:3]) < 256:
self.helper(s[3:], length + 1, ips + [s[:3]], res)


class Solution1:
def restoreIpAddresses(self, s: str) -> List[str]:
res = []
self.dfs(s, 0, "", res)
return res

def dfs(self, s, index, path, res):
if index == 4:
if not s:
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 == 2 and 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 == 3 and 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# 227. Basic Calculator II

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
return sum(stack)


class Solution1:
def calculate(self, s: str) -> int:
if not s:
return "0"
stack, num, sign = [], 0, "+"
for i in range(len(s)):
if s[i].isdigit():
num = num*10+ord(s[i])-ord("0")
if (not s[i].isdigit() and not s[i].isspace()) or i == len(s)-1:
if sign == "-":
stack.append(-num)
elif sign == "+":
stack.append(num)
elif sign == "*":
stack.append(stack.pop()*num)
else:
tmp = stack.pop()
if tmp//num < 0 and tmp%num != 0:
stack.append(tmp//num+1)
else:
stack.append(tmp//num)
sign = s[i]
num = 0
return sum(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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# 572. Subtree of Another Tree

# 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.val and
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
# 212. Word Search II

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

class Solution:
def fizzBuzz(self, n: int) -> List[str]:
return ['Fizz' * (not i % 3) + 'Buzz' * (not i % 5) or str(i) for i in range(1, n+1)]

Sigma

Feb 9, 2020
La Jolla, CA

Omega

https://leetcode.com/