力扣：第 304 场周赛
究极手速场
6132、使数组中所有元素都等于零
问题解析
题意：一个数组，你每次可以将数组的值减少一个整数，这个整数小于等于数组的最小正整数，问多少次操作可以将数组全部变为0
其实这题就是在问数组中有多少个不同的正整数罢了，因为每次操作，我们可以把数组中最小的正整数全部变成0。那么数组中有多少个不同的正整数，我们就减几次就可以了。
AC代码
class Solution {
public:
int minimumOperations(vector<int>& nums) {
sort(nums.begin(),nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
return nums[0]==0?nums.size()-1:nums.size();
}
};
6133. 分组的最大数量
问题解析
题意：一个数组，你要将数组分成几份，第i份的数字个数和数字总和要严格小于第i+1份，问你最多可以分成几份。
实际上，如果我们把数组升序排序就可以知道，只要第i+1份的数字个数大于第i份，那么i+1份的数组总和是一定大于第i份的，我们只要把小的数先分类好，再分大的即可。
那么问题就在数字个数上了，要尽可能多的分，那么贪心来说就要分成：一个数，两个数，三个树……，n个数这样，所以就看数组的长度按照这么分能满足分成多少组就行。
AC代码
class Solution {
public:
int maximumGroups(vector<int>& grades) {
int n=grades.size(),x=1,y=2;
while(x<n)x+=y++;
return n==x?y-1:y-2;
}
};
6134. 找到离给定两个节点最近的节点
问题解析
题意：一个带环单向图，给你两个点，问这两个点都能到达的一个点且距离最近的点是哪个。
建图后进行两遍dfs，第一遍先按照node0为出发点进行dfs，记录下node0能到达的所有点，并记录下node0到达这些点的距离。
再以node1为起点dfs，也记录走过的路，如果遍历到的点在第一次dfs中被记录到了，说明这个点node0和node1都可以到达，然后根据这个点到达node0和node1的距离来更新答案即可。
但是这图是带环的，单纯dfs会t的，我们可以把走过的点打上标记，当走到重复的点时我们直接停下不走这个点。
AC代码
class Solution {
public:
vector<int>v[100050];
unordered_map<int,int>mymap;
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<mx)
{
mx=t;
pos=x;
}
else if(t==mx)
{
mx=t;
pos=min(pos,x);
}
}
for(auto i:v[x])
{
dfs2(i,res+1);
}
}
int closestMeetingNode(vector<int>& edges, int node1, int node2) {
int n=edges.size();
for(int i=0;i<n;i++)
{
v[i].push_back(edges[i]);
}
dfs(node1,0);
dfs2(node2,0);
return pos;
}
};
6135. 图中的最长环
问题解析
题意：一个单向图，让你找出最大的一个环，求这个环的长度。
我们用一个标记数组标记走过的所有点，建图后以每个点为起点进行一遍dfs，如果这个点已经被打上标记了，我们就不以它为起点dfs。
每次dfs记录起点y到当前点x的距离，并且记录从起点出发一共走了多少距离，如果我们走到y点发现这个点已经被打上标记了，那么就有两种可能
- 这个点是其它点之前dfs时被打上标记的，那么起点到当前点的距离就等于起点走过的距离，没有环。
- 这个点我们在这一次dfs走过了两次，那么起点到当前点的距离就小于起点走过的距离，有环，而这段距离的差值就是环的大小。
我们只要维护环的最大值即可。
AC代码
class Solution {
public:
vector<int>v[100050];
int len=-1;
int st[100050];
unordered_map<int,unordered_map<int,int>>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<int>& edges) {
int n=edges.size();
for(int i=0;i<n;i++)
v[i].push_back(edges[i]);
for(int i=0;i<n;i++)
{
if(st[i]==0)
dfs(i,i,0);
}
return len;
}
};
|