LeetCode：第304场周赛【总结】

这场比赛也是手速题，前面两道题是思维题，后面两道题考得是图论

6132. 使数组中所有元素都等于零【思维题】

思路

题意转化为求除0以外，有多少种不同整数。

AC代码

class Solution {
    
public:
    int vis[105];
    int minimumOperations(vector<int>& nums) {
    
        int ans = 0;
        for(auto num : nums) {
    
            if (num == 0 || vis[num] == 1) continue;
            vis[num] = 1;
            ++ans;
        }
        return ans;
    }
};

6133. 分组的最大数量【思维题】

思路

将数组排序后，可分为第1个数分为第一组，第 2， 3个数分为第二组，…，最后剩余的数给最后一个分组。

AC代码

class Solution {
    
public:
    int solve(int n) {
    
        int ans = 0;
        int num = 0;
        for (int i = 1; i <= 100000; ++i) {
    
            num += i;
            if (num > n) {
    
                break;
            }
            ans++;
        }
        return ans;
    }
    int maximumGroups(vector<int>& grades) {
    
        int len = grades.size();
        return solve(len);
    }
};

6134. 找到离给定两个节点最近的节点【两次BFS】

思路

用两个bfs搞定，第一个bfs统计node1走过的点，并且记录该点到node1的距离，第二个bfs统计node2走过的点，同时判断node1走过没有，如果走过，则记录该点到node1和node2的最近距离，且要节点序号最小。
注：需要标记node1和node2走过的点，避免死循环。

AC代码

class Solution {
    
public:
    static const int n = 1e5 + 5;
    typedef pair<int, int> pii;
    int vis[n], d[n], vis2[n]; // vis记录node1走过的点，vis2记录node2走过的点，d记录node1走过点的距离
    void bfs_1(vector<int>& edges, int node1, int node2) {
    
        queue<pii> q;
        q.push(pii{
    node1, 0}); // 队列装两个数，第一个是走过的点，第二个是走过该点的距离
        while(!q.empty()) {
    
            pii tmp = q.front(); q.pop();
            int cur = tmp.first;
            vis[cur] = 1;
            int dis = tmp.second;
            d[cur] = dis;
            if (edges[cur] == -1 || vis[edges[cur]] == 1) continue;
            q.push(pii{
    edges[cur], dis + 1});
        }
    }
    int bfs_2(vector<int> & edges, int node1, int node2) {
    
        queue<pii> q;
        q.push(pii{
    node2, 0});
        int ans = -1, mi = 1e9;
        while(!q.empty()) {
    
            pii tmp = q.front(); q.pop();
            int cur = tmp.first;
            int dis = tmp.second;
            vis2[cur] = 1;
            if (vis[cur] == 1) {
     // 满足两条路径都走过的点
                int t = max(d[cur], dis); 
                if (t < mi) {
     // 找到离两个节点更近的点
                    mi = t;
                    ans = cur;
                } else if(t == mi) {
     // 如果存在离两个节点同样距离的节点，则选序号小的
                    mi = t;
                    ans = min(cur, ans);
                }
            }
            if (edges[cur] == -1 || vis2[edges[cur]] == 1) continue;
            q.push(pii{
    edges[cur], dis + 1});
        }
        return ans;
    }
    int closestMeetingNode(vector<int>& edges, int node1, int node2) {
    
        bfs_1(edges, node1, node2);
        return bfs_2(edges, node1, node2);
    }
};

6135. 图中的最长环【拓扑排序+BFS】

思路

用拓扑排序标记不再环中的点，在进行bfs时不用进行这些点的搜索，用bfs求环的长度。

AC代码

class Solution {
    
public:
    static const int n = 1e5 + 7;
    int indegree[n]; // 统计每个节点的入度
    int vis[n]; // 是否在环中
    int longestCycle(vector<int>& edges) {
    
        for (auto edge: edges) {
    
            if (edge == -1) continue;
            ++indegree[edge];
        }
        // 将不在环中的节点逻辑删除
        int len = edges.size();
        queue<int> q;
        for (int i = 0; i < len; ++i) {
    
            if (indegree[i] == 0) {
    
                q.push(i);
            }
        }
        while(!q.empty()) {
    
            int cur = q.front(); q.pop();
            vis[cur] = 1;
            if (edges[cur] == -1) continue;
            if(--indegree[edges[cur]] == 0) q.push(edges[cur]);
        }
        int ans = -1;
        // 利用bfs计算环的长度
        for (int i = 0; i < len; ++i) {
    
            if(vis[i] == 1) continue;
            --indegree[i];
            int num = 0;
            vis[i] = 1;
            q.push(i);
            while(!q.empty()) {
    
                int cur = q.front(); q.pop();
                num++;
                vis[cur] = 1;
                if (--indegree[edges[cur]] == 0) q.push(edges[cur]);
            }
            ans = max(ans, num);
        }
        return ans;
    }
};