力扣第322场周赛

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：

输入：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 的第一个字符相等。
这个句子是回环句。

提示：

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

C++

class Solution {
public:
    bool isCircularSentence(string sentence) {
        stringstream ssin(sentence); // 记住 stringstream ssin(sentence);
        string str;
        vector<string> strs;
        while(ssin >> str) strs.push_back(str);
        for(int i = 0; i < strs.size(); i ++){
            if(strs[i].back() != strs[(i + 1)%strs.size()][0]) return false;
        }
        return true;
    }
};

165. 比较版本号

给你两个版本号 version1 和 version2 ，请你比较它们。

版本号由一个或多个修订号组成，各修订号由一个 '.' 连接。每个修订号由 多位数字 组成，可能包含 前导零 。每个版本号至少包含一个字符。修订号从左到右编号，下标从 0 开始，最左边的修订号下标为 0 ，下一个修订号下标为 1 ，以此类推。例如，2.5.33 和 0.1 都是有效的版本号。

比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较 忽略任何前导零后的整数值 。也就是说，修订号 1 和修订号 001 相等 。如果版本号没有指定某个下标处的修订号，则该修订号视为 0 。例如，版本 1.0 小于版本 1.1 ，因为它们下标为 0 的修订号相同，而下标为 1 的修订号分别为 0 和 1 ，0 < 1 。

返回规则如下：

• 如果 *version1* > *version2* 返回 1，
• 如果 *version1* < *version2* 返回 -1，
• 除此之外返回 0。

示例 1：

输入：version1 = "1.01", version2 = "1.001"
输出：0
解释：忽略前导零，"01" 和 "001" 都表示相同的整数 "1"

示例 2：

输入：version1 = "1.0", version2 = "1.0.0"
输出：0
解释：version1 没有指定下标为 2 的修订号，即视为 "0"

示例 3：

输入：version1 = "0.1", version2 = "1.1"
输出：-1
解释：version1 中下标为 0 的修订号是 "0"，version2 中下标为 0 的修订号是 "1" 。0 < 1，所以 version1 < version2

提示：

• 1 <= version1.length, version2.length <= 500
• version1 和 version2 仅包含数字和 '.'
• version1 和 version2 都是 有效版本号
• version1 和 version2 的所有修订号都可以存储在 32 位整数 中

C++

class Solution {
public:
    int compareVersion(string version1, string version2) {
        version1 += '.';
        version2 += '.';

        string s1, s2;
        stringstream ss1(version1), ss2(version2);

        while(1){
            getline(ss1, s1, '.');
            getline(ss2, s2, '.');
            if(s1.empty() && s2.empty()) return 0;
            else {
                int a = !s1.empty() ? stoi(s1) : 0, b = !s2.empty() ? stoi(s2) : 0;
                if((a || b) && a != b) return a > b ? 1 : -1;
            }
        }
    }
};

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

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

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

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

示例 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 人团队。

提示：

• 2 <= skill.length <= 105
• skill.length 是偶数
• 1 <= skill[i] <= 1000

C++

class Solution {
public:
    long long dividePlayers(vector<int>& skill) {
        long long res = 0;
        int Sum = 0;
        for(int elem: skill) Sum += elem;
        int teamNum = skill.size()/ 2;
        if(Sum % teamNum) return -1;
        int sum = Sum/ teamNum;
        
        unordered_map<int, int> mp;
        for(int elem: skill){
            int temp = sum - elem;
            if(mp[temp]){
                res += temp* elem;
                mp[temp] --;
            } 
            else mp[elem] ++;
        }

        for(auto elem: mp){
            if(elem.second) return -1;
        }
        return res;
    }
};

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

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

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

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

注意：

• 一条路径指的是两个城市之间的道路序列。
• 一条路径可以 多次 包含同一条道路，你也可以沿着路径多次到达城市 1 和城市 n 。
• 测试数据保证城市 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 。

提示：

• 2 <= n <= 105
• 1 <= roads.length <= 105
• roads[i].length == 3
• 1 <= ai, bi <= n
• ai != bi
• 1 <= distancei <= 104
• 不会有重复的边。
• 城市 1 和城市 n 之间至少有一条路径。

C++

// 并查集
// merge合并两个集合；(“并”）
// find判断两个元素是否属于同一个集合．（“查”）
class Solution {
public:
    vector<int> v;
    
    int find(int x) { //查看x的根节点 -> x所属集合
        if (v[x] != x) v[x] = find(v[x]);
        return v[x];
    }

    int minScore(int n, vector<vector<int>>& roads) {
        v.resize(n + 1);
        vector<int> w(n + 1, 1e8);
        for (int i = 1; i <= n; i ++ ) v[i] = i; // 初始化并查集，每个节点的根结点都是自己
        for (auto& edge: roads) {
            int a = find(edge[0]), b = find(edge[1]), c = edge[2];// a为边起始点的根节点 b为边结束点的根节点 c为权值
            w[a] = min({w[a], w[b], c});
            v[b] = a; // 并
        }

        return w[find(1)];
    }
};