【题解】—— LeetCode一周小结29

🌟欢迎来到 我的博客 —— 探索技术的无限可能！

🌟博客的简介（文章目录）

【题解】—— 每日一道题目栏

上接：【题解】—— LeetCode一周小结28

15.账户合并

题目链接：721. 账户合并

给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是名称 (name)，其余元素是 emails 表示该账户的邮箱地址。

现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。

合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是按字符 ASCII 顺序排列的邮箱地址。账户本身可以以任意顺序返回。

示例 1：

输入：accounts = [[“John”, “johnsmith@mail.com”, “john00@mail.com”],
[“John”, “johnnybravo@mail.com”], [“John”, “johnsmith@mail.com”,
“john_newyork@mail.com”], [“Mary”, “mary@mail.com”]]

输出：[[“John”, ‘john00@mail.com’, ‘john_newyork@mail.com’,
‘johnsmith@mail.com’], [“John”, “johnnybravo@mail.com”], [“Mary”,
“mary@mail.com”]]

解释：

第一个和第三个 John 是同一个人，因为他们有共同的邮箱地址 “johnsmith@mail.com”。

第二个 John 和 Mary 是不同的人，因为他们的邮箱地址没有被其他帐户使用。

可以以任何顺序返回这些列表，例如答案
[[‘Mary’，‘mary@mail.com’]，[‘John’，‘johnnybravo@mail.com’]，
[‘John’，‘john00@mail.com’，‘john_newyork@mail.com’，‘johnsmith@mail.com’]]
也是正确的。

示例 2：

输入：accounts =
[[“Gabe”,“Gabe0@m.co”,“Gabe3@m.co”,“Gabe1@m.co”],[“Kevin”,“Kevin3@m.co”,“Kevin5@m.co”,“Kevin0@m.co”],[“Ethan”,“Ethan5@m.co”,“Ethan4@m.co”,“Ethan0@m.co”],[“Hanzo”,“Hanzo3@m.co”,“Hanzo1@m.co”,“Hanzo0@m.co”],[“Fern”,“Fern5@m.co”,“Fern1@m.co”,“Fern0@m.co”]]

输出：[[“Ethan”,“Ethan0@m.co”,“Ethan4@m.co”,“Ethan5@m.co”],
[“Gabe”,“Gabe0@m.co”,“Gabe1@m.co”,“Gabe3@m.co”],
[“Hanzo”,“Hanzo0@m.co”,“Hanzo1@m.co”,“Hanzo3@m.co”],
[“Kevin”,“Kevin0@m.co”,“Kevin3@m.co”,“Kevin5@m.co”],
[“Fern”,“Fern0@m.co”,“Fern1@m.co”,“Fern5@m.co”]]

提示：

1 <= accounts.length <= 1000

2 <= accounts[i].length <= 10

1 <= accounts[i][j].length <= 30

accounts[i][0] 由英文字母组成

accounts[i][j] (for j > 0) 是有效的邮箱地址

题解：
方法：并查集 + 哈希表

class UnionFind {
    private final int[] p;
    private final int[] size;

    public UnionFind(int n) {
        p = new int[n];
        size = new int[n];
        for (int i = 0; i < n; ++i) {
            p[i] = i;
            size[i] = 1;
        }
    }

    public int find(int x) {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }

    public boolean union(int a, int b) {
        int pa = find(a), pb = find(b);
        if (pa == pb) {
            return false;
        }
        if (size[pa] > size[pb]) {
            p[pb] = pa;
            size[pa] += size[pb];
        } else {
            p[pa] = pb;
            size[pb] += size[pa];
        }
        return true;
    }
}

class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        int n = accounts.size();
        UnionFind uf = new UnionFind(n);
        Map<String, Integer> d = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            for (int j = 1; j < accounts.get(i).size(); ++j) {
                String email = accounts.get(i).get(j);
                if (d.containsKey(email)) {
                    uf.union(i, d.get(email));
                } else {
                    d.put(email, i);
                }
            }
        }
        Map<Integer, Set<String>> g = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            int root = uf.find(i);
            g.computeIfAbsent(root, k -> new HashSet<>()).addAll(accounts.get(i).subList(1, accounts.get(i).size()));
        }
        List<List<String>> ans = new ArrayList<>();
        for (var e : g.entrySet()) {
            List<String> emails = new ArrayList<>(e.getValue());
            Collections.sort(emails);
            ans.add(new ArrayList<>());
            ans.get(ans.size() - 1).add(accounts.get(e.getKey()).get(0));
            ans.get(ans.size() - 1).addAll(emails);
        }
        return ans;
    }
}

16.找到两个数组中的公共元素

题目链接：2956. 找到两个数组中的公共元素

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，它们分别含有 n 和 m 个元素。请你计算以下两个数值：

answer1：使得 nums1[i] 在 nums2 中出现的下标 i 的数量。
answer2：使得 nums2[i] 在 nums1 中出现的下标 i 的数量。
返回 [answer1, answer2]。

示例 1：

输入：nums1 = [2,3,2], nums2 = [1,2]

输出：[2,1]

解释：

示例 2：

输

入：nums1 = [4,3,2,3,1], nums2 = [2,2,5,2,3,6]

输出：[3,4]

解释：

nums1 中下标在 1，2，3 的元素在 nums2 中也存在。所以 answer1 为 3。

nums2 中下标在 0，1，3，4 的元素在 nums1 中也存在。所以 answer2 为 4。

示例 3：

输入：nums1 = [3,4,2,3], nums2 = [1,5]

输出：[0,0]

解释：

nums1 和 nums2 中没有相同的数字，所以答案是 [0,0]。

提示：

n == nums1.length

m == nums2.length

1 <= n, m <= 100

1 <= nums1[i], nums2[i] <= 100

题解：
方法：线性

class Solution {
    public int[] findIntersectionValues(int[] nums1, int[] nums2) {
        HashSet<Integer> set1 = new HashSet<>();
        for (int x : nums1) {
            set1.add(x);
        }
        HashSet<Integer> set2 = new HashSet<>();
        for (int x : nums2) {
            set2.add(x);
        }

        int[] ans = new int[2];
        for (int x : nums1) {
            if (set2.contains(x)) {
                ans[0]++;
            }
        }
        for (int x : nums2) {
            if (set1.contains(x)) {
                ans[1]++;
            }
        }
        return ans;
    }
}

17.关闭分部的可行集合数目

题目链接：2959. 关闭分部的可行集合数目

一个公司在全国有 n 个分部，它们之间有的有道路连接。一开始，所有分部通过这些道路两两之间互相可以到达。

公司意识到在分部之间旅行花费了太多时间，所以它们决定关闭一些分部（也可能不关闭任何分部），同时保证剩下的分部之间两两互相可以到达且最远距离不超过 maxDistance 。

两个分部之间的距离是通过道路长度之和的最小值。

给你整数 n ，maxDistance 和下标从 0 开始的二维整数数组 roads ，其中 roads[i] = [ui, vi, wi] 表示一条从 ui 到 vi 长度为 wi的无向道路。

请你返回关闭分部的可行方案数目，满足每个方案里剩余分部之间的最远距离不超过 maxDistance。

注意，关闭一个分部后，与之相连的所有道路不可通行。

注意，两个分部之间可能会有多条道路。

示例 1：
在这里插入图片描述

输入：n = 3, maxDistance = 5, roads = [[0,1,2],[1,2,10],[0,2,10]]

输出：5

解释：可行的关闭分部方案有：

关闭分部集合 [2] ，剩余分部为 [0,1] ，它们之间的距离为 2 。
关闭分部集合 [0,1] ，剩余分部为 [2] 。
关闭分部集合 [1,2] ，剩余分部为 [0] 。
关闭分部集合 [0,2] ，剩余分部为 [1] 。
关闭分部集合 [0,1,2] ，关闭后没有剩余分部。
总共有 5 种可行的关闭方案。

示例 2：

在这里插入图片描述

输入：n = 3, maxDistance = 5, roads = [[0,1,20],[0,1,10],[1,2,2],[0,2,2]]

输出：7

解释：可行的关闭分部方案有：

关闭分部集合 [] ，剩余分部为 [0,1,2] ，它们之间的最远距离为 4 。
关闭分部集合 [0] ，剩余分部为 [1,2] ，它们之间的距离为 2 。
关闭分部集合 [1] ，剩余分部为 [0,2] ，它们之间的距离为 2 。
关闭分部集合 [0,1] ，剩余分部为 [2] 。
关闭分部集合 [1,2] ，剩余分部为 [0] 。
关闭分部集合 [0,2] ，剩余分部为 [1] 。
关闭分部集合 [0,1,2] ，关闭后没有剩余分部。

总共有 7 种可行的关闭方案。

示例 3：

输入：n = 1, maxDistance = 10, roads = []

输出：2

解释：可行的关闭分部方案有：

关闭分部集合 [] ，剩余分部为 [0] 。
关闭分部集合 [0] ，关闭后没有剩余分部。

总共有 2 种可行的关闭方案。

提示：

1 <= n <= 10

1 <= maxDistance <= 105

0 <= roads.length <= 1000

roads[i].length == 3

0 <= ui, vi <= n - 1

ui != vi

1 <= wi <= 1000

一开始所有分部之间通过道路互相可以到达。

题解：
方法：二进制枚举 + Floyd 算法

class Solution {
    public int numberOfSets(int n, int maxDistance, int[][] roads) {
        int ans = 0;
        for (int mask = 0; mask < 1 << n; ++mask) {
            int[][] g = new int[n][n];
            for (var e : g) {
                Arrays.fill(e, 1 << 29);
            }
            for (var e : roads) {
                int u = e[0], v = e[1], w = e[2];
                if ((mask >> u & 1) == 1 && (mask >> v & 1) == 1) {
                    g[u][v] = Math.min(g[u][v], w);
                    g[v][u] = Math.min(g[v][u], w);
                }
            }
            for (int k = 0; k < n; ++k) {
                if ((mask >> k & 1) == 1) {
                    g[k][k] = 0;
                    for (int i = 0; i < n; ++i) {
                        for (int j = 0; j < n; ++j) {
                            g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
                        }
                    }
                }
            }
            int ok = 1;
            for (int i = 0; i < n && ok == 1; ++i) {
                for (int j = 0; j < n && ok == 1; ++j) {
                    if ((mask >> i & 1) == 1 && (mask >> j & 1) == 1) {
                        if (g[i][j] > maxDistance) {
                            ok = 0;
                        }
                    }
                }
            }
            ans += ok;
        }
        return ans;
    }
}

18.访问消失节点的最少时间

题目链接：3112. 访问消失节点的最少时间

给你一个二维数组 edges 表示一个 n 个点的无向图，其中 edges[i] = [ui, vi, lengthi] 表示节点 ui 和节点 vi 之间有一条需要 lengthi 单位时间通过的无向边。

同时给你一个数组 disappear ，其中 disappear[i] 表示节点 i 从图中消失的时间点，在那一刻及以后，你无法再访问这个节点。

注意，图有可能一开始是不连通的，两个节点之间也可能有多条边。

请你返回数组 answer ，answer[i] 表示从节点 0 到节点 i 需要的最少单位时间。如果从节点 0 出发无法到达节点 i ，那么 answer[i] 为 -1 。

示例 1：
在这里插入图片描述

输入：n = 3, edges = [[0,1,2],[1,2,1],[0,2,4]], disappear = [1,1,5]

输出：[0,-1,4]

解释：

我们从节点 0 出发，目的是用最少的时间在其他节点消失之前到达它们。

对于节点 0 ，我们不需要任何时间，因为它就是我们的起点。

对于节点 1 ，我们需要至少 2 单位时间，通过 edges[0] 到达。但当我们到达的时候，它已经消失了，所以我们无法到达它。

对于节点 2 ，我们需要至少 4 单位时间，通过 edges[2] 到达。

示例 2：

在这里插入图片描述

输入：n = 3, edges = [[0,1,2],[1,2,1],[0,2,4]], disappear = [1,3,5]

输出：[0,2,3]

解释：

我们从节点 0 出发，目的是用最少的时间在其他节点消失之前到达它们。

对于节点 0 ，我们不需要任何时间，因为它就是我们的起点。

对于节点 1 ，我们需要至少 2 单位时间，通过 edges[0] 到达。

对于节点 2 ，我们需要至少 3 单位时间，通过 edges[0] 和 edges[1] 到达。

示例 3：

输入：n = 2, edges = [[0,1,1]], disappear = [1,1]

输出：[0,-1]

解释：

当我们到达节点 1 的时候，它恰好消失，所以我们无法到达节点 1 。

提示：

1 <= n <= 5 * 104

0 <= edges.length <= 105

edges[i] == [ui, vi, lengthi]

0 <= ui, vi <= n - 1

1 <= lengthi <= 105

disappear.length == n

1 <= disappear[i] <= 105

题解：
方法：Dijkstra

class Solution {
    public int[] minimumTime(int n, int[][] edges, int[] disappear) {
        List<int[]>[] g = new ArrayList[n]; // 稀疏图用邻接表
        Arrays.setAll(g, i -> new ArrayList<>());
        for (int[] e : edges) {
            int x = e[0];
            int y = e[1];
            int wt = e[2];
            g[x].add(new int[]{y, wt});
            g[y].add(new int[]{x, wt});
        }

        int[] dis = new int[n];
        Arrays.fill(dis, -1);
        dis[0] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
        pq.offer(new int[]{0, 0});
        while (!pq.isEmpty()) {
            int[] p = pq.poll();
            int dx = p[0];
            int x = p[1];
            if (dx > dis[x]) { // x 之前出堆过
                continue;
            }
            for (int[] e : g[x]) {
                int y = e[0];
                int newDis = dx + e[1];
                if (newDis < disappear[y] && (dis[y] < 0 || newDis < dis[y])) {
                    dis[y] = newDis; // 更新 x 的邻居的最短路
                    pq.offer(new int[]{newDis, y});
                }
            }
        }
        return dis;
    }
}

19.得到更多分数的最少关卡数目

题目链接：3096. 得到更多分数的最少关卡数目

给你一个长度为 n 的二进制数组 possible 。

Alice 和 Bob 正在玩一个有 n 个关卡的游戏，游戏中有一些关卡是困难模式，其他的关卡是简单模式。如果 possible[i] == 0 ，那么第 i 个关卡是困难模式。一个玩家通过一个简单模式的关卡可以获得 1 分，通过困难模式的关卡将失去 1 分。

游戏的一开始，Alice 将从第 0 级开始按顺序完成一些关卡，然后 Bob 会完成剩下的所有关卡。

假设两名玩家都采取最优策略，目的是最大化自己的得分，Alice 想知道自己最少需要完成多少个关卡，才能获得比 Bob 更多的分数。

请你返回 Alice 获得比 Bob 更多的分数所需要完成的最少关卡数目，如果无法达成，那么返回 -1 。

注意，每个玩家都至少需要完成 1 个关卡。

示例 1：

示例 2：

输入：possible = [1,1,1,1,1]

输出：3

解释：

我们来看一下 Alice 可以完成的关卡数目：

如果 Alice 只完成关卡 0 ，Bob 完成剩下的所有关卡，那么 Alice 获得 1 分，Bob 获得 4 分。

如果 Alice 完成到关卡 1 ，Bob 完成剩下的所有关卡，那么 Alice 获得 2 分，Bob 获得 3 分。

如果 Alice 完成到关卡 2 ，Bob 完成剩下的所有关卡，那么 Alice 获得 3 分，Bob 获得 2 分。

如果 Alice 完成到关卡 3 ，Bob 完成剩下的所有关卡，那么 Alice 获得 4 分，Bob 获得 1 分。

Alice 需要完成至少三个关卡获得更多的分数。

示例 3：

输入：possible = [0,0]

输出：-1

解释：

两名玩家只能各完成 1 个关卡，Alice 完成关卡 0 得到 -1 分，Bob 完成关卡 1 得到 -1 分。两名玩家得分相同，所以
Alice 无法得到更多分数。

提示：

2 <= n == possible.length <= 105

possible[i] 要么是 0 要么是 1 。

题解：
方法：枚举

class Solution {
    public int minimumLevels(int[] possible) {
        int s = 0;
        for (int x : possible) {
            s += x == 0 ? -1 : 1;
        }
        int t = 0;
        for (int i = 1; i < possible.length; ++i) {
            t += possible[i - 1] == 0 ? -1 : 1;
            if (t > s - t) {
                return i;
            }
        }
        return -1;
    }
}

20. 将石头分散到网格图的最少移动次数

题目链接：2850. 将石头分散到网格图的最少移动次数

给你一个大小为 3 * 3 ，下标从 0 开始的二维整数矩阵 grid ，分别表示每一个格子里石头的数目。网格图中总共恰好有 9 个石头，一个格子里可能会有多个石头。

每一次操作中，你可以将一个石头从它当前所在格子移动到一个至少有一条公共边的相邻格子。

请你返回每个格子恰好有一个石头的最少移动次数。

示例 1：

在这里插入图片描述

输入：grid = [[1,1,0],[1,1,1],[1,2,1]]

输出：3

解释：让每个格子都有一个石头的一个操作序列为：

1 - 将一个石头从格子 (2,1) 移动到 (2,2) 。

2 - 将一个石头从格子 (2,2) 移动到 (1,2) 。

3 - 将一个石头从格子 (1,2) 移动到 (0,2) 。

总共需要 3 次操作让每个格子都有一个石头。

让每个格子都有一个石头的最少操作次数为 3 。

示例 2：

在这里插入图片描述

输入：grid = [[1,3,0],[1,0,0],[1,0,3]]

输出：4

解释：让每个格子都有一个石头的一个操作序列为：

1 - 将一个石头从格子 (0,1) 移动到 (0,2) 。

2 - 将一个石头从格子 (0,1) 移动到 (1,1) 。

3 - 将一个石头从格子 (2,2) 移动到 (1,2) 。

4 - 将一个石头从格子 (2,2) 移动到 (2,1) 。

总共需要 4 次操作让每个格子都有一个石头。

让每个格子都有一个石头的最少操作次数为 4 。

提示：

grid.length == grid[i].length == 3

0 <= grid[i][j] <= 9

grid 中元素之和为 9 。

题解：
方法：枚举

class Solution {
    public int minimumMoves(int[][] grid) {
        List<int[]> from = new ArrayList<>();
        List<int[]> to = new ArrayList<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] > 1) {
                    for (int k = 1; k < grid[i][j]; k++) {
                        from.add(new int[]{i, j});
                    }
                } else if (grid[i][j] == 0) {
                    to.add(new int[]{i, j});
                }
            }
        }

        int ans = Integer.MAX_VALUE;
        for (List<int[]> from2 : permutations(from)) {
            int total = 0;
            for (int i = 0; i < from2.size(); i++) {
                int[] f = from2.get(i);
                int[] t = to.get(i);
                total += Math.abs(f[0] - t[0]) + Math.abs(f[1] - t[1]);
            }
            ans = Math.min(ans, total);
        }
        return ans;
    }

    private List<List<int[]>> permutations(List<int[]> arr) {
        List<List<int[]>> result = new ArrayList<>();
        permute(arr, 0, result);
        return result;
    }

    private void permute(List<int[]> arr, int start, List<List<int[]>> result) {
        if (start == arr.size()) {
            result.add(new ArrayList<>(arr));
        }
        for (int i = start; i < arr.size(); i++) {
            swap(arr, start, i);
            permute(arr, start + 1, result);
            swap(arr, start, i);
        }
    }

    private void swap(List<int[]> arr, int i, int j) {
        int[] temp = arr.get(i);
        arr.set(i, arr.get(j));
        arr.set(j, temp);
    }
}

21. 删除一次得到子数组最大和

题目链接：1186. 删除一次得到子数组最大和

给你一个整数数组，返回它的某个非空子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。

注意，删除一个元素后，子数组不能为空。

示例 1：

输入：arr = [1,-2,0,3]

输出：4

解释：我们可以选出 [1, -2, 0, 3]，然后删掉 -2，这样得到 [1, 0, 3]，和最大。

示例 2：

输入：arr = [1,-2,-2,3]

输出：3

解释：我们直接选出 [3]，这就是最大和。

示例 3：

输入：arr = [-1,-1,-1,-1]

输出：-1

解释：最后得到的子数组不能为空，所以我们不能选择 [-1] 并从中删去 -1 来得到 0。
 我们应该直接选择 [-1]，或者选择 [-1, -1] 再从中删去一个 -1。

提示：

1 <= arr.length <= 105

-104 <= arr[i] <= 104

题解：
方法：记忆化搜索

class Solution {
    private int[] arr;
    private int[][] memo;

    public int maximumSum(int[] arr) {
        this.arr = arr;
        int n = arr.length;
        int ans = Integer.MIN_VALUE;
        memo = new int[n][2];
        for (int[] row : memo)
            Arrays.fill(row, Integer.MIN_VALUE);
        for (int i = 0; i < n; i++)
            ans = Math.max(ans, Math.max(dfs(i, 0), dfs(i, 1)));
        return ans;
    }

    private int dfs(int i, int j) {
        if (i < 0) return Integer.MIN_VALUE / 2; // 除 2 防止负数相加溢出
        if (memo[i][j] != Integer.MIN_VALUE) return memo[i][j]; // 之前计算过
        if (j == 0) return memo[i][j] = Math.max(dfs(i - 1, 0), 0) + arr[i];
        return memo[i][j] = Math.max(dfs(i - 1, 1) + arr[i], dfs(i - 1, 0));
    }
}