23.03.26 Today’s Leetcode

2360. Longest Cycle in a Graph (hard)

class Solution:
    def longestCycle(self, edges: List[int]) -> int:
        n = len(edges)
        res = -1
        visited = [-1] * n
        def help(start):
            nonlocal res
            level = start
            que = deque([start])
            while que:
                temp = deque([])
                while que:
                    target = que.pop()
                    if target == -1:
                        continue
                    if visited[target] >= start:
                        print(target)
                        res = max(res, level - visited[target])
                        continue
                    temp.append(edges[target])
                    visited[target] = level
                que = temp
                level += 1
        
        for i in range(n):
            if visited[i] == -1:
                help(i)
        print(visited)
        return res

class Solution:
    def longestCycle(self, edges: List[int]) -> int:
        longest_cycle_len = -1
        time_step = 1
        node_visited_at_time = [0] * len(edges)

        for current_node in range(len(edges)):
            if node_visited_at_time[current_node] > 0:
                continue
            start_time = time_step
            u = current_node
            while u != -1 and node_visited_at_time[u] == 0:
                node_visited_at_time[u] = time_step
                time_step += 1
                u = edges[u]
            if u != -1 and node_visited_at_time[u] >= start_time:
                longest_cycle_len = max(longest_cycle_len, time_step - node_visited_at_time[u])

        return longest_cycle_len

2471. Minimum Number of Operations to Sort a Binary Tree by Level (medium)

# 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 minimumOperations(self, root: Optional[TreeNode]) -> int:
        level = []
        que = deque([root])
        while que:
            temp = deque([])
            level.append([])
            while que:
                tar = que.popleft()
                level[-1].append(tar.val)
                if tar.left: temp.append(tar.left)
                if tar.right: temp.append(tar.right)
            que = temp
        
        print(level)
        def counts(arr):
            sorted_arr = sorted(arr)
            num = 0
            print(sorted_arr, arr)
            for i in range(len(arr)):
                if sorted_arr[i] != arr[i]:
                    num += 1
            return num

        res = 0
        for p in level:
            # print(p, counts(p))
            res += counts(p)
        return (res + 1) // 2

class Solution:
    def minimumOperations(self, root: Optional[TreeNode]) -> int:
        ans = 0 
        queue = deque([root])
        while queue: 
            vals = []
            for _ in range(len(queue)): 
                node = queue.popleft()
                vals.append(node.val)
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
            mp = {x : i for i, x in enumerate(sorted(vals))}
            visited = [0]*len(vals)
            for i in range(len(vals)): 
                cnt = 0 
                while not visited[i] and i != mp[vals[i]]: 
                    visited[i] = 1
                    cnt += 1
                    i = mp[vals[i]]
                ans += max(0, cnt-1)
        return ans