LeetCode周赛304，图论双压，你能搞定吗？

大家好，我是梁唐。

这几天由于换了城市，实在是没有挤出时间，因此更新晚了一些，大家见谅。

这一场周赛由cider赞助举办，前300名可以获得校招和社招简历内推的机会。

这次的题目总体来说难度不大，尤其是前两题。有同学在赛后调侃说这次的题目适合熬夜之后的脑子，不得不说是很形象了。

好了，回到正题，我们来看题吧。

使数组中所有元素都等于零

给你一个非负整数数组 nums 。在一步操作中，你必须：

• 选出一个正整数 x ，x 需要小于或等于 nums 中 最小 的 非零 元素。
• nums 中的每个正整数都减去 x。

返回使 nums 中所有元素都等于 0 需要的 最少 操作数。

题解

简单分析之后会发现，要使得所有数等于0，要进行的操作数量等于数组当中不同的元素值的数量。

我们可以使用C++中的unique函数来对元素进行去重，去重之后的元素的数量就是答案，注意要去掉0的情况。

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = unique(nums.begin(), nums.end()) - nums.begin();
        if (nums[0] == 0) n--;
        return n;
    }
};

分组的最大数量

给你一个正整数数组 grades ，表示大学中一些学生的成绩。你打算将 所有 学生分为一些 有序 的非空分组，其中分组间的顺序满足以下全部条件：

• 第 i 个分组中的学生总成绩 小于 第 (i + 1) 个分组中的学生总成绩，对所有组均成立（除了最后一组）。
• 第 i 个分组中的学生总数 小于 第 (i + 1) 个分组中的学生总数，对所有组均成立（除了最后一组）。

返回可以形成的 最大 组数。

题解

这题看起来很花哨条件很多，但仔细分析之后可以发现本题的关键在排序。只需要将数组中的元素进行排序，之后再按照题目的分组要求进行划分。就可以保证元素数量更少的分组对应的总和也一定最小。

所以我们的分组情况就和元素值的大小解绑了，只和元素的数量有关。我们只需要计算一下对应的数量下最多能够拆分的分组数即可。

class Solution {
public:
    int maximumGroups(vector<int>& grades) {
        int n = grades.size();
        int ret = 0;
        int sum = 0, cur = 1;
        while (sum + cur <= n) {
            ret++;
            sum += cur++;
        }
        return ret;
    }
};

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

给你一个 n 个节点的 有向图 ，节点编号为 0 到 n - 1 ，每个节点 至多 有一条出边。

有向图用大小为 n 下标从 0 开始的数组 edges 表示，表示节点 i 有一条有向边指向 edges[i] 。如果节点 i 没有出边，那么 edges[i] == -1 。

同时给你两个节点 node1 和 node2 。

请你返回一个从 node1 和 node2 都能到达节点的编号，使节点 node1 和节点 node2 到这个节点的距离 较大值最小化。如果有多个答案，请返回 最小 的节点编号。如果答案不存在，返回 -1 。

注意 edges 可能包含环。

题解

图论裸题，我们只需要算出从node1和node2节点出发到达其他点的最短距离，然后找出既能连通又满足题意的答案即可。

计算从单点出发到达其他点的方法有很多，常用的有dijkstra、spfa等。这题当中我们可以使用spfa，它的思路比较简单，和bfs搜索非常相似。

class Solution {
public:
    int closestMeetingNode(vector<int>& edges, int node1, int node2) {
        int n = edges.size();
        
        auto spfa = [&](int u, vector<int> &dis) {
            dis[u] = 0;
            queue<int> que;
            que.push(u);
            vector<bool> inqueue(n, 0);
            inqueue[u] = true;
            
            while (!que.empty()) {
                int f = que.front();
                que.pop();
                inqueue[f] = false;
                int v = edges[f];
                if (v != -1 && dis[f] + 1 < dis[v]) {
                    dis[v] = dis[f] + 1;
                    if (!inqueue[v]) {
                        inqueue[v] = true;
                        que.push(v);
                    }
                }
            }
        };
        
        vector<int> dis1(n+1, 0x3f3f3f3f), dis2(n+1, 0x3f3f3f3f);
        spfa(node1, dis1);
        spfa(node2, dis2);
        
        int ret = -1, maxi = 0x3f3f3f3f;
        for (int i = 0; i < n; i++) {

            if (max(dis1[i], dis2[i]) < maxi) {
                maxi = max(dis1[i], dis2[i]);
                ret = i;
            }
        }
        return ret;
    }
};

图中的最长环

给你一个 n 个节点的 有向图 ，节点编号为 0 到 n - 1 ，其中每个节点 至多 有一条出边。

图用一个大小为 n 下标从 0 开始的数组 edges 表示，节点 i 到节点 edges[i] 之间有一条有向边。如果节点 i 没有出边，那么 edges[i] == -1 。

请你返回图中的 最长 环，如果没有任何环，请返回 -1 。

一个环指的是起点和终点是 同一个 节点的路径。

题解

这题看起来同样非常麻烦，尤其是涉及到环的存在，很多人不熟悉，实际上有一个比较简单的办法可以解决这个问题。

这个方法就是染色，我们从一个点出发，将所有能够遍历到的点染成相同的颜色。如果在遍历的过程当中，遇到了已经染色的点，那么说明肯定存在环，通过每个点记录的和起点的距离可以算出环的长度。

由于每个点只有一个出度，也就是说每一个点引出的边只有一条。所以如果从当前点出发指向的点已经染了其他颜色，那么说明当前点一定不在环上，否则当前点也会染上同样的颜色。所以可以直接退出循环。

解法本身不难，有一些细节在代码当中，可以参考注释理解。

class Solution {
public:
    int longestCycle(vector<int>& edges) {
        int n = edges.size();
        // 染色数组
        vector<int> col(n+1, -1);
      	// 距离
        int dis[n+1];
        memset(dis, 0x3f, sizeof dis);
        
        auto bfs = [&](int u) -> int {
          	// 如果已经染色，说明之前被遍历过，可以直接退出
            if (col[u] != -1) return -1;
            col[u] = u;
            dis[u] = 0;
            
            queue<int> que;
            que.push(u);
            
            while (!que.empty()) {
                int f = que.front();
                que.pop();
                int v = edges[f];
                if (v == -1) continue;
                
              	// 如果v点已经染色了u，说明存在环
              	// 由于每个点最多只有一个出度，所以每个点最多在一个环上，可以直接返回
                if (col[v] == u) {
                    return dis[f] + 1 - dis[v];
                }
                if (col[v] == -1) {
                    col[v] = u;
                    dis[v] = dis[f] + 1;
                    que.push(v);
                // 如果v点染了其他颜色，而u点没有，说明u和v不在一个环上，直接退出
                }else break;
            }
            return -1;
        };
        
        int ret = -1;
        for (int i = 0; i < n; i++) {
            ret = max(ret, bfs(i));
        }
        return ret;
    }
};

这次的题目总体来说难度不大，主要是最后两题都和图论相关，很多同学可能不太熟悉。实际上图论的很多问题只是看起来比较复杂，涉及的算法常用的也只有几种，原理也并不复杂，希望大家不要畏难。