23.03.15 Today’s Leetcode
958. Check Completeness of a Binary Tree (medium)
class Solution:
def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
res = True
q = deque([root])
state = 0
# 0 : two child
# 1 : left child
# 2 : no child
while q:
temp = deque([])
while q:
cur = q.popleft()
print(state, cur.val)
temp_state = 0
if cur.left and not cur.right:
temp_state = 1
if not cur.left and not cur.right:
temp_state = 2
if not cur.left and cur.right:
temp_state = -1
if state < temp_state:
state = temp_state
elif state == 1 and temp_state == 1:
return False
elif state > temp_state:
return False
if cur.left: temp.append(cur.left)
if cur.right: temp.append(cur.right)
q = temp
return True
959. Regions Cut By Slashes (medium)
IDEA Fails
class Solution:
def regionsBySlashes(self, grid: List[str]) -> int:
n = len(grid)
board = [[0 for i in range(n + 1)] for j in range(n + 1)]
for col in range(n):
for row in range(n):
s = grid[col][row]
if s == '\\':
board[col][row] = 1
board[col + 1][row + 1] = 1
if s == '/':
board[col][row + 1] = 1
board[col + 1][row] = 1
# print(board)
def spread(x, y):
nonlocal board
if x < 0 or x >= n + 1 or y < 0 or y >= n + 1:
return
if board[x][y] == 1:
return
board[x][y] = 1
spread(x + 1, y)
spread(x - 1, y)
spread(x, y + 1)
spread(x, y - 1)
count = 0
for x in range(n + 1):
for y in range(n + 1):
if board[x][y] == 0:
# print(board)
spread(x, y)
count += 1
return count
Union and Find
class UnionFind:
def __init__(self, n):
self.parent = [i for i in range(n)]
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, a, b):
self.parent[self.find(b)] = self.find(a)
class Solution:
def regionsBySlashes(self, grid: List[str]) -> int:
n = len(grid)
# Divide each square into 4 triangles
uf = UnionFind(4 * n * n)
for row in range(n):
for col in range(n):
cell = grid[row][col]
index = 4 * (row * n + col)
# When there are no lines in the square
if cell == ' ':
uf.union(index+0, index+1)
uf.union(index+1, index+2)
uf.union(index+2, index+3)
# When there's a bottom left - top right diagonal line dividing the square
if cell == '/':
uf.union(index+0, index+3)
uf.union(index+1, index+2)
# When there's a top left - bottom right diagonal line dividing the square
if cell == '\\':
uf.union(index+2, index+3)
uf.union(index+0, index+1)
# Connecting a square with square below it
if row < n - 1:
uf.union(index+2, (index + 4*n) + 0)
# Connecting a square with right side square
if col < n - 1:
uf.union(index+1, (index + 4) + 3)
output = 0
for i in range(4*n*n):
if uf.find(i) == i:
output += 1
return output
lee sensei’s solution link
def regionsBySlashes(self, grid):
f = {}
def find(x):
f.setdefault(x, x)
if x != f[x]:
f[x] = find(f[x])
return f[x]
def union(x, y):
f[find(x)] = find(y)
for i in xrange(len(grid)):
for j in xrange(len(grid)):
if i:
union((i - 1, j, 2), (i, j, 0))
if j:
union((i, j - 1, 1), (i, j, 3))
if grid[i][j] != "/":
union((i, j, 0), (i, j, 1))
union((i, j, 2), (i, j, 3))
if grid[i][j] != "\\":
union((i, j, 3), (i, j, 0))
union((i, j, 1), (i, j, 2))
return len(set(map(find, f)))
260. Single Number III (medium)
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
counter = Counter(nums)
res = []
for key in counter.keys():
if counter[key] == 1:
res.append(key)
return res
274. H-Index (medium)
class Solution:
def hIndex(self, citations: List[int]) -> int:
cit = [-i for i in citations]
heapify(cit)
res = 0
i = 1
while i <= len(citations):
val = heappop(cit)
if -val < i:
break
else:
res = i
i += 1
return res
275. H-Index II (medium)
class Solution:
def hIndex(self, citations: List[int]) -> int:
n = len(citations)
left, right = 0, n - 1
while left <= right:
mid = (left + right) // 2
if citations[mid] == n - mid:
return n - mid
elif citations[mid] < n - mid:
left = mid + 1
else:
right = mid - 1
return n - left
284. Peeking Iterator (medium)
# Below is the interface for Iterator, which is already defined for you.
#
# class Iterator:
# def __init__(self, nums):
# """
# Initializes an iterator object to the beginning of a list.
# :type nums: List[int]
# """
#
# def hasNext(self):
# """
# Returns true if the iteration has more elements.
# :rtype: bool
# """
#
# def next(self):
# """
# Returns the next element in the iteration.
# :rtype: int
# """
class PeekingIterator:
def __init__(self, iterator):
"""
Initialize your data structure here.
:type iterator: Iterator
"""
self.arr = []
while iterator.hasNext():
self.arr.append(iterator.next())
print(self.arr)
self.index = 0
self.size = len(self.arr)
def peek(self):
"""
Returns the next element in the iteration without advancing the iterator.
:rtype: int
"""
return self.arr[self.index]
def next(self):
"""
:rtype: int
"""
if not self.hasNext():
return -1
self.index += 1
return self.arr[self.index - 1]
def hasNext(self):
"""
:rtype: bool
"""
return not (self.index >= self.size)
# Your PeekingIterator object will be instantiated and called as such:
# iter = PeekingIterator(Iterator(nums))
# while iter.hasNext():
# val = iter.peek() # Get the next element but not advance the iterator.
# iter.next() # Should return the same value as [val].
289. Game of Life (medium)
class Solution:
def gameOfLife(self, board: List[List[int]]) -> None:
m = len(board)
n = len(board[0])
for i in range(m):
for j in range(n):
ones = 0
for x in range(max(0, i - 1), min(m, i + 2)):
for y in range(max(0, j - 1), min(n, j + 2)):
ones += board[x][y] & 1
# Any live cell with 2 or 3 live neighbors
# lives on to the next generation
if board[i][j] == 1 and (ones == 3 or ones == 4):
board[i][j] |= 0b10
# Any dead cell with exactly 3 live neighbors
# becomes a live cell, as if by reproduction
if board[i][j] == 0 and ones == 3:
board[i][j] |= 0b10
for i in range(m):
for j in range(n):
board[i][j] >>= 1
299. Bulls and Cows (medium)
class Solution:
def getHint(self, secret: str, guess: str) -> str:
num_bulls = 0
num_cows = 0
a, b = Counter(secret), Counter(guess)
n = len(secret)
for i in range(n):
if secret[i] == guess[i]:
num_bulls += 1
a[secret[i]] -= 1
b[secret[i]] -= 1
# print(a, b)
c = a & b
for key in c.keys():
num_cows += c[key]
return str(num_bulls) + 'A' + str(num_cows) + 'B'
287. Find the Duplicate Number (medium)
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
counter = Counter(nums)
for key in counter.keys():
if counter[key] > 1:
return key
return -1