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();
    }
1
2
3
4
5
6
7
8

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;
    }

1
2
3
4
5
6
7
8
9
10
11
12

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);
    }
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

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);
    }
}
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

5）算法与时间复杂度

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

5、周赛总结

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