This is my 8th day of the November Gwen Challenge. Check out the final Gwen Challenge 2021 for more details

link

Leetcode-cn.com/contest/wee…

There are four questions in the weekly competition. Today is the analysis of the last two questions.

The title

2049. Count the nodes with the highest score

DFS

parsing

The problems of binary tree are mostly related to DFS/BFS. BFS is also known as hierarchical traversal. The DFS traversal modes of specific nodes can be divided into three types: pre-order, middle-order and post-order traversal. The maximum score required by this problem is abstracted from the result calculated by the number of left subtree elements, right subtree elements and the number of remaining elements of each node after the sequential traversal, compared with a maximum value and updated it.

There are two other points to note: first, the calculation method of maximum score is related to the number of left subtree elements, right subtree elements and the number of remaining elements, which can be divided into five cases, as shown in the code. The second point is the relationship between the maximum score and the maximum number of points. In fact, the logic of finding the maximum number of points is very simple, that is, use another variable to store the maximum number of points, set this variable as 1 every time a new maximum score occurs, and add this variable as 1 every time the same maximum score occurs.

code

class Solution:
    def countHighestScoreNodes(self, parents: List[int]) - >int:
        n = len(parents)
        nodes = [[None.None] for _ in range(0, n)]
        for i in range(1, n):
            parent = parents[i]
            if nodes[parent][0] is None:
                nodes[parent][0] = i
            else:
                nodes[parent][1] = i
        self.nodes = nodes
        self.n = n
        self.maxScore, self.maxScoreCount = 1.0
        self.childNumCount(0)
        return self.maxScoreCount
        
    def childNumCount(self, nodeInd) :
        if self.nodes[nodeInd][0] = =None:
            self.countScore(self.n-1)
            return 1
        elif self.nodes[nodeInd][1] = =None:
            leftChildNumCount = self.childNumCount(self.nodes[nodeInd][0])
            elseCount = self.n-1 - leftChildNumCount
            if elseCount == 0:
                score = leftChildNumCount
            else:
                score = elseCount * leftChildNumCount
            self.countScore(score)
            return 1 + leftChildNumCount
        else:
            leftChildNumCount = self.childNumCount(self.nodes[nodeInd][0])
            rightChildNumCount = self.childNumCount(self.nodes[nodeInd][1])
            elseCount = self.n-1 - leftChildNumCount - rightChildNumCount
            if elseCount == 0:
                score = leftChildNumCount * rightChildNumCount
            else:
                score = elseCount * leftChildNumCount * rightChildNumCount
            self.countScore(score)
            return 1 + leftChildNumCount + rightChildNumCount
        
    def countScore(self, score) :
        if score > self.maxScore:
            self.maxScore = score
            self.maxScoreCount = 1
        elif score == self.maxScore:
            self.maxScoreCount += 1
Copy the code

2050. Concurrent Course III

Topological sort + base DP

parsing

The description of this problem is similar to LeetCode common 207. Timetable, 210. Schedule II these two problems are very similar, it is easy to think of using the idea of topological ordering to order the course. The only difference is the minimum time required to complete all courses.

Based on greedy thinking, if “every course is completed as early as possible”, all courses in such a directed acyclic graph in the question will be completed at the earliest possible time, which is equivalent to figuring out the minimum completion time of all courses. Described above is equivalent to the one who has a topological sort of directed acyclic graph, all need only in its most late pre course starts immediately after the completion of the study, with a dp array to store the most night time, then after the completion of the topological sort through this array, then the latest finish time of all courses.

code

class Solution:
    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) - >int:
        latestTime = [time[i] for i in range(0, n)]
        if len(relations) == 0:
            return max(time)
        adj = [[] for _ in range(n)]
        relationCount = len(relations)
        indegree = [0] * n
        for relation in relations:
            adj[relation[0] -1].append(relation[1] -1)
            indegree[relation[1] -1] + =1
        queue = []
        for i in range(n):
            if indegree[i] == 0:
                queue.append(i)
        while len(queue):
            front = queue.pop(0)
            for tail in adj[front]:
                latestTime[tail] = max(latestTime[tail], latestTime[front] + time[tail])
                indegree[tail] -= 1
                relationCount -= 1
                if indegree[tail] == 0:
                    queue.append(tail)
        return max(latestTime)
Copy the code