23.04.27 Today’s Leetcode
319. Bulb Switcher (medium)
class Solution:
def bulbSwitch(self, n: int) -> int:
return (int)(n ** 0.5)
672. Bulb Switcher II (medium)
class Solution:
def flipLights(self, n, p):
return [[1,1,1], [2,3,4], [2,4,7], [2,4,8]][min(p, 3)][min(n - 1, 2)]
341. Flatten Nested List Iterator (medium)
# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger:
# def isInteger(self) -> bool:
# """
# @return True if this NestedInteger holds a single integer, rather than a nested list.
# """
#
# def getInteger(self) -> int:
# """
# @return the single integer that this NestedInteger holds, if it holds a single integer
# Return None if this NestedInteger holds a nested list
# """
#
# def getList(self) -> [NestedInteger]:
# """
# @return the nested list that this NestedInteger holds, if it holds a nested list
# Return None if this NestedInteger holds a single integer
# """
class NestedIterator:
def __init__(self, nestedList: [NestedInteger]):
def help(arr):
temp = []
for elem in arr:
if elem.isInteger():
temp.append(elem.getInteger())
else:
temp.extend(help(elem.getList()))
# print(temp)
return temp
# print(nestedList)
self.d = help(nestedList)
self.index = 0
def next(self) -> int:
self.index += 1
return self.d[self.index - 1]
def hasNext(self) -> bool:
return self.index < len(self.d)
# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())
385. Mini Parser (medium)
# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger:
# def __init__(self, value=None):
# """
# If value is not specified, initializes an empty list.
# Otherwise initializes a single integer equal to value.
# """
#
# def isInteger(self):
# """
# @return True if this NestedInteger holds a single integer, rather than a nested list.
# :rtype bool
# """
#
# def add(self, elem):
# """
# Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
# :rtype void
# """
#
# def setInteger(self, value):
# """
# Set this NestedInteger to hold a single integer equal to value.
# :rtype void
# """
#
# def getInteger(self):
# """
# @return the single integer that this NestedInteger holds, if it holds a single integer
# Return None if this NestedInteger holds a nested list
# :rtype int
# """
#
# def getList(self):
# """
# @return the nested list that this NestedInteger holds, if it holds a nested list
# Return None if this NestedInteger holds a single integer
# :rtype List[NestedInteger]
# """
class Solution:
def deserialize(self, s: str) -> NestedInteger:
num = ''
stack = []
res = None
for c in s:
if c.isdigit() or c == '-':
num += c
continue
if c == '[':
ne = NestedInteger()
if stack:
stack[-1].add(ne)
stack +=[ne]
elif c == ',' and num:
stack[-1].add(NestedInteger(int(num)))
num = ''
elif c == ']':
if num:
stack[-1].add(NestedInteger(int(num)))
num = ''
res = stack.pop()
return res if res else NestedInteger(int(num))
449. Serialize and Deserialize BST (medium)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Codec:
def serialize(self, root: Optional[TreeNode]) -> str:
def height(node):
if not node:
return 0
return 1 + max(height(node.left), height(node.right))
def dfs(cur, index):
if not cur:
return
arr[index] = str(cur.val)
dfs(cur.left, index * 2)
dfs(cur.right, index * 2 + 1)
h = height(root)
arr = ['-'] * (2 ** h)
dfs(root, 1)
print(arr)
return ','.join(arr)
def deserialize(self, data: str) -> Optional[TreeNode]:
arr = data.split(',')
n = len(arr)
d = {}
d[1] = None
print(arr)
for i in range(n - 1, -1, -1):
elem = arr[i]
if elem == '-':
continue
d[i] = TreeNode(int(elem))
if (i * 2) in d:
d[i].left = d[i * 2]
if (i * 2 + 1) in d:
d[i].right = d[i * 2 + 1]
print(d)
return d[1]
# Your Codec object will be instantiated and called as such:
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# tree = ser.serialize(root)
# ans = deser.deserialize(tree)
# return ans
class Codec:
def serialize(self, root: Optional[TreeNode]) -> str:
"""Encodes a tree to a single string."""
if not root:
return ""
stack = [root]
serialized = ""
while stack:
node = stack.pop()
if not node:
serialized += "$,"
else:
serialized += str(node.val) + ","
stack.append(node.right)
stack.append(node.left)
return serialized[:-1]
def deserialize(self, data: str) -> Optional[TreeNode]:
"""Decodes your encoded data to tree."""
if not data:
return None
values = data.split(",")
queue = deque(values)
return self._deserialize(queue)
def _deserialize(self, queue: Deque[str]) -> Optional[TreeNode]:
value = queue.popleft()
if value == "$":
return None
node = TreeNode(int(value))
node.left = self._deserialize(queue)
node.right = self._deserialize(queue)
return node