23.03.13 Today’s Leetcode
101. Symmetric Tree (easy)
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
def dfs(left, right):
if left == None and right == None:
return False
elif left == None:
return True
elif right == None:
return True
res = (left.val != right.val)
res |= dfs(left.left, right.right)
res |= dfs(left.right, right.left)
return res
return not dfs(root.left, root.right)
637. Average of Levels in Binary Tree (easy)
class Solution:
def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
q = deque([root])
res = []
while q:
temp = deque([])
sum_, count_ = 0, 0
while q:
tar = q.popleft()
sum_ += tar.val
count_ += 1
if tar.left: temp.append(tar.left)
if tar.right: temp.append(tar.right)
res.append(sum_ / count_)
q = temp
return res
967. Numbers With Same Consecutive Differences (medium)
class Solution:
def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
res = []
def dfs(cur):
if n - 1 <= log10(cur) and log10(cur) < n:
nonlocal res
res.append(cur)
return
last_digit = cur % 10
for i in range(10):
if abs(i - last_digit) == k:
dfs(cur * 10 + i)
for i in range(1, 10):
dfs(i)
return res
968. Binary Tree Cameras (hard)
class Solution:
def minCameraCover(self, root: Optional[TreeNode]) -> int:
if not root: return 0
def isLeaf(node):
return not node.left and not node.right
if isLeaf(root): return 1
res = 0
def dfs(node):
if not node:
return False
if isLeaf(node):
return False
isCamera = False
left, right = dfs(node.left), dfs(node.right)
if not left and not right:
isCamera = True
if isCamera:
node.val = 1
nonlocal res
res += 1
return isCamera
dfs(root)
return res
lee sensai’s Solution
Apply a recusion function dfs.
Return 0 if it’s a leaf.
Return 1 if it’s a parent of a leaf, with a camera on this node.
Return 2 if it’s coverd, without a camera on this node.
For each node,
if it has a child, which is leaf (node 0), then it needs camera.
if it has a child, which is the parent of a leaf (node 1), then it’s covered.
If it needs camera, then res++ and we return 1.
If it’s covered, we return 2.
Otherwise, we return 0.
class Solution:
def minCameraCover(self, root):
self.res = 0
def dfs(root):
if not root: return 2
l, r = dfs(root.left), dfs(root.right)
if l == 0 or r == 0:
self.res += 1
return 1
return 2 if l == 1 or r == 1 else 0
return (dfs(root) == 0) + self.res
1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold (medium)
class Solution:
def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
value = 0
for i in range(k):
value += arr[i]
n = len(arr)
count = 0
for i in range(n - k):
print(value)
if value / k >= threshold:
count += 1
value -= arr[i]
value += arr[i + k]
if value / k >= threshold:
count += 1
return count
2090. K Radius Subarray Averages (medium)
class Solution:
def getAverages(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
res = [-1] * n
value = sum(nums[:2 * k + 1])
for i in range(k, n - k):
# print(i, value)
res[i] = value // (2 * k + 1)
if i + k + 1 >= n:
break
value -= nums[i - k]
value += nums[i + k + 1]
return res
1609. Even Odd Tree (medium)
class Solution:
def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
if not root: return True
q = deque([root])
level = 0
while q:
temp = deque([])
prev = -1 if level % 2 == 0 else 10**6 + 1
while q:
tar = q.popleft()
print(tar.val)
if tar.val % 2 == level % 2:
return False
if level % 2 == 1:
if prev <= tar.val: return False
if level % 2 == 0:
if prev >= tar.val: return False
if tar.left: temp.append (tar.left)
if tar.right: temp.append (tar.right)
prev = tar.val
level += 1
q = temp
return True
2288. Apply Discount to Prices (medium)
class Solution:
def discountPrices(self, sentence: str, discount: int) -> str:
split = sentence.split(' ')
res = []
def func(word):
num = int(word[1:])
return f"$%.2f"% (num * (100 - discount) / 100)
for word in split:
if word[0] == '$' and word[1:].isnumeric(): res.append(func(word))
else: res.append(word)
return ' '.join(res)
905. Sort Array By Parity (easy)
class Solution:
def sortArrayByParity(self, nums: List[int]) -> List[int]:
even, odd = [], []
for num in nums:
if num % 2 == 0: even.append(num)
else: odd.append(num)
return even + odd
2164. Sort Even and Odd Indices Independently (easy)
class Solution:
def sortEvenOdd(self, nums: List[int]) -> List[int]:
even = deque(sorted(nums[::2]))
odd = deque(sorted(nums[1::2])[::-1])
print(even, odd)
res = []
while even and odd:
a, b = even.popleft(), odd.popleft()
res.append(a)
res.append(b)
while even:
res.append(even.popleft())
while odd:
res.append(odd.popleft())
return res
922. Sort Array By Parity II (easy)
class Solution:
def sortArrayByParityII(self, nums: List[int]) -> List[int]:
even, odd = deque([]), deque([])
for num in nums:
if num % 2 == 0: even.append(num)
else: odd.append(num)
res = []
while even and odd:
a, b = even.popleft(), odd.popleft()
res.append(a)
res.append(b)
while even:
res.append(even.popleft())
while odd:
res.append(odd.popleft())
return res