目录

• 1.使数组中所有元素都等于零
• • 1）题目描述
  • 2）原题链接
  • 3）思路解析
  • 4）模板代码
  • 5）算法与时间复杂度
• 2、分组的最大数量
• • 1）题目描述
  • 2）原题链接
  • 3）思路解析
  • 4）模板代码
  • 5）算法与时间复杂度
• 3.找到离给定两个节点最近的节点
• • 1）题目描述
  • 2）原题链接
  • 3）思路解析
  • 4）模板代码
  • 5）算法与时间复杂度
• 4.图中最长环
• • 1）题目描述
  • 2）原题链接
  • 3）思路解析
  • 4）模板代码
  • 5）算法与时间复杂度
• 5、周赛总结

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

1）题目描述

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

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

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

2）原题链接

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

3）思路解析

• $(1)$很明显，贪心的思考我们应该每次选取数组中最小的非0元素作为x，然后将所有元素慢慢变为0。问题将变化为数组中存在多少个非0的不同元素。

4）模板代码

 public int minimumOperations(int[] nums) { Set<Integer> set=new HashSet<>(); int n=nums.length; for (int num : nums) {     if (num != 0) set.add(num); } return set.size();    }

5）算法与时间复杂度

  算法：贪心
  时间复杂度：遍历一次数组，复杂度为$O(n)$。

2、分组的最大数量

1）题目描述

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

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

2）原题链接

LeetCode.6133. 分组的最大数量

3）思路解析

• $(1)$后面的组不仅要保证人比前面的多，还要保证总成绩高于前面前面的组。那么很明显，我们可以让成绩差的人去人少的组，成绩好的人去人多的组，这样就一定能保证符合条件。然后我们以组人数分别为1,2,3…这样分下去，看最多能分多少组。这里相当于是一个等差数列，我们可以二分 出答案。

4）模板代码

 public int maximumGroups(int[] arr) { int n=arr.length; int l=0,r=100000; while (l<r){     int mid=l+r+1>>1;     long v= (long) mid *(mid+1)/2;     if(v>n) r=mid-1;     else l=mid; } return r;    }

5）算法与时间复杂度

  算法：贪心 脑筋急转弯 二分
  时间复杂度：二分复杂度为$O(logn)$。

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

1）题目描述

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

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

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

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

注意 edges 可能包含环。

2）原题链接

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

3）思路解析

• $(1)$首先很明显，答案节点必须是node1和node2都能到达的节点，我们可以对两个结点分别做一次bfs，把遇到的节点分别放到set中。
• $(2)$使用dist数组统计到达每个点的距离，由于答案求的是较大值最小化，所以首先两个结点都能到达的结点的距离我们需要取max。
• $(3)$最后对dist进行遍历，找到两个set都存储过的点，然后这些找到dist最小的结点。

4）模板代码

Map<Integer,Integer> map=new HashMap<>();    int N=100010;    int[] dist=new int[N];    int ans=Integer.MAX_VALUE;    Set<Integer> s1=new HashSet<>();    Set<Integer> s2=new HashSet<>();    int jie=-1;    public int closestMeetingNode(int[] edges, int node1, int node2) { int n=edges.length; for (int i = 0; i <n; i++) {     add(i,edges[i]); } bfs(node1,true); bfs(node2,false); for (int i = 0; i < n; i++) {     if (s1.contains(i)&&s2.contains(i)){  if (dist[i]<ans){      ans=dist[i];      jie=i;  }     } } return jie;    }    void bfs(int start,boolean f){ Queue<Integer> q=new LinkedList<>(); boolean[] st=new boolean[N]; st[start]=true; q.offer(start); int x=0; while (!q.isEmpty()){     int size=q.size();     while (size-->0){  int curr=q.poll();  if (f) s1.add(curr);  else s2.add(curr);  int next=map.get(curr);  dist[curr]=Math.max(x,dist[curr]);  if (next==-1||st[next]) continue;  q.offer(next);  st[next]=true;     }     x++; }    }    void add(int a,int b){ map.put(a,b);    }

5）算法与时间复杂度

  算法：BFS
  时间复杂度：最坏不超过$O(n)$

4.图中最长环

1）题目描述

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

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

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

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

2）原题链接

LeetCode.6135. 图中的最长环

3）思路解析

• $(1)$找到图中最长环，我们可以对每个点进行一次搜索，在搜索的过程中，记录下到达了哪些点和到该点的距离，使用哈希存下来，当遇到走过的点说明遇到了环，算出此时的环长。
• $(2)$由于每个点的出度都为1，所以对于之前已经访问过的点，我们不需要再以它为起点进行搜索了，否则会超时。在所有搜索到的环中取最大值。

4）模板代码

class Solution {    boolean[] st=new boolean[100010];    Map<Integer,Integer> map=new HashMap<>();    int res=0;    public int longestCycle(int[] edges) { int n=edges.length; for (int i = 0; i <n ; i++) {     add(i,edges[i]); } for (int i = 0; i < n; i++) {     if (!st[i]) bfs(i); } return res==0?-1:res;    }    void bfs(int start){ Queue<Integer> q=new LinkedList<>(); st[start]=true; q.offer(start); Map<Integer,Integer> ad=new HashMap<>(); ad.put(start,0); int x=0; while (!q.isEmpty()){     int size=q.size();     while (size-->0){  int curr=q.poll();  int next=map.get(curr);  if (ad.containsKey(next)){      res=Math.max(x-ad.get(next)+1,res);  }  if (next==-1||st[next]) return;  ad.put(next,x+1);  q.offer(next);  st[next]=true;     }     x++; }    }    void add(int a,int b){ map.put(a,b);    }}

5）算法与时间复杂度

  算法：BFS
  时间复杂度：每个点最多访问一次，$O(n)$

5、周赛总结

  图论题不熟练，写的太慢，代码又臭又长。