建设银行 网站设置密码,wordpress文章内多页效果,未来做哪些网站能致富,php网站开发技术是什么文章目录1. 题目2. 解题1. 题目
在一个社交圈子当中#xff0c;有 N 个人。每个人都有一个从 0 到 N-1 唯一的 id 编号。
我们有一份日志列表 logs#xff0c;其中每条记录都包含一个非负整数的时间戳#xff0c;以及分属两个人的不同 id#xff0c;logs[i] [timestamp,…
文章目录1. 题目2. 解题1. 题目
在一个社交圈子当中有 N 个人。每个人都有一个从 0 到 N-1 唯一的 id 编号。
我们有一份日志列表 logs其中每条记录都包含一个非负整数的时间戳以及分属两个人的不同 idlogs[i] [timestamp, id_A, id_B]。
每条日志标识出两个人成为好友的时间友谊是相互的如果 A 和 B 是好友那么 B 和 A 也是好友。
如果 A 是 B 的好友或者 A 是 B 的好友的好友那么就可以认为 A 也与 B 熟识。
返回圈子里所有人之间都熟识的最早时间。如果找不到最早时间就返回 -1 。
示例
输入logs [[20190101,0,1],[20190104,3,4],[20190107,2,3],[20190211,1,5],[20190224,2,4],[20190301,0,3],[20190312,1,2],[20190322,4,5]],N 6
输出20190301
解释
第一次结交发生在 timestamp 201901010 和 1 成为好友
社交朋友圈如下 [0,1], [2], [3], [4], [5]。
第二次结交发生在 timestamp 201901043 和 4 成为好友
社交朋友圈如下 [0,1], [2], [3,4], [5].
第三次结交发生在 timestamp 201901072 和 3 成为好友
社交朋友圈如下 [0,1], [2,3,4], [5].
第四次结交发生在 timestamp 201902111 和 5 成为好友
社交朋友圈如下 [0,1,5], [2,3,4].
第五次结交发生在 timestamp 201902242 和 4 已经是好友了。
第六次结交发生在 timestamp 201903010 和 3 成为好友大家都互相熟识了。提示1 N 100
1 logs.length 10^4
0 logs[i][0] 10^9
0 logs[i][1], logs[i][2] N - 1
保证 logs[i][0] 中的所有时间戳都不同
Logs 不一定按某一标准排序
logs[i][1] ! logs[i][2]来源力扣LeetCode 链接https://leetcode-cn.com/problems/the-earliest-moment-when-everyone-become-friends 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
参考数据结构并查集
先按时间排序按时间顺序合并两个人检查是否只有一个团如果是返回当前时间
class dsu
{vectorint f;
public:dsu(int n){f.resize(n);for(int i 0; i n; i)f[i] i;}void merge(int a, int b){int fa find(a);int fb find(b);f[fa] fb;}int find(int a){int origin a;while(a ! f[a])a f[a];return f[origin] a;}bool onlyOne(){int count 0;for(int i 0; i f.size(); i){if(i find(i))count;if(count 1)return false;}return true;}
};
class Solution {
public:int earliestAcq(vectorvectorint logs, int N) {sort(logs.begin(), logs.end(),[](auto a, auto b){return a[0] b[0];});dsu u(N);for(auto lg : logs){u.merge(lg[1], lg[2]);if(u.onlyOne())return lg[0];}return -1;}
};244 ms 32.4 MB
或者有效的合并 N-1次就完成了
class dsu
{vectorint f;
public:dsu(int n){f.resize(n);for(int i 0; i n; i)f[i] i;}void merge(int a, int b){int fa find(a);int fb find(b);f[fa] fb;}bool weAreFriend(int a, int b){int fa find(a);int fb find(b);return fa fb;}int find(int a){int origin a;while(a ! f[a])a f[a];return f[origin] a;}
};
class Solution {
public:int earliestAcq(vectorvectorint logs, int N) {sort(logs.begin(), logs.end(),[](auto a, auto b){return a[0] b[0];});dsu u(N);for(auto lg : logs){if(!u.weAreFriend(lg[1], lg[2])){ //不是朋友时才进行合并u.merge(lg[1], lg[2]);N--;if(N1)//合并了N-1次找到了return lg[0];}}return -1;}
};240 ms 32.3 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
