LeetCode 第 46 场双周赛题解

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

输入：s = "Bb"输出："Bb"解释："Bb" 是美好字符串，因为 'B' 和 'b' 都出现了。整个字符串也是原字符串的子字符串。

输入：s = "c"输出：""解释：没有美好子字符串。

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

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;    }}

输入：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] 。这两个子数组是不相交的，因为它们没有任何共同的元素。

输入：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] 之前。

输入：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 开始）。

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;    }}

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

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

为了方便，使用 * 代表水域
起始状态     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]

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;    }}

输入：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 是离它最近的符合要求的祖先节点。

输入：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]

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);    }}