leetcode赛后补题: 322周赛题解
又是一周过去了, 这周又在 leetcode 上开了一场周赛，总共吃了 6 个罚时，导致排名并不乐观。。。
I. circular-sentence(模拟)
题目地址:
https://leetcode.cn/problems/circular-sentence/
A sentence is a list of words that are separated by a single space with no leading or trailing spaces.
For example, "Hello World", "HELLO", "hello world hello world" are all sentences.
Words consist of only uppercase and lowercase English letters. Uppercase and lowercase English letters are considered different.
A sentence is circular if:
The last character of a word is equal to the first character of the next word.
The last character of the last word is equal to the first character of the first word.
For example, "leetcode exercises sound delightful", "eetcode", "leetcode eats soul" are all circular sentences. However, "Leetcode is cool", "happy Leetcode", "Leetcode" and "I like Leetcode" are not circular sentences.
Given a string sentence, return true if it is circular. Otherwise, return false.
Example 1:
Input: sentence = "leetcode exercises sound delightful"
Output: true
Explanation: The words in sentence are ["leetcode", "exercises", "sound", "delightful"].
- leetcode's last character is equal to exercises's first character.
- exercises's last character is equal to sound's first character.
- sound's last character is equal to delightful's first character.
- delightful's last character is equal to leetcode's first character.
The sentence is circular.
Example 2:
Input: sentence = "eetcode"
Output: true
Explanation: The words in sentence are ["eetcode"].
- eetcode's last character is equal to eetcode's first character.
The sentence is circular.
Example 3:
Input: sentence = "Leetcode is cool"
Output: false
Explanation: The words in sentence are ["Leetcode", "is", "cool"].
- Leetcode's last character is not equal to is's first character.
The sentence is not circular.
大意是给你个句子把每个单词拆分出来, 在判断每个单词的首末位置是否构成一个环.
比如说:
拆分调用Python中的split函数，直接模拟即可:
时间复杂度：O(n)
II.divide-players-into-teams-of-equal-skill(哈希表)
You are given a positive integer array skill of even length n where skill[i] denotes the skill of the ith player. Divide the players into n / 2 teams of size 2 such that the total skill of each team is equal.
The chemistry of a team is equal to the product of the skills of the players on that team.
Return the sum of the chemistry of all the teams, or return -1 if there is no way to divide the players into teams such that the total skill of each team is equal.
Example 1:
Input: skill = [3,2,5,1,3,4]
Output: 22
Explanation:
Divide the players into the following teams: (1, 5), (2, 4), (3, 3), where each team has a total skill of 6.
The sum of the chemistry of all the teams is: 1 * 5 + 2 * 4 + 3 * 3 = 5 + 8 + 9 = 22.
Example 2:
Input: skill = [3,4]
Output: 12
Explanation:
The two players form a team with a total skill of 7.
The chemistry of the team is 3 * 4 = 12.
Example 3:
Input: skill = [1,1,2,3]
Output: -1
Explanation:
There is no way to divide the players into teams such that the total skill of each team is equal.
给定一个偶数长度 n 的数组表示员工的技能，分成技能相同的组并计算出化学反应(The chemistry of a team)， 也就是每一组的乘积。
先考虑是否能分组，如果能分组那么总和一定是个合数并且能被分的组数(n / 2)整除。
确定能分组后, 我们可以计算出每一组的化学反应, 因为每一组都是相等的，假设这个值是 , 那么问题就可以转化为在一个数组中寻找两个数的和等于
的数量，如果存在 n / 2个，那么就可以分组并计算出化学反应了!
III. minimum-score-of-a-path-between-two-cities/submissions(图论 + 并查集)
You are given a positive integer n representing n cities numbered from 1 to n. You are also given a 2D array roads where roads[i] = [ai, bi, distancei] indicates that there is a bidirectional road between cities ai and bi with a distance equal to distancei. The cities graph is not necessarily connected.
The score of a path between two cities is defined as the minimum distance of a road in this path.
Return the minimum possible score of a path between cities 1 and n.
Note:
A path is a sequence of roads between two cities.
It is allowed for a path to contain the same road multiple times, and you can visit cities 1 and n multiple times along the path.
The test cases are generated such that there is at least one path between 1 and n.
Example 1:
Input: n = 4, roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]]
Output: 5
Explanation: The path from city 1 to 4 with the minimum score is: 1 -> 2 -> 4. The score of this path is min(9,5) = 5.
It can be shown that no other path has less score.
Example 2:
Input: n = 4, roads = [[1,2,2],[1,3,4],[3,4,7]]
Output: 2
Explanation: The path from city 1 to 4 with the minimum score is: 1 -> 2 -> 1 -> 3 -> 4. The score of this path is min(2,2,4,7) = 2.
大意是让你找出 从 1 到 城市 n 所以路径中的最小值, 注意这里并不是路径和的最小值!
首先我们可以证明 这条路径是一定是包含 1 和 n的， 这非常显然。根据题意这条路径是一定存在的，那么我们可以证明 1 和 n 是连通的.
接下来证明我们的答案是 1 和 n 所属连通块中的路径最小值。
我们由连通块的定义可知, 在连通块内的点集 中， 其中的每一个点都相互到达，也就是在连通块内存在一条路径
, 经过某一节点的位置是最小的。
问题就变得简单了，如何寻找图的连通块呢? 我们可以使用并查集这种结构。什么是并查集呢，这是一种专门维护一组数组的从属关系的数据结构。本质上就是用数组模拟了一颗树(是不是想起来树状数组呢?), 下面简单介绍一下:
初始化 ：每个元素的父节点为本身，也就是"自成一派", 用一个数组pre来存放每个元素的父节点:
如何寻找呢? 由上面初始化来看，如果自己的父节点是自己的话，那么说明已经找到父节点了， 否则不断先上寻找.。(想象一颗树至底向上搜索的过程)
我们可以进行优化，们可以在他返回的时候将他路径上的每个节点的父节点全部改为根节点。这样就减少了搜索的时间了。
接下来是合并两个元素的操作, 寻找两个元素的父节点，如果不相等(不是同一节点)，修改pre改变从属关系进行合并:
那么就可以解决了:
关于并查集还有很多有意思的东西，比如它的时间复杂度是一个特殊的函数, 还可以用秩来对合并操作进行优化，具体可以移步<<算法导论>>.
