[Leetcode Weekly Contest]322

链接：LeetCode

[Leetcode]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 。

遍历即可。

class Solution {
    public boolean isCircularSentence(String sentence) {
        String[] words = sentence.split(" ");
        int n = words.length;
        for(int i=0;i<n;++i) {
            String word = words[i];
            if(i==0) {
                if(word.charAt(0) != words[n-1].charAt(words[n-1].length()-1)) return false;
            }
            else {
                if(word.charAt(0) != words[i-1].charAt(words[i-1].length()-1)) return false;
            }
        }
        return true;
    }
}

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

给你一个正整数数组 skill ，数组长度为 偶数 n ，其中 skill[i] 表示第 i 个玩家的技能点。将所有玩家分成 n / 2 个 2 人团队，使每一个团队的技能点之和 相等 。
团队的 化学反应 等于团队中玩家的技能点 乘积 。
返回所有团队的 化学反应 之和，如果无法使每个团队的技能点之和相等，则返回 -1 。

排序。
如果最小的不和最大的匹配，那么最大的和一个比最小数更大的数匹配，就会导致技能点之和不相等。
因此最小的一定和最大的匹配。

class Solution {
    public long dividePlayers(int[] skill) {
        int sum_ = 0, n = skill.length;
        for(int s:skill) sum_+=s;
        int group = sum_ * 2 / n;
        Arrays.sort(skill);
        long res = 0;
        int start = 0, end = n-1;
        while(start <= end) {
            if(skill[start] + skill[end] != group) return -1;
            res += skill[start] * skill[end];
            start ++;
            end --;
        }
        return res;
    }
}

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

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

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

DFS.由于路径可以折返，取连通块中的 \(\textit{distance}_i\)最小的那条边，即为答案。

class Solution {
    Set<Integer> visited = new HashSet<>();
    Map<Integer, ArrayList<Integer>> graph = new HashMap<>();

    public int minScore(int n, int[][] roads) {
        for(int[] road:roads) {
            graph.computeIfAbsent(road[0], k -> new ArrayList<Integer>()).add(road[1]);
            graph.computeIfAbsent(road[1], k -> new ArrayList<Integer>()).add(road[0]);
        }
        dfs(1);
        visited.add(1);
        int res = Integer.MAX_VALUE;
        for(int[] road:roads) {
            if(visited.contains(road[0])) res = Math.min(res, road[2]);
        }
        return res;
    }

    public void dfs(int cur) {
        for(int nxt:graph.get(cur)) {
            if(visited.contains(nxt)) continue;
            visited.add(nxt);
            dfs(nxt);
        }
    }
}

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

给你一个正整数 n ，表示一个 无向 图中的节点数目，节点编号从 1 到 n 。
同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 双向 边。注意给定的图可能是不连通的。
请你将图划分为 m 个组（编号从 1 开始），满足以下要求：
图中每个节点都只属于一个组。
图中每条边连接的两个点 [ai, bi] ，如果 ai 属于编号为 x 的组，bi 属于编号为 y 的组，那么 |y - x| = 1 。
请你返回最多可以将节点分为多少个组（也就是最大的 m ）。如果没办法在给定条件下分组，请你返回 -1 。

class Solution {
    private List<Integer>[] g;
    private final List<Integer> nodes = new ArrayList<>();
    private int[] time, color; // time 充当 vis 数组的作用（避免在 BFS 内部重复创建 vis 数组）
    private int clock;

    public int magnificentSets(int n, int[][] edges) {
        g = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for (var e : edges) {
            int x = e[0] - 1, y = e[1] - 1;
            g[x].add(y);
            g[y].add(x);
        }

        time = new int[n];
        color = new int[n];
        var ans = 0;
        for (var i = 0; i < n; i++) {
            if (color[i] != 0) continue;
            nodes.clear();
            if (!isBipartite(i, 1)) return -1; // 如果不是二分图（有奇环），则无法分组
            // 否则一定可以分组
            var maxDepth = 0;
            for (var x : nodes) // 枚举连通块的每个点，作为起点 BFS，求最大深度
                maxDepth = Math.max(maxDepth, bfs(x));
            ans += maxDepth;
        }
        return ans;
    }

    // 二分图判定
    private boolean isBipartite(int x, int c) {
        nodes.add(x);
        color[x] = c;
        for (var y : g[x])
            if (color[y] == c || color[y] == 0 && !isBipartite(y, -c))
                return false;
        return true;
    }

    // 返回从 start 出发的最大深度
    private int bfs(int start) {
        var depth = 0;
        time[start] = ++clock;
        var q = new ArrayList<Integer>();
        q.add(start);
        while (!q.isEmpty()) {
            var tmp = q;
            q = new ArrayList<>();
            for (var x : tmp)
                for (var y : g[x])
                    if (time[y] != clock) { // 没有在同一次 BFS 中访问过
                        time[y] = clock;
                        q.add(y);
                    }
            ++depth;
        }
        return depth;
    }
}

参考：LeetCode