Leetcode LC-Contest

Weekly Contest 270

Leetcode 2094, 2095, 2095, 2097

Sailorlqh
2021-12-08
4 min

# 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)]