LeetCode第3场双周赛1-3题题解

ゝ一世哀愁。 2021-12-23 01:41 303阅读 0赞

竞赛链接：[https://leetcode-cn.com/contest/biweekly-contest-3][https_leetcode-cn.com_contest_biweekly-contest-3]

**1.小于K的两数之和**

给你一个整数数组 `A` 和一个整数 `K`，请在该数组中找出两个元素，使它们的和小于 `K` 但尽可能地接近 `K`，**返回这两个元素的和**。

如不存在这样的两个元素，请返回 `-1`。

**示例 1：**

输入：A = [34,23,1,24,75,33,54,8], K = 60
    输出：58
    解释：
    34 和 24 相加得到 58，58 小于 60，满足题意。

**示例 2：**

输入：A = [10,20,30], K = 15
    输出：-1
    解释：
    我们无法找到和小于 15 的两个元素。

**提示：**

1.  `1 <= A.length <= 100`
2.  `1 <= A[i] <= 1000`
3.  `1 <= K <= 2000`

**思路：**

**将数组种的元素进行两两组合，找到K-A\[i\]-A\[j\]最小的那对返回即可，如果所有的A\[i\]+A\[j\]都大于等于K就返回-1。**

**上AC代码：**

class Solution {
    public:
        int twoSumLessThanK(vector<int>& A, int K) {
            int min=0x3f3f3f3f;
            int len=A.size();
            int i,j;
            int ret=-1;
            for(i=0;i<len-1;i++)
            {
                for(j=i+1;j<len;j++)
                {
                    if(A[i]+A[j]<K)
                    {
                        if(K-A[i]-A[j]<min)
                        {
                            min=K-A[i]-A[j];
                            ret=A[i]+A[j];
                        }
                    }
                }
            }
            return ret;
        }
    };

**2.长度为K的无重复字符子串**

给你一个字符串 `S`，找出所有长度为 `K` 且不含重复字符的子串，请你返回全部满足要求的子串的 **数目**。

**示例 1：**

输入：S = "havefunonleetcode", K = 5
    输出：6
    解释：
    这里有 6 个满足题意的子串，分别是：'havef','avefu','vefun','efuno','etcod','tcode'。

**示例 2：**

输入：S = "home", K = 5
    输出：0
    解释：
    注意：K 可能会大于 S 的长度。在这种情况下，就无法找到任何长度为 K 的子串。

**思路：**

**开一个长度为26的数组dp，每到一个子串的起始位置时就将dp的元素都初始化为0，从起始位置开始遍历K个字母，出现重复的就跳出循环找下一个子串，如果成功遍历完这K个字母就让满足要求的子串个数+1。如果K大于字符串的长度就直接返回0。**

**上AC代码：**

class Solution {
    public:
        int numKLenSubstrNoRepeats(string S, int K) {
            int len=S.size();
            if(K>len)
            {
                return 0;
            }
            int i,j;
            bool dp[26];
            int ret=0;
            for(i=0;i<len;i++)
            {
                memset(dp,0,sizeof(dp));
                if(i+K>len)
                {
                    break;
                }
                for(j=i;j<i+K;j++)
                {
                    if(dp[S[j]-'a']==false)
                    {
                        dp[S[j]-'a']=true;
                    }
                    else
                    {
                       break; 
                    }
                    if(j==i+K-1)
                    {
                        ret++;
                    }
                }
            }
            return ret;
        }
    };

**3.彼此熟识的最早时间**

在一个社交圈子当中，有 `N` 个人。每个人都有一个从 `0` 到 `N-1` 唯一的 id 编号。

我们有一份日志列表 `logs`，其中每条记录都包含一个非负整数的时间戳，以及分属两个人的不同 id，`logs[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 = 20190101，0 和 1 成为好友，社交朋友圈如下 [0,1], [2], [3], [4], [5]。
    第二次结交发生在 timestamp = 20190104，3 和 4 成为好友，社交朋友圈如下 [0,1], [2], [3,4], [5].
    第三次结交发生在 timestamp = 20190107，2 和 3 成为好友，社交朋友圈如下 [0,1], [2,3,4], [5].
    第四次结交发生在 timestamp = 20190211，1 和 5 成为好友，社交朋友圈如下 [0,1,5], [2,3,4].
    第五次结交发生在 timestamp = 20190224，2 和 4 已经是好友了。
    第六次结交发生在 timestamp = 20190301，0 和 3 成为好友，大家都互相熟识了。

**提示：**

1.  `1 <= N <= 100`
2.  `1 <= logs.length <= 10^4`
3.  `0 <= logs[i][0] <= 10^9`
4.  `0 <= logs[i][1], logs[i][2] <= N - 1`
5.  保证 `logs[i][0]` 中的所有时间戳都不同
6.  `Logs` 不一定按某一标准排序
7.  `logs[i][1] != logs[i][2]`

**思路：**

**并查集。先将所有日志按照时间从小到大排序，形成日志主次表，遍历日志主次表进行并查集的合并操作，合并完后直接进行判断是不是所有的人都在同一个集合里（集合的个数为1），如果是就返回当前遍历到的日志的时间。如果日志主次表都遍历完了还没有使集合的个数为1，就返回-1。**

**上AC代码：**

struct rizhi
    {
        int time;
        int a;
        int b;
    };
    bool cmp(rizhi x,rizhi y)
    {
        return x.time<y.time;
    }
    class Solution {
    public:
        rizhi rz[10001];
        int f[100];
        int Find(int x)
        {
            if(x==f[x])
                return x;
            else
                return Find(f[x]);
        }
        int earliestAcq(vector<vector<int>>& logs, int N) {
            
            int i,j;
            int len=logs.size();
            for(i=0;i<len;i++)
            {
                rz[i].time=logs[i][0];
                rz[i].a=logs[i][1];
                rz[i].b=logs[i][2];
            }
            sort(rz,rz+len,cmp);
            //初始化并查集
            for(i=0;i<N;i++)
            {
                f[i]=i;
            }
            for(i=0;i<len;i++)
            {
                f[Find(rz[i].a)]=Find(rz[i].b);
                //检查是否只有一个根
                bool flag=true;
                int change=Find(0);
                for(j=1;j<N;j++)
                {
                    if(Find(j)!=change)
                    {
                        flag=false;
                        break;
                    }
                }
                if(flag)
                {
                    return rz[i].time;
                }
            }
            return -1;
        }
    };

**欢迎大家关注/订阅我的微信公众号Code Art Online，我会在我的公众号分享个人见闻，发现生活趣味；这里不仅有0和1，还有是诗和远方↓↓↓**

![20200227123106884.jpg][]

[https_leetcode-cn.com_contest_biweekly-contest-3]: https://leetcode-cn.com/contest/biweekly-contest-3
[20200227123106884.jpg]: /images/20211220/10bee03aaf5e4929aa04e0666a86bdb6.png