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