leetcode conttest 304

周赛的状态越来越不好，感觉第四题的状态越来越差，不过也感觉力扣好的题目越来越少了。套路题目太多了，感觉就刷一下周赛即可。

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

题目

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

选出一个正整数 x ，x 需要小于或等于 nums 中最小的非零元素。
nums 中的每个正整数都减去 x。
返回使 nums 中所有元素都等于 0 需要的最少操作数。

示例 1：

输入：nums = [1,5,0,3,5]
输出：3
解释：
第一步操作：选出 x = 1 ，之后 nums = [0,4,0,2,4] 。
第二步操作：选出 x = 2 ，之后 nums = [0,2,0,0,2] 。
第三步操作：选出 x = 2 ，之后 nums = [0,0,0,0,0] 。

示例 2：

输入：nums = [0]
输出：0
解释：nums 中的每个元素都已经是 0 ，所以不需要执行任何操作。

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 100

地址

https://leetcode.cn/problems/make-array-zero-by-subtracting-equal-amounts/

题意

直接模拟

思路

首先我们可以直接模拟，将数组按照从小到大进行排序，然后按照从小到大的顺序依次取出元素 $x$，将所有的元素都减去 $x$，直到所有元素变为 $0$ 为止。
由于数组中所有的元素都不相同，因此每次模拟时，我们只能将其中一个元素变为 $0$，因此总共需要的次数即为数组中大于 $0$ 的不同元素的个数。
复杂度分析：

时间复杂度：$O(n)$，其中 $n$ 为数组元素的个数。
空间复杂度：$O(n)$，其中 $n$ 为数组元素的个数。

代码

直接模拟：

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        set<int> cnt;
        sort(nums.begin(), nums.end());
        int ans = 0;
        int pos = 0;
        while(nums.back() > 0) {
            while(pos < nums.size() && nums[pos] == 0) {
                pos++;
            }
            int x = nums[pos];
            for(int i = pos; i < nums.size(); i++) {
                nums[i] -= x;
            }
            ans++;
        }
        return ans;
    }
};

数学：

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        int ans = 0;
        unordered_set<int> cnt;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != 0) {
                cnt.emplace(nums[i]);
            }
        }
        return cnt.size();
    }
};

2358. 分组的最大数量

题目

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

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

示例 1：

输入：grades = [10,6,12,7,3,5]
输出：3
解释：下面是形成 3 个分组的一种可行方法：
- 第 1 个分组的学生成绩为 grades = [12] ，总成绩：12 ，学生数：1
- 第 2 个分组的学生成绩为 grades = [6,7] ，总成绩：6 + 7 = 13 ，学生数：2
- 第 3 个分组的学生成绩为 grades = [10,3,5] ，总成绩：10 + 3 + 5 = 18 ，学生数：3 
可以证明无法形成超过 3 个分组。

示例 2：

输入：grades = [8,8]
输出：1
解释：只能形成 1 个分组，因为如果要形成 2 个分组的话，会导致每个分组中的学生数目相等。

提示：

1 <= grades.length <= 105
1 <= grades[i] <= 105

地址

https://leetcode.cn/problems/maximum-number-of-groups-entering-a-competition

题意

贪心算法

思路

典型的贪心算法，若要是分组数目尽可能的大，则应该满足第一个分组尽可能的小，按照贪心规则可以知道第一个分组最小只能为数组中最小的元素。此时我们将第一个最小的元素去掉，再按照题目中要求的情况去模拟，找到第二个分组满足情况，当然经过仔细分析可以知道如下最大分组应该分布如下：
$$
(1,2,3,4,…,k)
$$
第一个分组中应有 $1$ 个元素，第二个分组中应有 $2$ 个元素，第三个分组中应有 $3$ 个元素。当然此时我们可以利用解一元二次方程即可。
复杂度分析：

时间复杂度：时间复杂度为 $O(1)$。
空间复杂度：$O(1)$。

代码

class Solution {
public:
    int maximumGroups(vector<int>& grades) {
        int ans = 0;
        int n = grades.size();
        for (int i = 1; i <= n; i++) {
            n -= i;
            ans++;
        }
        return ans;
    }
};

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

题目

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

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

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

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

注意 edges 可能包含环。

示例 1：

输入：edges = [2,2,3,-1], node1 = 0, node2 = 1
输出：2
解释：从节点 0 到节点 2 的距离为 1 ，从节点 1 到节点 2 的距离为 1 。
两个距离的较大值为 1 。我们无法得到一个比 1 更小的较大值，所以我们返回节点 2 。

示例 2：

输入：edges = [1,2,-1], node1 = 0, node2 = 2
输出：2
解释：节点 0 到节点 2 的距离为 2 ，节点 2 到它自己的距离为 0 。
两个距离的较大值为 2 。我们无法得到一个比 2 更小的较大值，所以我们返回节点 2 。

提示：

n == edges.length
2 <= n <= 105
-1 <= edges[i] < n
edges[i] != i
0 <= node1, node2 < n

地址

https://leetcode.cn/problems/find-closest-node-to-given-two-nodes

题意

BFS

思路

感觉是非常简单的 BFS 即可，通过 BFS 分别求出所有节点到 node1 与 node2 的距离。然后依次遍历节点，找到二者之间共同可以访问的节点，并求出共同可以访问节点的距离之和的最小值即可，感觉没有多少难度，很直观的思路和解题方法。
复杂度分析：

时间复杂度：时间复杂度为 $O(n)$。
空间复杂度：空间复杂度为 $O(n)$。

代码

class Solution {
public:
    void bfs(unordered_map<int, vector<int>>& adj, int node, unordered_map<int, int> &dist) {
        queue<int> qu;
        qu.emplace(node);
        int step = 0;
        while (!qu.empty()) {
            int sz = qu.size();
            for (int i = 0; i < sz; i++) {
                int curr = qu.front();
                qu.pop();
                dist[curr] = step;
                for (auto v : adj[curr]) {
                    if(dist.count(v)) continue;
                    qu.emplace(v);
                }
            }
            step++;
        }
    }
    
    int closestMeetingNode(vector<int>& edges, int node1, int node2) {
        int n = edges.size();
        unordered_map<int, vector<int>> adj;
        for (int i = 0; i < n; i++) {
            if(edges[i] >= 0) {
                adj[i].emplace_back(edges[i]);
            }
        }
        unordered_map<int, int> dist1;
        unordered_map<int, int> dist2;
        bfs(adj, node1, dist1);
        bfs(adj, node2, dist2);
        int ans = -1;
        int mindist = INT_MAX;
        for (auto &[node, dist] : dist1) {
            if (dist2.count(node)) {
                int curr = max(dist, dist2[node]);
                if (curr < mindist) {
                    ans = node;
                    mindist = curr;
                } else if (curr == mindist && node < ans) {
                    ans = node;
                    mindist = curr;
                }
            }
        }
        return ans;
    }
};

2360. 图中的最长环

题目

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

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

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

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

示例 1：

输入：edges = [3,3,4,2,3]
输出去：3
解释：图中的最长环是：2 -> 4 -> 3 -> 2 。
这个环的长度为 3 ，所以返回 3 。

示例 2：

输入：edges = [2,-1,3,1]
输出：-1
解释：图中没有任何环。

提示：

n == edges.length
2 <= n <= 105
-1 <= edges[i] < n
edges[i] != i

地址

https://leetcode.cn/problems/longest-cycle-in-a-graph

题意

DFS

思路

经典题目，解法有很多种，经典的解法如下。

拓扑排序：首先我们可以利用拓扑排序将环以外的部分去掉，剩余未访问的节点均在环上，此时我们从环上任意一点开始访问求出环的最大深度即可，当然本题每条边的出度为 $1$，计算时更为简单，只需要循环即可。
DFS 标记: 参考题解：内向基环树找环 + 利用时间戳简单实现，感觉容易写错，当然可以老老实实的用拓扑排序方法，去掉非环上的所有节点。

复杂度分析：

时间复杂度：$O(n \log n)$，$n$ 表示数组的长度。
空间复杂度：$O(n)$，$n$ 表示数组的长度。

代码

class Solution {
public:
    int longestCycle(vector<int>& edges) {
        int n = edges.size();
        vector<int> degree(n);
        for (auto v : edges) {
            if (v >= 0) {
                degree[v]++;
            }
        }
        queue<int> qu;
        vector<bool> visit(n, false);
        for (int i = 0; i < n; i++) {
            if (degree[i] == 0) {
                qu.emplace(i);
                visit[i] = true;
            }
        }
        while (!qu.empty()) {
            int curr = qu.front();
            qu.pop();
            int nx = edges[curr];
            if (nx >= 0) {
                degree[nx]--;
                if (degree[nx] == 0) {
                    qu.emplace(nx);
                    visit[nx] = true;
                }
            }
        }
        int ans = -1;
        for (int i = 0; i < n; i++) {
            if (!visit[i]) {
                int x = i;
                int dist = 0;
                while(!visit[x]) {
                    visit[x] = true;
                    dist++;
                    x = edges[x];
                }
                ans = max(ans, dist);
            }
        }
        return ans;
    }
};

欢迎关注和打赏，感谢支持！

关注我的博客: http://mikemeng.org/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 力扣周赛

← leetcode biweekly conttest 84 leetcode conttest 303 →

扫描二维码，分享此文章