LeetCode Biweekly Contest 101

6327. Form Smallest Number From Two Digit Arrays

给你两个只包含 1 到 9 之间数字的数组 nums1 和 nums2 ，每个数组中的元素 互不相同 ，请你返回 最小 的数字，两个数组都 至少 包含这个数字的某个数位。

测试样例

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

输出：15

解释：

数字 15 的数位 1 在 nums1 中出现，数位 5 在 nums2 中出现。15 是我们能得到的最小数字。

没有分配方案能让获得 8 美元的儿童数超过 1 。

解答：如果2个数组有一样的数字，则返回最小的相同数字。否则就分别挑选2个数组的最小值，然后返回一个十位数。

class Solution {
    public int minNumber(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();
        int min2 = Integer.MAX_VALUE;
        for (int n : nums2) {
            set.add(n);
            min2 = Math.min(n, min2);
        }
        int min1 = Integer.MAX_VALUE, common = Integer.MAX_VALUE;
        for (int n : nums1) {
            if (set.contains(n)) {
                common = Math.min(common, n);
            }
            min1 = Math.min(min1, n);
        }
        if (common != Integer.MAX_VALUE) {
            return common;
        }
        return Math.min(min1, min2) * 10 + Math.max(min1, min2);
    }
}

6328. Find the Substring With Maximum Cost

给你一个字符串 s ，一个字符 互不相同 的字符串 chars 和一个长度与 chars 相同的整数数组 vals 。

子字符串的开销 是一个子字符串中所有字符对应价值之和。空字符串的开销是 0 。

字符的价值 定义如下：

• 如果字符不在字符串 chars 中，那么它的价值是它在字母表中的位置（下标从 1 开始）。
  • 比方说，'a' 的价值为 1 ，'b' 的价值为 2 ，以此类推，'z' 的价值为 26 。
• 否则，如果这个字符在 chars 中的位置为 i ，那么它的价值就是 vals[i]。

请你返回字符串 s 的所有子字符串中的最大开销。

测试样例：

输入：s = "adaa", chars = "d", vals = [-1000]

输出：2

解释：

字符 "a" 和 "d" 的价值分别为 1 和 -1000 。最大开销子字符串是 "aa" ，它的开销为 1 + 1 = 2 。2 是最大开销。

解答: 本质就是最大子数组和

class Solution {
    public int maximumCostSubstring(String s, String chars, int[] vals) {
        int[] map = new int[26];
        for (int i = 0; i < 26; ++i) {
            map[i] = i + 1;
        }
        for (int i = 0; i < chars.length(); ++i) {
            map[chars.charAt(i) - 'a'] = vals[i];
        }
        int max = 0, sum = 0;
        for (int i = 0; i < s.length(); ++i) {
            sum += map[s.charAt(i) - 'a'];
            max = Math.max(max, sum);
            sum = Math.max(0, sum);
        }
        return max;
    }
}

6329. Make K-Subarray Sums Equal

给你一个下标从 0 开始的整数数组 arr 和一个整数 k 。数组 arr 是一个循环数组。换句话说，数组中的最后一个元素的下一个元素是数组中的第一个元素，数组中第一个元素的前一个元素是数组中的最后一个元素。

你可以执行下述运算任意次：

• 选中 arr 中任意一个元素，并使其值加上 1 或减去 1 。

执行运算使每个长度为 k 的 子数组 的元素总和都相等，返回所需要的最少运算次数。

子数组 是数组的一个连续部分。

测试样例：

输入：arr = [1,4,1,3], k = 2

输出：1

解释：

在下标为 1 的元素那里执行一次运算，使其等于 3 。

执行运算后，数组变为 [1,3,1,3] 。

• 0 处起始的子数组为 [1, 3] ，元素总和为 4
• 1 处起始的子数组为 [3, 1] ，元素总和为 4
• 2 处起始的子数组为 [1, 3] ，元素总和为 4
• 3 处起始的子数组为 [3, 1] ，元素总和为 4

解答: 由于数组是循环数组，且所有长度为k的子数组总和一定要一样。那么我们可以知道arr[i] == arr[(i + k) % arr.length]。这样用并查集将所有应该一样的数字聚合，然后利用中位数寻找产生的操作数。

class Solution {
    private class DSU {
        private int[] parent;

        public DSU(int n) {
            parent = new int[n];
            for (int i = 0; i < n; ++i) {
                parent[i] = i;
            }
        }

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

        public void union(int x, int y) {
            parent[find(x)] = find(y);
        }
    }

    public long makeSubKSumEqual(int[] arr, int k) {
        DSU uf = new DSU(arr.length);
        for (int i = 0; i < arr.length; ++i) {
            uf.union(i, (i + k) % arr.length);
        }
        Map<Integer, List<Integer>> group = new HashMap<>();
        for (int i = 0; i < arr.length; ++i) {
            int p = uf.find(i);
            if (!group.containsKey(p)) {
                group.put(p, new ArrayList<>());
            }
            group.get(p).add(arr[i]);
        }
        long res = 0;
        for (Map.Entry<Integer, List<Integer>> kv : group.entrySet()) {
            res += helper(kv.getValue());
        }
        return res;
    }

    private long helper(List<Integer> list) {
        Collections.sort(list);
        int mid = list.get(list.size() / 2);
        long res = 0;
        for (int i : list) {
            res += Math.abs(i - mid);
        }
        return res;
    }
}

6330. Shortest Cycle in a Graph

现有一个含 n 个顶点的 双向 图，每个顶点按从 0 到 n - 1 标记。图中的边由二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示顶点 ui 和 vi 之间存在一条边。每对顶点最多通过一条边连接，并且不存在与自身相连的顶点。

返回图中 最短 环的长度。如果不存在环，则返回 -1 。

环 是指以同一节点开始和结束，并且路径中的每条边仅使用一次。

测试样例：

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

输出：3

解释：

长度最小的循环是：0 -> 1 -> 2 -> 0

解答：这道题目有2个很重要的提示：

• 2 <= n <= 1000
• 1 <= edges.length <= 1000

这个规模可以直接利用暴力计算每个节点为开始的最小环（如果存在环的话）。

class Solution {
    public int findShortestCycle(int n, int[][] _edges) {
        List<Integer>[] edges = new List[n];
        for (int i = 0; i < n; ++i) {
            edges[i] = new ArrayList<>();
        }
        for (int[] e : _edges) {
            edges[e[0]].add(e[1]);
            edges[e[1]].add(e[0]);
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < n; ++i) {
            Queue<int[]> queue = new LinkedList<>();
            queue.add(new int[]{i, -1}); queue.add(null);
            int[] isVisited = new int[n];
            Arrays.fill(isVisited, -1);
            isVisited[i] = 0;
            int dis = 1;

            while (queue.size() > 1) {
                int[] tmp = queue.poll();
                if (tmp == null) {
                    queue.add(null);
                    ++dis;
                } else {
                    for (int next : edges[tmp[0]]) {
                        if (isVisited[next] == -1) {
                            isVisited[next] = dis;
                            queue.add(new int[]{next, tmp[0]});
                        } else if (next != tmp[1]) {
                            min = Math.min(min, isVisited[next] + isVisited[tmp[0]] + 1);
                        }
                    }
                }
            }
        }
        return min == Integer.MAX_VALUE ? -1 : min;
    }
}