力扣：第 304 场周赛

力扣：第 304 场周赛
力扣：第 304 场周赛

究极手速场

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

 问题解析

题意：一个数组，你每次可以将数组的值减少一个整数，这个整数小于等于数组的最小正整数，问多少次操作可以将数组全部变为0

其实这题就是在问数组中有多少个不同的正整数罢了，因为每次操作，我们可以把数组中最小的正整数全部变成0。那么数组中有多少个不同的正整数，我们就减几次就可以了。

AC代码
```
class Solution {
public:
    int minimumOperations(vector& nums) {
        sort(nums.begin(),nums.end());
        nums.erase(unique(nums.begin(), nums.end()), nums.end());
        return nums[0]==0?nums.size()-1:nums.size();
    }
};
1
2
3
4
5
6
7
8
```
6133. 分组的最大数量

 问题解析

题意：一个数组，你要将数组分成几份，第i份的数字个数和数字总和要严格小于第i+1份，问你最多可以分成几份。

实际上，如果我们把数组升序排序就可以知道，只要第i+1份的数字个数大于第i份，那么i+1份的数组总和是一定大于第i份的，我们只要把小的数先分类好，再分大的即可。

那么问题就在数字个数上了，要尽可能多的分，那么贪心来说就要分成：一个数，两个数，三个树……，n个数这样，所以就看数组的长度按照这么分能满足分成多少组就行。

AC代码
```
class Solution {
public:
    int maximumGroups(vector& grades) {
        int n=grades.size(),x=1,y=2;
        while(x
```
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
6134. 找到离给定两个节点最近的节点

 问题解析

题意：一个带环单向图，给你两个点，问这两个点都能到达的一个点且距离最近的点是哪个。

建图后进行两遍dfs，第一遍先按照node0为出发点进行dfs，记录下node0能到达的所有点，并记录下node0到达这些点的距离。

再以node1为起点dfs，也记录走过的路，如果遍历到的点在第一次dfs中被记录到了，说明这个点node0和node1都可以到达，然后根据这个点到达node0和node1的距离来更新答案即可。

但是这图是带环的，单纯dfs会t的，我们可以把走过的点打上标记，当走到重复的点时我们直接停下不走这个点。

AC代码
```
class Solution {
public:
    vectorv[100050];
    unordered_mapmymap;
    int st[100050],st2[100050],mx=1e9,pos=-1;
    void dfs(int x,int res)
    {
        if(x==-1)return ;
        if(st[x]==1)return;
        st[x]=1;
        mymap[x]=res;
        for(auto i:v[x])
        {
            dfs(i,res+1);
        }
    }
    void dfs2(int x,int res)
    {
        if(x==-1)return;
        if(st2[x]==1)return;
        st2[x]=1;
        if(mymap.count(x))
        {
            int t=max(mymap[x],res);
            if(t& edges, int node1, int node2) {
        int n=edges.size();
        for(int i=0;i
```
- 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
- 46
- 47
- 48
- 49
- 50
- 51
- 52
6135. 图中的最长环

 问题解析

题意：一个单向图，让你找出最大的一个环，求这个环的长度。

我们用一个标记数组标记走过的所有点，建图后以每个点为起点进行一遍dfs，如果这个点已经被打上标记了，我们就不以它为起点dfs。

每次dfs记录起点y到当前点x的距离，并且记录从起点出发一共走了多少距离，如果我们走到y点发现这个点已经被打上标记了，那么就有两种可能
1. 这个点是其它点之前dfs时被打上标记的，那么起点到当前点的距离就等于起点走过的距离，没有环。
2. 这个点我们在这一次dfs走过了两次，那么起点到当前点的距离就小于起点走过的距离，有环，而这段距离的差值就是环的大小。
我们只要维护环的最大值即可。

AC代码
```
class Solution {
public:
    vectorv[100050];
    int len=-1;
    int st[100050];
    unordered_map>mymap;
    void dfs(int x,int y,int res)
    {
        if(x==-1)return;
        if(mymap[y].count(x))
        {
            mymap[y][x]=min(mymap[y][x],res);
        }
        else mymap[y][x]=res;
        if(st[x]==1)
        {
            if(res==mymap[y][x])return;
            else 
            {
                len=max(len,res-mymap[y][x]);
                return;
            }
        }
        st[x]=1;
        for(auto i:v[x])
        {
            dfs(i,y,res+1);
        }
    }
    int longestCycle(vector& edges) {
        int n=edges.size();
        for(int i=0;i
```

力扣：第 304 场周赛

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

问题解析

AC代码

6133. 分组的最大数量

问题解析

AC代码

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

问题解析

AC代码

6135. 图中的最长环

问题解析

AC代码