# Weekly Contest 270
# 2094. Finding 3-Digit Even Numbers
# Solution
Instead of search through all indexs, seach through [100, 999] would lead to a less time complexity.
class Solution:
def findEvenNumbers(self, digits):
c = Counter(digits)
res = []
for i in range(100, 999, 2):
temp = str(i)
tempC = Counter(temp)
flag = True
for key in tempC:
if tempC[key] > c[int(key)]:
flag = False
break
if flag:
res.append(i)
return res
# 2095. Delete the Middle Node of a Linked List
2095. Delete the Middle Node of a Linked List
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
cnt = 0
node = head
if node.next is None:
return None
while node is not None:
cnt += 1
node = node.next
mid = cnt // 2
prev = None
node = head
next_node = node.next
cur = 0
while cur < mid:
prev = node
node = node.next
next_node = next_node.next
cur += 1
prev.next = next_node
return head
# Leetcode 2096
[2096. Step-By-Step Directions From a Binary Tree Node to Anotherr](\2096. Step-By-Step Directions From a Binary Tree Node to Another)
Classic LCA problem
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
self.father_dic = {}
def helper(node, father, isLeft):
self.father_dic[node.val] = (father, isLeft)
if node.left is not None:
helper(node.left, node.val, True)
if node.right is not None:
helper(node.right, node.val, False)
helper(root, None, False)
print(self.father_dic)
visited = set()
node = startValue
path = ""
while node is not None:
visited.add(node)
node = self.father_dic[node][0]
node = destValue
while node not in visited:
if self.father_dic[node][1]:
path = 'L' + path
else:
path = 'R' + path
node = self.father_dic[node][0]
startNode = startValue
while startNode != node:
path = "U" + path
startNode = self.father_dic[startNode][0]
return path
# Leetcode 2097
2097. Valid Arrangement of Pairs
Current solution leads to TLE, working on improvement.
class Solution:
def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:
out_d = defaultdict(set)
in_d = defaultdict(set)
for start, end in pairs:
out_d[start].add(end)
in_d[end].add(start)
start_node = None
for key in out_d:
if key not in in_d:
start_node = key
break
if start_node is None:
start_node = pairs[0][0]
self.res = None
def dfs(start, path):
if len(path) == len(pairs):
self.res = list(path)
return
for node in out_d[start]:
if len(out_d[node]) == 0 and len(path) != len(pairs) - 1:
continue
if self.res is not None:
return
out_d[start].remove(node)
path.append([start, node])
dfs(node, path)
path.pop()
out_d[start].add(node)
dfs(start_node, [])
return self.res
Improvement: Hierholzer's Algorithm
def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:
g = defaultdict(list) # graph
din, dout = Counter(), Counter() #in degree, out degree
for u, v in pairs:
g[u].append(v)
dout[u] += 1
din[v] += 1
S = pairs[0][0] # Start anywhere if it's an Eulerian cycle.
for p in dout:
if dout[p] - din[p] == 1: # It's an Eulerian trail. Have to start here
S = p
break
# Hierholzer's Algorithm:
route = []
st = [S]
while st:
while g[st[-1]]:
st.append(g[st[-1]].pop())
route.append(st.pop())
route.reverse()
return [[route[i], route[i+1]] for i in range(len(route)-1)]