【无标题】

一、本周周赛总结

• 勉强ak。图论弱鸡。
• 看到图很紧张，在T3疯狂失误。wa的6声哭了出来。
• 貌似有题re了，这是re后排名。
  

二、 [Easy] 2357. 使数组中所有元素都等于零

链接: 2357. 使数组中所有元素都等于零

1. 题目描述

2. 思路分析

• 每次都会消除一种非0数字，去重统计即可。

3. 代码实现

class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        return len([x for x in set(nums) if x > 0])
1
2
3

三、[Medium] 2358. 分组的最大数量

链接: 2358. 分组的最大数量

1. 题目描述

2. 思路分析

• 贪心模拟。
• 我们发现如果对学生成绩排序，只需满足条件2，条件1自动满足。
• 因此让第一组1个，第二组2个。。依次类推，等差数列求和公式即可O(1)算出来。
• 我比赛时模拟，模拟到一半发现学生成绩没用，后边模拟了组员数。

3. 代码实现

class Solution:
    def maximumGroups(self, gs: List[int]) -> int:
        gs.sort()
        n = len(gs)
        presum = accumulate(gs,initial=0)
        size = 2
        step = 1
        ans = 1
        print(step,size,n)
        while step+size <= n:
            step += size 
            size += 1
            ans+=1
            # print(step,size,n,ans)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

四、[Medium] 2359. 找到离给定两个节点最近的节点

链接: 2359. 找到离给定两个节点最近的节点

1. 题目描述

2. 思路分析

定级Medium。

• 从两个点分别出发，找到所有能到达的节点。
• 然后取交集，最小的那个即可。

3. 代码实现

class Solution:
    def closestMeetingNode(self, es: List[int], node1: int, node2: int) -> int:
        g= defaultdict(list)
        n = len(es)
        for i,e in enumerate(es):
            if e != -1:
                g[i].append(e)
        
        path1 = {}
        visited1 = defaultdict(int)
        visited1[node1] = 1
        # path1[node1] = 0
        q = deque([node1])
        while q:
            u = q.popleft()
            depth = visited1[u]+1
            for v in g[u]:
                if not visited1[v]:
                    visited1[v] = depth
                    q.append(v)
        
        visited2 = defaultdict(int)
        q = deque([node2])
        visited2[node2] = 1
        while q :
            u = q.popleft()
            depth = visited2[u] + 1
            for v in g[u]:
                if not visited2[v]:
                    visited2[v] = depth
                    q.append(v)

        # print(visited1,visited2)
        ans,d = inf,inf
        for k,v in visited1.items():
            if k in visited2:
                m = max(v,visited2[k])
                if m < d:
                    d = m
                    ans = k
                if m == d:
                    ans = min(ans,k)
            
            # print(k,v,visited2[k],ans,d)
        return ans if ans != inf else -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

五、[Hard] 2360. 图中的最长环

链接: 2360. 图中的最长环

1. 题目描述

2. 思路分析

定级Hard。

• 实际是模板题，但我不会。
• 图是个基环内向树。（有一个环、所有不在环上的点都指向环）
• 三色标记，未访问的节点标0，进入递归标1，出递归标-1.
• 用栈记录路径，进递归加栈，出递归弹栈。找到环就向前计数，找到同节点即可。

3. 代码实现

class Solution:
    def longestCycle(self, edges: List[int]) -> int:
        n = len(edges)
        g = defaultdict(list)
        for i,e in enumerate(edges):
            if e != -1:
                g[i].append(e)
                
            
        visited = [0] * n
        ma = -1
        path = []
        
        def dfs(u):
            visited[u] = 1
            path.append(u)
            for v in g[u]:
                if visited[v] == 0:
                    dfs(v)
                if visited[v] == 1:
                    # print('环')
                    cnt = 0 
                    for j in path[::-1]:
                        cnt += 1
                        if j == v:
                            break
                    nonlocal ma
                    if cnt > ma:
                        ma = cnt
            visited[u] = -1
            path.pop()
            
        for i in range(n):
            if  visited[i] > -1:
                dfs(i)
                
        return ma
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37