LeetCode304周赛

https://leetcode.cn/contest/weekly-contest-304/
记录两道没写出来的题
参考的讲解：Y总
这是一个基环树问题，就是一个环上挂了一堆树。

LeetCode 6134. 找到离给定两个节点最近的节点

https://leetcode.cn/problems/find-closest-node-to-given-two-nodes/
解决思路：分别从 node1 和 node2 开始，记录每个节点到 node1 和 node2 的距离，若有环或者到尽头结束。然后遍历节点，若求最小的 max(d1[i], d2[i]) 的节点 i。

class Solution {
public:
    int closestMeetingNode(vector<int>& p, int x, int y) {
        int n = p.size(); // 记录点数
        vector<int> d1(n, -1); // 记录每个点到 x 的距离
        vector<int> d2(n, -1); // 记录每个点到 y 的距离
        d1[x] = d2[y] = 0;
        while (p[x] != -1) {
            if (d1[p[x]] != -1) { // 已经遍历过，跳出循环
                break;
            }
            d1[p[x]] = d1[x] + 1; // 节点距离 + 1
            x = p[x];
        }

        while (p[y] != -1) {
            if (d2[p[y]] != -1) { // 已经遍历过，跳出循环
                break;
            }
            d2[p[y]] = d2[y] + 1; // 节点距离 + 1
            y = p[y];
        }

        int ans = -1, id = -1;

        for (int i = 0; i < n; i++) {
            int a = d1[i], b = d2[i];
            if (a != -1 && b != -1) {
                if (ans == -1 || max(a, b) < ans) { // 若某节点距离 x 和 y 更近，记录为 ans
                    ans = max(a, b);
                    id = i;
                }
            }
        }

        return id;
    }
};
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

LeetCode 6135. 图中的最长环

https://leetcode.cn/problems/longest-cycle-in-a-graph/
解决思路：循环节点数 n 次，每次从第 i 个节点开始，若有环或者到尽头结束，记录能走的长度。最终结果就是取 n 个节点开始能走的最长路线长度。

class Solution {
    
public:
    vector<int> p;
    vector<bool> st; // 存储每个点是否被搜索过
    vector<int> in_stk; // 是否在栈当中，深度为多少
    int ans = -1;
    
    void dfs(int x, int depth){
        st[x] = true; // 表示被遍历过
        in_stk[x] = depth; // 加入栈，标记为栈的深度

        int next = p[x];    // 搜索 x 的下一个节点
        if (next != -1) {
            if (!st[next]) { // 未被搜过
                dfs(j, depth + 1);
            } else if (in_stk[next]) { //被搜索过，在栈中，有环
                ans = max(ans, depth + 1 - in_stk[next]);    // 深度更新
            }
        }

        in_stk[x] = 0; // 出栈，标记清空
    }

    int longestCycle(vector<int>& p) {
        this->p = p;
        int n = p.size(); // 节点个数

        st = vector<bool>(n);
        in_stk = vector<int>(n);
        
        for (int i = 0; i < n; i++) { // 遍历所有点
            if (!st[i]) { // 如果当前点没被搜索过
                dfs(i, 1);
            }
        }

        return ans;
    }
};
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