写点什么

LeetCode 第 46 场双周赛题解

发布于: 2021 年 02 月 21 日
LeetCode 第 46 场双周赛题解

t1:5668. 最长的美好子字符串(简单)


当一个字符串 s 包含的每一种字母的大写和小写形式 同时 出现在 s 中,就称这个字符串 s 是 美好 字符串。


比方说,"abABB" 是美好字符串,因为 'A' 和 'a' 同时出现了,且 'B' 和 'b' 也同时出现了。


然而,"abA" 不是美好字符串因为 'b' 出现了,而 'B' 没有出现。


给你一个字符串 s ,请你返回 s 最长的 美好子字符串 。


如果有多个答案,请你返回 最早 出现的一个。如果不存在美好子字符串,请你返回一个空字符串。


示例 1:

输入:s = "YazaAay"输出:"aAa"解释:"aAa" 是一个美好字符串,因为这个子串中仅含一种字母,其小写形式 'a' 和大写形式 'A' 也同时出现了。"aAa" 是最长的美好子字符串。
复制代码

示例 2:

输入:s = "Bb"输出:"Bb"解释:"Bb" 是美好字符串,因为 'B' 和 'b' 都出现了。整个字符串也是原字符串的子字符串。
复制代码

示例 3:

输入:s = "c"输出:""解释:没有美好子字符串。
复制代码

示例 4:

输入:s = "dDzeE"输出:"dD"解释:"dD" 和 "eE" 都是最长美好子字符串。由于有多个美好子字符串,返回 "dD" ,因为它出现得最早。
复制代码


提示:

  • 1 <= s.length <= 100

  • s 只包含大写和小写英文字母。




朴素解法


由于数据范围只有 100,因此怎么做都可以。


对于这种数据范围的题,大家尽量选择 简单的、出错率低 的做法。


一个直观的做法是,枚举每个子串的「起点」和「终点」,检查子串中的每个字符,是否在子串同时包含小写字母和大写字母。


class Solution {    public String longestNiceSubstring(String s) {        int n = s.length();        String ans = "";        for (int i = 0; i < n; i++) {            out:for (int j = i + 1; j < n; j++) {                String sub = s.substring(i, j + 1);                if (sub.length() > ans.length()) {                    for (char c : sub.toCharArray()) {                        char lo = Character.toLowerCase(c), up = Character.toUpperCase(c);                        if (sub.indexOf(lo) < 0 || sub.indexOf(up) < 0) continue out;                    }                      ans = sub;                }            }        }        return ans;    }}
复制代码
  • 时间复杂度:$O(n^3)$

  • 空间复杂度:$O(1)$


t2:5669. 通过连接另一个数组的子数组得到一个数组(中等)


给你一个长度为 n 的二维整数数组 groups ,同时给你一个整数数组 nums 。


你是否可以从 nums 中选出 n 个 不相交 的子数组,使得第 i 个子数组与 groups[i] (下标从 0 开始)完全相同,且如果 i > 0 ,那么第 (i-1) 个子数组在 nums 中出现的位置在第 i 个子数组前面。(也就是说,这些子数组在 nums 中出现的顺序需要与 groups 顺序相同)


如果你可以找出这样的 n 个子数组,请你返回 true ,否则返回 false 。


如果不存在下标为 k 的元素 nums[k] 属于不止一个子数组,就称这些子数组是 不相交 的。子数组指的是原数组中连续元素组成的一个序列。


示例 1:

输入:groups = [[1,-1,-1],[3,-2,0]],      nums = [1,-1,0,1,-1,-1,3,-2,0]输出:true解释:你可以分别在 nums 中选出第 0 个子数组 [1,-1,0,1,-1,-1,3,-2,0] 和第 1 个子数组 [1,-1,0,1,-1,-1,3,-2,0] 。这两个子数组是不相交的,因为它们没有任何共同的元素。
复制代码

示例 2:

输入:groups = [[10,-2],[1,2,3,4]],      nums = [1,2,3,4,10,-2]输出:false解释:选择子数组 [1,2,3,4,10,-2] 和 [1,2,3,4,10,-2] 是不正确的因为它们出现的顺序与 groups 中顺序不同。[10,-2] 必须出现在 [1,2,3,4] 之前。
复制代码

示例 3:

输入:groups = [[1,2,3],[3,4]],      nums = [7,7,1,2,3,4,7,7]输出:false解释:选择子数组 [7,7,1,2,3,4,7,7] 和 [7,7,1,2,3,4,7,7] 是不正确因为它们不是不相交子数组。它们有一个共同的元素 nums[4] (下标从 0 开始)。
复制代码


提示:


  • groups.length == n

  • 1 <= n <= $10^3$

  • 1 <= groups[i].length, sum(groups[i].length) <= $10^3$

  • 1 <= nums.length <= $10^3$

  • $-10^7$ <= groups[i][j], nums[k] <= $10^7$




朴素解法


本质上是道模拟题。


使用 i 指针代表 nums 当前枚举到的位置;j 代表 groups 中枚举到哪个数组。


cnt 代表匹配的数组个数。


  • i 开头的连续一段和 groups[j] 匹配:j 指针右移一位(代表匹配下一个数组),i 指针右移 groups[j].length 长度。

  • i 开头的连续一段和 groups[j] 不匹配:i 右移一位。


代码:

class Solution {    public boolean canChoose(int[][] gs, int[] nums) {        int n = nums.length, m = gs.length;        int cnt = 0;        for (int i = 0, j = 0; i < n && j < m;) {            if (check(gs[j], nums, i)) {                i += gs[j++].length;                cnt++;            } else {                i++;            }        }        return cnt == m;    }    boolean check(int[] g, int[] nums, int i) {        int j = 0;        for (;j < g.length && i < nums.length; j++, i++) {            if (g[j] != nums[i]) return false;        }        return j == g.length;    }}
复制代码
  • 时间复杂度:$O(n * m)$

  • 空间复杂度:$O(1)$


t3:5671. 地图中的最高点(中等)


给你一个大小为 m x n 的整数矩阵 isWater,它代表了一个由陆地和*水域*单元格组成的地图。


  • 如果 isWater[i][j] == 0,格子 (i, j) 是一个陆地格子。

  • 如果 isWater[i][j] == 1,格子 (i, j) 是一个水域格子。


你需要按照如下规则给每个单元格安排高度:


  • 每个格子的高度都必须是非负的。

  • 如果一个格子是是 水域 ,那么它的高度必须为 0 。

  • 任意相邻的格子高度差 至多 为 1 。当两个格子在正东、南、西、北方向上相互紧挨着,就称它们为相邻的格子。(也就是说它们有一条公共边)

  • 找到一种安排高度的方案,使得矩阵中的最高高度值 最大 。


请你返回一个大小为 m x n 的整数矩阵 height ,其中 height[i][j] 是格子 (i, j) 的高度。如果有多种解法,请返回 任意一个 。


示例 1:


输入:isWater = [[0,1],[0,0]]输出:[[1,0],[2,1]]解释:上图展示了给各个格子安排的高度。蓝色格子是水域格,绿色格子是陆地格。
复制代码

示例 2:


输入:isWater = [[0,0,1],[1,0,0],[0,0,0]]输出:[[1,1,0],[0,1,1],[1,2,2]]解释:所有安排方案中,最高可行高度为 2 。任意安排方案中,只要最高高度为 2 且符合上述规则的,都为可行方案。
复制代码


提示:


  • m == isWater.length

  • n == isWater[i].length

  • 1 <= m, n <= 1000

  • isWater[i][j] 要么是 0 ,要么是 1 。

  • 至少有 1 个水域格子。



多源 BFS 解法(Flood Fill)


假设只有一个「水域」的话,我们会如何求解?


显然,「水域」所在的位置是 0,而从「水域」出发一步可达的位置是 11 位置一步可达的位置 2 ...


这是一个 BFS 的过程。


当只有一个水域时,是个「单源 BFS」问题。


而本题有多个水域,相应的我们可以使用「多源 BFS」解决。


「多源 BFS」和「单源 BFS」本质上其实并无区别,都遵循以下步骤:


1. 将「起点」进行入队

2. 弹出队列中的元素,将从「弹出元素」出发一步可达(并符合条件)的节点,加入队列

3. 重复步骤 2,直到队列为空(代表没有节点需要更新)


值得注意的是,在我们熟悉的「单源 BFS」中,通常我们会建一个 boolean 数组来记录哪些点已经入过队列。


但其实我们本质上不是为了记录哪些点入过队列,而是为了记录哪些节点不再需要被更新。


对于「单源 BFS」而言,每个节点只会被更新一次,不会遇到需要被多次更新的情况。


因此每个节点入队一次之后我们就使用 boolean 数组来标记「不再需要被更新」。


而对于本题(多源 BFS)而言,一个节点是需要被多次更新的。


为了方便理解,我们可以将整个过程拆开来看,以上面的 「示例 2」 为例子:


  1. 先忽略水域 2 ,使用水域 1 作为起点更新整个区域(这时候得到的答案是满足水域 1 而不满足水域 2 的)

  2. 然后再以水域 2 为起点更新区域,对于那些高度与水域 2 冲突的值,使用满足条件的值对其进行覆盖(用更小的值去更新冲突的区域)

  3. 所有的水域作为起点更新完之后,最终得到的就是满足所有水域条件的答案


为了方便,使用 * 代表水域
起始状态 1 更新 2 更新[0,0,*] [1,2,*] [1,1,0][*,0,0] => [0,1,2] => [0,1,1][0,0,0] [1,2,3] [1,2,2]
复制代码


可见,这时候我们不能与「单源 BFS」一样,以「是否入过队列」作为「是否需要更新」的标准,一个节点是否需要被更新应该「取决于当前高度是否过高(会造成冲突)」。


所以完整的流程应该是:


  1. 将所有的「起点」,也就是水域进行入队

  2. 弹出队列中的元素,判断「弹出元素」的相邻元素的高度是否需要被更新,如果相邻元素需要被更新,则将相邻元素进行入队

  3. 重复步骤 2,直到队列为空(代表没有节点需要更新)


代码:

class Solution {    public int[][] highestPeak(int[][] wa) {        int m = wa.length, n = wa[0].length;        int[][] ans = new int[m][n];        Deque<int[]> d = new ArrayDeque<>();        for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                                if (wa[i][j] == 1) {                    ans[i][j] = 0;                    d.addLast(new int[]{i, j});                } else {                    ans[i][j] = Integer.MAX_VALUE;                }            }        }        int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};        while (!d.isEmpty()) {            int[] cur = d.pollFirst();            for (int[] dir : dirs) {                int x = cur[0], y = cur[1];                int nx = x + dir[0], ny = y + dir[1];                if (nx >= 0 && nx < m && ny >= 0 && ny < n && wa[nx][ny] != 1) {                    // 当该节点需要被更新时(高度过高),可能会导致其相邻节点也需要被更新                    // 因此将此节点入队                    if (ans[nx][ny] > ans[x][y] + 1) {                        ans[nx][ny] = ans[x][y] + 1;                        d.addLast(new int[]{nx, ny});                    }                 }            }        }        return ans;    }}
复制代码
  • 时间复杂度:节点的总数量为 n,水域节点的数量为 m。每个节点入队的次数与水域数量有关。复杂度为 $O(n * m)$

  • 空间复杂度:$O(n)$


t4:5670. 互质树(困难)


给你一个 n 个节点的树(也就是一个无环连通无向图),节点编号从 0 到 n - 1 ,且恰好有 n - 1 条边,每个节点有一个值。树的 根节点 为 0 号点。


给你一个整数数组 nums 和一个二维数组 edges 来表示这棵树。nums[i] 表示第 i 个点的值,edges[j] = [uj, vj] 表示节点 uj 和节点 vj 在树中有一条边。


当 gcd(x, y) == 1 ,我们称两个数 x 和 y 是 互质的 ,其中 gcd(x, y) 是 x 和 y 的 最大公约数 。


从节点 i 到 根 最短路径上的点都是节点 i 的祖先节点。一个节点 不是 它自己的祖先节点。


请你返回一个大小为 n 的数组 ans ,其中 ans[i]是离节点 i 最近的祖先节点且满足 nums[i] 和 nums[ans[i]] 是 互质的 ,如果不存在这样的祖先节点,ans[i] 为 -1 。


示例 1:


输入:nums = [2,3,3,2],      edges = [[0,1],[1,2],[1,3]]输出:[-1,0,0,1]解释:上图中,每个节点的值在括号中表示。- 节点 0 没有互质祖先。- 节点 1 只有一个祖先节点 0 。它们的值是互质的(gcd(2,3) == 1)。- 节点 2 有两个祖先节点,分别是节点 1 和节点 0 。节点 1 的值与它的值不是互质的(gcd(3,3) == 3)但节点 0 的值是互质的(gcd(2,3) == 1),所以节点 0 是最近的符合要求的祖先节点。- 节点 3 有两个祖先节点,分别是节点 1 和节点 0 。它与节点 1 互质(gcd(3,2) == 1),所以节点 1 是离它最近的符合要求的祖先节点。
复制代码


示例 2:



输入:nums = [5,6,10,2,3,6,15],      edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]输出:[-1,0,-1,0,0,0,-1]
复制代码


提示:


  • nums.length == n

  • 1 <= nums[i] <= 50

  • 1 <= n <= $10^5$

  • edges.length == n - 1

  • edges[j].length == 2

  • 0 <= uj, vj < n

  • uj != vj




基本思路


题目描述很长,但其实就是说每个节点从下往上找,找到最近的「与其互质」的节点。


数据范围是 $10^5$,如果每个节点都直接往上找最近「互质」祖宗节点的话,当树为线性时,复杂度是 $O(n^2)$ ,会超时。


因此我们要利用 nums[i] 范围只有 50 的特性。


我们可以先预处理除 [1, 50] 范围内的每个数,求出他们互质的数有哪些,存到一个字典里。


那么对于某个节点而言,假设节点的值为 x ,所在层数为 y


那么问题转化为求与 x 互质的数有哪些,最近的在哪一层。


dep[x] 表示距离值为 x 的节点最近的层是多少;pos[x] 代表具体的节点编号。




DFS 解法


代码:


class Solution {    int[] ans;    Map<Integer, List<Integer>> map = new HashMap<>(); // 边映射    Map<Integer, List<Integer>> val = new HashMap<>(); // 互质数字典    int[] dep;    int[] pos = new int[52];    public int[] getCoprimes(int[] nums, int[][] edges) {        int n = nums.length;        ans = new int[n];        dep = new int[n];        Arrays.fill(ans, - 1);        Arrays.fill(pos, -1);
for (int[] edge : edges) { int a = edge[0], b = edge[1]; List<Integer> alist = map.getOrDefault(a, new ArrayList<>()); alist.add(b); map.put(a, alist); List<Integer> blist = map.getOrDefault(b, new ArrayList<>()); blist.add(a); map.put(b, blist); }
for (int i = 1; i <= 50; i++) { for (int j = 1; j <= 50; j++) { if (gcd(i, j) == 1) { List<Integer> list = val.getOrDefault(i, new ArrayList<>()); list.add(j); val.put(i, list); } } }
dfs(nums, 0, -1); return ans; } void dfs(int[] nums, int u, int form) { int t = nums[u]; for (int v : val.get(t)) { if (pos[v] == -1) continue; if (ans[u] == -1 || dep[ans[u]] < dep[pos[v]]) ans[u] = pos[v]; } int p = pos[t]; pos[t] = u;
for (int i : map.get(u)) { if (i == form) continue; dep[i] = dep[u] + 1; dfs(nums, i, u); } pos[t] = p; } int gcd(int a, int b) { if (b == 0) return a; if (a == 0) return b; return gcd(b, a % b); }}
复制代码
  • 时间复杂度:对于每个节点而言,会检查与其数值互质的数有哪些,在哪层。最坏情况下会检查 50 个互质数(当前数值为 1)。复杂度为 $O(n)$

  • 空间复杂度:$O(n)$

最后


这是 2021/02/21 的 LeetCode 第 46 场双周赛的比赛题解。


除了前两道模拟题以外,这次周赛与「搜索」相关的题比较多。


t3 是一道「多源 BFS」裸题,t4 是一道脑筋急转弯的 DFS 搜索题。


发布于: 2021 年 02 月 21 日阅读数: 13
用户头像

算法爱好者,退役 OIer 2020.03.07 加入

公众号「宫水三叶的刷题日记 」。每天十分钟,快乐学算法 ~

评论

发布
暂无评论
LeetCode 第 46 场双周赛题解