又是一周過(guò)去了, 這周又在 leetcode 上開(kāi)了一場(chǎng)周賽，總共吃了 6 個(gè)罰時(shí)，導(dǎo)致排名并不樂(lè)觀。。。

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.

大意是給你個(gè)句子把每個(gè)單詞拆分出來(lái), 在判斷每個(gè)單詞的首末位置是否構(gòu)成一個(gè)環(huán).

比如說(shuō):

拆分調(diào)用Python中的split函數(shù)，直接模擬即可:

時(shí)間復(fù)雜度：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.

給定一個(gè)偶數(shù)長(zhǎng)度 n 的數(shù)組表示員工的技能，分成技能相同的組并計(jì)算出化學(xué)反應(yīng)(The chemistry of a team)， 也就是每一組的乘積。

先考慮是否能分組，如果能分組那么總和一定是個(gè)合數(shù)并且能被分的組數(shù)(n / 2)整除。

確定能分組后, 我們可以計(jì)算出每一組的化學(xué)反應(yīng), 因?yàn)槊恳唤M都是相等的，假設(shè)這個(gè)值是?, 那么問(wèn)題就可以轉(zhuǎn)化為在一個(gè)數(shù)組中尋找兩個(gè)數(shù)的和等于? 的數(shù)量，如果存在 n / 2個(gè)，那么就可以分組并計(jì)算出化學(xué)反應(yīng)了!

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的， 這非常顯然。根據(jù)題意這條路徑是一定存在的，那么我們可以證明 1 和 n 是連通的.

接下來(lái)證明我們的答案是 1 和 n 所屬連通塊中的路徑最小值。

我們由連通塊的定義可知, 在連通塊內(nèi)的點(diǎn)集??中， 其中的每一個(gè)點(diǎn)都相互到達(dá)，也就是在連通塊內(nèi)存在一條路徑?, 經(jīng)過(guò)某一節(jié)點(diǎn)的位置是最小的。

問(wèn)題就變得簡(jiǎn)單了，如何尋找圖的連通塊呢? 我們可以使用并查集這種結(jié)構(gòu)。什么是并查集呢，這是一種專門維護(hù)一組數(shù)組的從屬關(guān)系的數(shù)據(jù)結(jié)構(gòu)。本質(zhì)上就是用數(shù)組模擬了一顆樹(shù)(是不是想起來(lái)樹(shù)狀數(shù)組呢?), 下面簡(jiǎn)單介紹一下:

初始化 ：每個(gè)元素的父節(jié)點(diǎn)為本身，也就是"自成一派", 用一個(gè)數(shù)組pre來(lái)存放每個(gè)元素的父節(jié)點(diǎn):

如何尋找呢? 由上面初始化來(lái)看，如果自己的父節(jié)點(diǎn)是自己的話，那么說(shuō)明已經(jīng)找到父節(jié)點(diǎn)了， 否則不斷先上尋找.。(想象一顆樹(shù)至底向上搜索的過(guò)程)

我們可以進(jìn)行優(yōu)化，們可以在他返回的時(shí)候?qū)⑺窂缴系?strong>每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)全部改為根節(jié)點(diǎn)。這樣就減少了搜索的時(shí)間了。

接下來(lái)是合并兩個(gè)元素的操作, 尋找兩個(gè)元素的父節(jié)點(diǎn)，如果不相等(不是同一節(jié)點(diǎn))，修改pre改變從屬關(guān)系進(jìn)行合并:

那么就可以解決了:

關(guān)于并查集還有很多有意思的東西，比如它的時(shí)間復(fù)雜度是一個(gè)特殊的函數(shù), 還可以用秩來(lái)對(duì)合并操作進(jìn)行優(yōu)化，具體可以移步<<算法導(dǎo)論>>.