Leetcode solutions 1.5
3 min readMar 30, 2019
728. Self Dividing Numbers
def selfDividingNumbers(self, left, right):
"""
:type left: int
:type right: int
:rtype: List[int]
"""
output = []
for num in range(left, right+1):
temp_num = num
digits = []
isSelfDividing = True
while temp_num:
d = temp_num % 10
temp_num = temp_num // 10
if d == 0:
isSelfDividing = False
break
else:
digits.append(d)
if not isSelfDividing:
continue
else:
for d in digits:
if num % d != 0:
isSelfDividing = False
break
if isSelfDividing:
output.append(num)
return output999. Available Captures for Rook
A very pythonic submission using zip(*board)
def numRookCaptures(self, board):
"""
:type board: List[List[str]]
:rtype: int
"""
count = 0
# columns
for x in zip(*board):
string = "".join(x).strip(".")
#print(string)
if "R" in string:
rook_position = string.find("R")
index_right = rook_position + 1
index_left = rook_position - 1
while index_right < len(string):
if string[index_right] == "p":
count += 1
break
elif string[index_right] == ".":
pass
else:
break
index_right += 1
while index_left >= 0:
if string[index_left] == "p":
count += 1
break
elif string[index_left] == ".":
pass
else:
break
index_left -= 1
# rows
for x in board:
string = "".join(x).strip(".")
# print(string)
if "R" in string:
rook_position = string.find("R")
index_right = rook_position + 1
index_left = rook_position - 1
while index_right < len(string):
if string[index_right] == "p":
count += 1
break
elif string[index_right] == ".":
pass
else:
break
index_right += 1
while index_left >= 0:
if string[index_left] == "p":
count += 1
break
elif string[index_left] == ".":
pass
else:
break
index_left -= 1
return count589. N-ary Tree Preorder Traversal
#dfs #preorder # stack
def preorder(self, root):
"""
:type root: Node
:rtype: List[int]
"""
queue = [root]
output = []
while queue:
node = queue.pop()
if node:
output.append(node.val)
queue.extend(list(reversed(node.children)))
return output933. Number of Recent Calls
def __init__(self):
self.q = collections.deque()
def ping(self, t: int) -> int:
self.q.append(t)
while self.q[0] < t-3000:
self.q.popleft()
return len(self.q)605. Can Place Flowers
# Corner case hell !
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
index = 0
if len(flowerbed) == 0:
return False
if n == 0:
return True
if len(flowerbed) == 1:
if flowerbed[0] == 0 and n == 1:
return True
else:
return Falsewhile index < len(flowerbed) and n > 0:
if index == 0 and flowerbed[index + 1] == 0 and flowerbed[index] == 0:
n-=1
flowerbed[index] = 1
elif index == len(flowerbed) - 1 and flowerbed[index - 1] == 0 and flowerbed[index] == 0:
n-=1
flowerbed[index] = 1
elif index < len(flowerbed) - 1 and flowerbed[index-1] == 0 and flowerbed[index + 1] == 0 and flowerbed[index] == 0:
n-=1
flowerbed[index] = 1
index += 1
if n == 0:
return True
else:
return False
394. Decode String
# AppDynamics USC on-campus interview
# Stack
3 main points to consider here :
- digits can be more than 1 eg. “3[a10[bc]]”
- account for null string
- whenever pushing a solved string to the stack check if stack top is a string and concat it to the stack top if it exists
class Solution:
def format_string(self, substr: str, k: int) -> str:
return "".join([substr for i in range(k)])
def decodeString(self, s: str) -> str:
index = 0
stack = []
if not s:
return ""while index < len(s):
# print(index, stack)
if s[index].isdigit():
concat_digit = ""
# print('isdigit')
while s[index].isdigit():
concat_digit += s[index]
index += 1
stack.append(concat_digit)
elif s[index].isalpha():
concated_string = ""
while index < len(s) and s[index].isalpha():
concated_string += s[index]
index += 1
if stack:
stack[-1] = stack[-1] + concated_string
else:
stack.append(concated_string)
elif s[index] == '[':
index += 1
concated_string = ""
while s[index].isalpha():
concated_string += s[index]
index += 1
stack.append(concated_string)
elif s[index] == ']':
string = stack.pop()
k = stack.pop()
if stack:
stack[-1] = stack[-1] + self.format_string(string, int(k))
else:
stack.append(self.format_string(string, int(k)))
index += 1
while stack:
if len(stack) == 1:
return stack[0]
else:
if stack[-2].isdigit():
string = stack.pop()
k = stack.pop()
stack.append(self.format_string(string, int(k)))
elif stack[-2].isalpha():
str2 = stack.pop()
str1 = stack.pop()
stack.append(str1 + str2)
590. N-ary Tree Postorder Traversal
# DFS # queue # postorder
class Solution:
def postorder(self, root: 'Node') -> List[int]:
queue = [root]
output = []
while queue:
node = queue.pop()
if type(node) == int:
output.append(node)
elif node:
queue.append(node.val)
queue.extend(list(reversed(node.children)))
return output429. N-ary Tree Level Order Traversal
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
stack = [(0, root)]
output = []
while stack:
level, node = stack.pop()
if node:
if len(output) > level:
output[level].append(node.val)
else:
output.append([node.val])
stack.extend([(level + 1, i) for i in list(reversed(node.children))])
return output
