算法leetcode

leetcode第322场周赛：搜索专场

字数统计: 3.6k字   |   阅读时长: 15分
,

摘要: 本文是 leetcode 第 322 周赛的记录。主要涉及的算法包括单串单向双指针、哈希表、BFS、BFS

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

总览

本周进行了 leetcode 第 322 场周赛，本场比赛由阿里巴巴质量创新大会赞助，奖品如下：

  • 排名第 1 - 2 名的参赛者可「阿里巴巴质量创新大会 TICA」门票 x1
  • 排名第 3 - 5 名的参赛者可「阿里巴巴质量创新大会 TICA」提供的精美小礼品 x1

这场比赛的奖励是见过的最少的了。只有前五名才有，并且没有内推奖励。阿里不用多介绍了，阿里巴巴质量创新大会 TICA（Test Innovation Conference of Alibaba）已经举办了 3 届，今年是第 4 届，12 月 15 日举办，主要有高可用、大数据&智能化、工程效能、IOT&端智能、数字化转型等等共五个专场。本次大会的亮点是与阿里云合作，新设数字化转型分会场，我们希望把有转型计划和在转型路上的传统企业聚集到一起，分享数字化转型经验。不过这个大会是要买票的，感兴趣的话详见下面这篇文章的介绍：

1
https://developer.aliyun.com/article/1068574

介绍完赞助公司，回到本场比赛。本场比赛的前三题非常简单，在通过率上也能反映出来，分别通过了 4000 人，2000 人，3000 人。也就是说仅仅是完成前三题的话，名次也不会太高，这里面有力扣知名度越来越高的功劳，越来越多的高手来打力扣的周赛了。可惜的是第四题还是没有在比赛中做出来，最终名次 1204/5085，这次的成绩如下：

本场比赛的两点是 C 题和 D 题都是搜索的问题，C 题的框架是 DFS、D 题的框架是 BFS，两者在搜索过程中都要维护一些复杂信息或数据结构。因此本场比赛可以成为搜索专场。

各个题目涉及到的知识点汇总如下：

往期参加比赛的记录如下：

【连载】leetcode周赛

A 题

2490. 回环句

句子 是由单个空格分隔的一组单词，且不含前导或尾随空格。

例如，”Hello World”、”HELLO”、”hello world hello world” 都是符合要求的句子。

单词 仅 由大写和小写英文字母组成。且大写和小写字母会视作不同字符。

如果句子满足下述全部条件，则认为它是一个 回环句 ：

  • 单词的最后一个字符和下一个单词的第一个字符相等。
  • 最后一个单词的最后一个字符和第一个单词的第一个字符相等。

例如，”leetcode exercises sound delightful”、”eetcode”、”leetcode eats soul” 都是回环句。然而，”Leetcode is cool”、”happy Leetcode”、”Leetcode” 和 “I like Leetcode” 都 不 是回环句。

给你一个字符串 sentence ，请你判断它是不是一个回环句。如果是，返回 true ；否则，返回 false 。

提示：

1
2
3
4
1 <= sentence.length <= 500
sentence 仅由大小写英文字母和空格组成
sentence 中的单词由单个空格进行分隔
不含任何前导或尾随空格

示例 1：
输入：sentence = “leetcode exercises sound delightful”
输出：true
解释：句子中的单词是 [“leetcode”, “exercises”, “sound”, “delightful”] 。

  • leetcode 的最后一个字符和 exercises 的第一个字符相等。
  • exercises 的最后一个字符和 sound 的第一个字符相等。
  • sound 的最后一个字符和 delightful 的第一个字符相等。
  • delightful 的最后一个字符和 leetcode 的第一个字符相等。
    这个句子是回环句。

示例 2：
输入：sentence = “eetcode”
输出：true
解释：句子中的单词是 [“eetcode”] 。

  • eetcode 的最后一个字符和 eetcode 的第一个字符相等。
    这个句子是回环句。

示例 3：
输入：sentence = “Leetcode is cool”
输出：false
解释：句子中的单词是 [“Leetcode”, “is”, “cool”] 。

  • Leetcode 的最后一个字符和 is 的第一个字符 不 相等。
    这个句子 不 是回环句。

算法: 单串单向双指针

维护双指针 [left, right]，每次遇到新词的起始位置时，更新 left 为新词的起始位置，然后 right 从 left 开始向右推进，直至单词末尾。然后根据区间 [left, right] 表示的单词做相应的操作即可。

代码(C++)

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
class Solution {
public:
    bool isCircularSentence(string sentence) {
        int n = sentence.size();
        int left = 0;
        while(left < n)
        {
            int right = left;
            while(right < n && sentence[right] != ' ')
                right++;
            if(right == n)
            {
                if(sentence[0] != sentence[right - 1])
                    return false;
            }
            else
            {
                if(sentence[right + 1] != sentence[right - 1])
                    return false;
            }
            left = right + 1;
        }
        return true;
    }
};

B 题

2491. 划分技能点相等的团队

给你一个正整数数组 skill ，数组长度为 偶数 n ，其中 skill[i] 表示第 i 个玩家的技能点。将所有玩家分成 n / 2 个 2 人团队，使每一个团队的技能点之和 相等 。

团队的 化学反应 等于团队中玩家的技能点 乘积 。

返回所有团队的 化学反应 之和，如果无法使每个团队的技能点之和相等，则返回 -1 。

提示：

1
2
3
2 <= skill.length <= 1e5
skill.length 是偶数
1 <= skill[i] <= 1000

示例 1：
输入：skill = [3,2,5,1,3,4]
输出：22
解释：
将玩家分成 3 个团队 (1, 5), (2, 4), (3, 3) ，每个团队的技能点之和都是 6 。
所有团队的化学反应之和是 1 5 + 2 4 + 3 * 3 = 5 + 8 + 9 = 22 。

示例 2：
输入：skill = [3,4]
输出：12
解释：
两个玩家形成一个团队，技能点之和是 7 。
团队的化学反应是 3 * 4 = 12 。

示例 3：
输入：skill = [1,1,2,3]
输出：-1
解释：
无法将玩家分成每个团队技能点都相等的若干个 2 人团队。

算法: 哈希表

由于数字范围是 1 ~ 1000，开一个长度 1001 的数组 cnts，其中 cnts[x] 表示数字 x 出现的次数，代替哈希表。

总共要分 n / 2 组，因此我们先看总和 sum 是否能整除 n / 2，如果不能则直接返回 -1，如果能，则记 t = sum / (n / 2)，为每组的两个数字的和。

然后我们一次枚举 skill，假设枚举到 skill[i]，如果 cnts[skill[i]] 大于 0，且 t - skill[i] 在 cnts 的范围中并且对应的值也大于 0，则找到一组数字，更新答案，然后将这一组的两个数字在 cnts 中对应的值减 1。

代码(C++)

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
class Solution {
public:
    long long dividePlayers(vector<int>& skill) {
        int n = skill.size();
        long long sum = 0;
        vector<int> cnts(1001);
        for(int x: skill)
        {
            cnts[x]++;
            sum += x;
        }
        if(sum % (n / 2) != 0)
            return -1;
        int t = sum / (n / 2);
        long long ans = 0;
        for(int i = 0; i < n; ++i)
        {
            if(cnts[skill[i]] == 0)
                continue;
            int a = skill[i];
            cnts[skill[i]]--;
            int b = t - a;
            if(b < 0 || cnts[b] == 0)
                return -1;
            cnts[b]--;
            ans += a * b;
        }
        return ans;
    }
};

C 题

2492. 两个城市间路径的最小分数

给你一个正整数 n ，表示总共有 n 个城市，城市从 1 到 n 编号。给你一个二维数组 roads ，其中 roads[i] = [ai, bi, distancei] 表示城市 ai 和 bi 之间有一条 双向 道路，道路距离为 distancei 。城市构成的图不一定是连通的。

两个城市之间一条路径的 分数 定义为这条路径中道路的 最小 距离。

城市 1 和城市 n 之间的所有路径的 最小 分数。

注意：

  • 一条路径指的是两个城市之间的道路序列。
  • 一条路径可以 多次 包含同一条道路，你也可以沿着路径多次到达城市 1 和城市 n 。
  • 测试数据保证城市 1 和城市n 之间 至少 有一条路径。

提示：

1
2
3
4
5
6
7
8
2 <= n <= 1e5
1 <= roads.length <= 1e5
roads[i].length == 3
1 <= ai, bi <= n
ai != bi
1 <= distancei <= 1e4
不会有重复的边。
城市 1 和城市 n 之间至少有一条路径。

示例 1：

输入：n = 4, roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]]
输出：5
解释：城市 1 到城市 4 的路径中，分数最小的一条为：1 -> 2 -> 4 。这条路径的分数是 min(9,5) = 5 。
不存在分数更小的路径。

示例 2：

输入：n = 4, roads = [[1,2,2],[1,3,4],[3,4,7]]
输出：2
解释：城市 1 到城市 4 分数最小的路径是：1 -> 2 -> 1 -> 3 -> 4 。这条路径的分数是 min(2,2,4,7) = 2 。

算法: DFS、哈希表

首先枚举所有的边，建立邻接表 g。

从节点 1 出发，在邻接表 g 上进行一次 DFS，将所有访问到的节点记录到一个哈希表 setting 中。

然后再次枚举所有的边，如果该边的第一个点在哈希表 setting 中，则该边的两个节点与节点 1 是连通的，是候选答案。如果该边长度是当前候选答案中最小的，则更新答案。

代码(C++)

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
struct Edge
{
    int v;
    int d;
    Edge(){}
    Edge(int v, int d):v(v),d(d){}
};

class Solution {
public:
    int minScore(int n, vector<vector<int>>& roads) {
        vector<vector<Edge>> g(n + 1);
        for(const vector<int> &road: roads)
        {
            g[road[0]].emplace_back(road[1], road[2]);
            g[road[1]].emplace_back(road[0], road[2]);
        }
        vector<int> visited(n + 1);
        unordered_set<int> setting;
        dfs(g, 1, setting, visited);
        int ans = 1e4 + 1;
        for(const vector<int> &road: roads)
        {
            if(setting.count(road[0]) == 0)
                continue;
            ans = min(ans, road[2]);
        }
        return ans;
    }

    void dfs(const vector<vector<Edge>>& g, int u, unordered_set<int>& setting, vector<int>& visited)
    {
        setting.insert(u);
        for(const Edge &e: g[u])
        {
            if(visited[e.v] == 1)
                continue;
            visited[e.v] = 1;
            dfs(g, e.v, setting, visited);
        }
    }
};

D 题

2493. 将节点分成尽可能多的组

给你一个正整数 n ，表示一个 无向 图中的节点数目，节点编号从 1 到 n 。

同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 双向 边。注意给定的图可能是不连通的。

请你将图划分为 m 个组（编号从 1 开始），满足以下要求：

  • 图中每个节点都只属于一个组。
  • 图中每条边连接的两个点 [ai, bi] ，如果 ai 属于编号为 x 的组，bi 属于编号为 y 的组，那么 |y - x| = 1 。

请你返回最多可以将节点分为多少个组（也就是最大的 m ）。如果没办法在给定条件下分组，请你返回 -1 。

提示：

1
2
3
4
5
6
1 <= n <= 500
1 <= edges.length <= 1e4
edges[i].length == 2
1 <= ai, bi <= n
ai != bi
两个点之间至多只有一条边。

示例 1：

输入：n = 6, edges = [[1,2],[1,4],[1,5],[2,6],[2,3],[4,6]]
输出：4
解释：如上图所示，

  • 节点 5 在第一个组。
  • 节点 1 在第二个组。
  • 节点 2 和节点 4 在第三个组。
  • 节点 3 和节点 6 在第四个组。
    所有边都满足题目要求。
    如果我们创建第五个组，将第三个组或者第四个组中任何一个节点放到第五个组，至少有一条边连接的两个节点所属的组编号不符合题目要求。

示例 2：
输入：n = 3, edges = [[1,2],[2,3],[3,1]]
输出：-1
解释：如果我们将节点 1 放入第一个组，节点 2 放入第二个组，节点 3 放入第三个组，前两条边满足题目要求，但第三条边不满足题目要求。
没有任何符合题目要求的分组方式。

算法: BFS

由于图是不连通的，我们可以对每个连通分量分别求最多可以分的组数，然后相加得到答案。

对于一个连通分量，枚举每个点作为起点，然后把该连通分量 BFS 一遍，得到该起点下的最大深度，在所有起点中对应的最大深度的最大值为该连通分量下我们要求的最大组数。

在 BFS 过程中，记录一个数组 levels，levels[u] 表示 u 对应的 level，如果某个点 u 的子节点为 v，则合法的 v 有三种情况：

  • v 尚未访问到 (levels[v] == -1)
  • levels[v] == levels[u] - 1
  • levels[v] == levels[u] + 1

如果不满足这三种情况，直接返回 -1。

另外在下面的代码中求连通分量的过程可以在求最大深度的 BFS 过程中顺便做了，可以少写一些代码。

由于边数为 m=1e4，点数为 n=500，时间复杂度 $O(nm)$ 可以完成。

代码(C++)

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class Solution {
public:
    int magnificentSets(int n, vector<vector<int>>& edges) {
        vector<vector<int>> g(n + 1);
        for(const vector<int> &e: edges)
        {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
        }
        connected_component.assign(n + 1, 0);
        int ans = 0;
        int id = 1;
        for(int u = 1; u <= n; ++u)
        {
            if(connected_component[u] != 0)
                continue;
            // u 代表一个新的连通分量
            int max_level = solve(g, u, id++);
            if(max_level == -1)
                return -1;
            ans += max_level + 1;
        }
        return ans;
    }

    vector<int> levels;
    vector<int> connected_component;

    int solve(const vector<vector<int>>& g, int u, const int id)
    {
        int n = g.size() - 1;
        levels.assign(n + 1, -1);
        int max_level = bfs(g, u, id);
        if(max_level == -1)
            return -1;
        int ans = max_level;
        for(int uu = u + 1; uu <= n; ++uu)
        {
            if(connected_component[uu] != id)
                continue;
            levels.assign(n + 1, -1);
            int max_level = bfs(g, uu, id);
            ans = max(ans, max_level);
        }
        return ans;
    }

    int bfs(const vector<vector<int>>& g, int start, const int id)
    {
        int max_level = 0;
        queue<int> q;
        levels[start] = 0;
        q.push(start);
        while(!q.empty())
        {
            int u = q.front();
            connected_component[u] = id;
            int level = levels[u];
            q.pop();
            max_level = max(max_level, level);
            for(int v: g[u])
            {
                if(levels[v] != -1)
                {
                    if(levels[v] != level - 1 && levels[v] != level + 1)
                        return -1;
                    continue;
                }
                levels[v] = level + 1;
                q.push(v);
            }
        }
        return max_level;
    }
};
Share