【周赛复盘】LeetCode第304场单周赛

【周赛复盘】LeetCode第304场单周赛

目录

​​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）思路解析

4）模板代码

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

5）算法与时间复杂度

2、分组的最大数量

1）题目描述

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

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

2）原题链接

​​LeetCode.6133. 分组的最大数量​

3）思路解析

4）模板代码

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

5）算法与时间复杂度

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）思路解析

4）模板代码

Map map=new HashMap<>(); int N=100010; int[] dist=new int[N]; int ans=Integer.MAX_VALUE; Set s1=new HashSet<>(); Set s2=new HashSet<>(); int jie=-1; public int closestMeetingNode(int[] edges, int node1, int node2) { int n=edges.length; for (int i = 0; i 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）算法与时间复杂度

4.图中最长环

1）题目描述

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

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

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

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

​

3）思路解析

4）模板代码

class Solution { boolean[] st=new boolean[100010]; Map map=new HashMap<>(); int res=0; public int longestCycle(int[] edges) { int n=edges.length; for (int i = 0; i q=new LinkedList<>(); st[start]=true; q.offer(start); Map 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）算法与时间复杂度

5、周赛总结

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。