双周赛101（模拟、动态规划、中位数贪心+裴蜀定理、BFS）

6327. 从两个数字数组里生成最小数字

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

示例 1：

输入：nums1 = [4,1,3], nums2 = [5,7]s
输出：15
解释：数字 15 的数位 1 在 nums1 中出现，数位 5 在 nums2 中出现。15 是我们能得到的最小数字。

示例 2：

输入：nums1 = [3,5,2,6], nums2 = [3,1,7]
输出：3
解释：数字 3 的数位 3 在两个数组中都出现了。

提示：

• 1 <= nums1.length, nums2.length <= 9
• 1 <= nums1[i], nums2[i] <= 9
• 每个数组中，元素 互不相同 。

模拟

class Solution {
    public int minNumber(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Set<Integer> set = new HashSet<>();
        for(int n : nums1) set.add(n);
        Arrays.sort(nums2);
        int a = nums1[0], b = nums2[0];
        for(int c : nums2) {
            if (set.contains(c)) return c;
        }
        if(a > b) return b*10 + a;
        else return a*10 + b;
    }
}

6328. 找到最大开销的子字符串

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

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

字符的价值 定义如下：

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

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

示例 1：

输入：s = "adaa", chars = "d", vals = [-1000]
输出：2
解释：字符 "a" 和 "d" 的价值分别为 1 和 -1000 。
最大开销子字符串是 "aa" ，它的开销为 1 + 1 = 2 。
2 是最大开销。

示例 2：

输入：s = "abc", chars = "abc", vals = [-1,-1,-1]
输出：0
解释：字符 "a" ，"b" 和 "c" 的价值分别为 -1 ，-1 和 -1 。
最大开销子字符串是 "" ，它的开销为 0 。
0 是最大开销。

提示：

• 1 <= s.length <= 105
• s 只包含小写英文字母。
• 1 <= chars.length <= 26
• chars 只包含小写英文字母，且 互不相同 。
• vals.length == chars.length
• -1000 <= vals[i] <= 1000

同向双指针

class Solution {
    public int maximumCostSubstring(String s, String chars, int[] vals) {
        Map<Character, Integer> map = new HashMap<>();
        for(int i = 0; i < vals.length; i++){
            map.put(chars.charAt(i), vals[i]);
        }
        int res = 0;
        int left = 0, right = 0;
        int cur = 0;
        while(right < s.length()){
            int v = map.containsKey(s.charAt(right)) ? map.get(s.charAt(right)) : s.charAt(right)-'a'+1;
            right++;
            cur += v;
            if(cur > res){
                res = cur;
            }else{
                while(left < right && cur < 0){
                    int d = map.containsKey(s.charAt(left)) ? map.get(s.charAt(left)) : s.charAt(left)-'a'+1;
                    cur -= d;
                    left++;
                }
            }
        }
        return res;
    }
}

动态规划

同： 53. 最大子数组和

考虑f[i]接还是不接在f[i-1]后面：

• 接：f[i] = f[i-1] + nums[i]
• 不接：f[i] = nums[i]

class Solution {
    public int maximumCostSubstring(String s, String chars, int[] vals) {
        Map<Character, Integer> map = new HashMap<>();
        for(int i = 0; i < vals.length; i++){
            char c = chars.charAt(i);
            int val = vals[i];
            map.put(c, val);
        }
        int n = s.length();
        int[] dp = new int[n+1];
        dp[0] = Math.max(map.getOrDefault(s.charAt(0), s.charAt(0)-'a'+1), 0);
        int res = dp[0];
        for(int i = 1; i < n; i++){
            int v = map.containsKey(s.charAt(i)) ? map.get(s.charAt(i)) : s.charAt(i)-'a'+1;
            dp[i] = Math.max(dp[i-1] + v, 0);
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

(相似)53. 最大子数组和

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

输入：nums = [1]
输出：1

输入：nums = [5,4,-1,7,8]
输出：23

class Solution {
    public int maxSubArray(int[] nums) {
        // 【重要】技巧：无后效性
        // 这里状态的定义不是题目中的问题的定义，不能直接将最后一个状态返回回去；
        // 这里状态的定义不是题目中的问题的定义，不能直接将最后一个状态返回回去；
        // 这里状态的定义不是题目中的问题的定义，不能直接将最后一个状态返回回去。
        // 接：f[i] = f[i-1] + nums[i]
        // 不接：f[i] = nums[i]
        // 两种情况取最大值
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int res = dp[0];
        for(int i = 1; i < nums.length; i++){
            dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}
// 【重要】技巧：无后效性
// 李煜东著《算法竞赛进阶指南》：为了保证计算子问题能够按照顺序、不重复地进行，
// 动态规划要求已经求解的子问题不受后续阶段的影响。这个条件也被叫做「无后效性」。
// 换言之，动态规划对状态空间的遍历构成一张有向无环图，遍历就是该有向无环图的一个拓扑序。
// 有向无环图中的节点对应问题中的「状态」，图中的边则对应状态之间的「转移」，转移的选取就是动态规划中的「决策」。

🎃6329. 使子数组元素和相等

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

输入：arr = [2,5,5,7], k = 3
输出：5
解释：在下标为 0 的元素那里执行三次运算，使其等于 5 。在下标为 3 的元素那里执行两次运算，使其等于 5 。
执行运算后，数组变为 [5,5,5,5] 。
- 0 处起始的子数组为 [5, 5, 5] ，元素总和为 15
- 1 处起始的子数组为 [5, 5, 5] ，元素总和为 15
- 2 处起始的子数组为 [5, 5, 5] ，元素总和为 15
- 3 处起始的子数组为 [5, 5, 5] ，元素总和为 15

中位数贪心 + 裴蜀定理

class Solution {
    // a[i] + a[i+1] + .. + a[i+k-1]
    // = a[i+1] + a[i+2] + .. + a[i+k]
    // ==> a[i] = a[i+k]

    // 按照i mod k 的结果将 arr 分组，对每一组（记为b）：
    // 让数组b的所有元素相等的最少运算次数：
    // 根据中位数贪心：将b的所有元素变为b的中位数是最优的
    // 裴蜀定理 ： 一个循环数组如果既有周期n，又有周期k，则必然有周期gcd(n,k)
    public long makeSubKSumEqual(int[] arr, int k) {
        int n = arr.length;
        k = gcd(k, n);
        long ans = 0;
        for(int i = 0; i < k; i++){
            List<Integer> list = new ArrayList<>();
            for(int j = i; j < n; j += k){
                list.add(arr[j]);
            }
            Collections.sort(list);
            int mid = list.get(list.size() / 2);
            for(int x : list){
                ans += Math.abs(x - mid);
            }
        }
        return ans;
    }

    public int gcd(int x, int y){
        return y == 0 ? x : gcd(y, x%y);
    }
}

(相似)462. 最小操作次数使数组元素相等 II

输入：nums = [1,2,3]
输出：2
解释：
只需要两次操作（每次操作指南使一个元素加 1 或减 1）：
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

输入：nums = [1,10,2,9]
输出：16

class Solution {
    public int minMoves2(int[] nums) {
        // 中位数贪心
        int res = 0;
        Arrays.sort(nums);
        int mid = nums[nums.length/2];
        for(int x : nums){
            res += Math.abs(x - mid);
        }
        return res;
    }
}

🎃6330. 图中的最短环

输入：n = 7, edges = [[0,1],[1,2],[2,0],[3,4],[4,5],[5,6],[6,3]]
输出：3
解释：长度最小的循环是：0 -> 1 -> 2 -> 0 

输入：n = 4, edges = [[0,1],[0,2]]
输出：-1
解释：图中不存在循环

BFS

比赛时一直在想

①：1->2, 2->1 ，访问完1，访问2，存在2到1的连接，怎么判断？ :BFS传参数pre，标识从这个节点过来的

class Solution {
    // 从0出发跑bfs, 同时维护0到每个点的最短路dis
    // 0 出队，1 2入队； 1出队 3入队；2出队 4入队； 
    // 3出队发现4已经入队
    // 此时就找到了一个包含0的最小环，环长尾dis[3] + dis[4] + 1
    // 从每个顶点都跑一遍bfs，最小环一定能找到
    List<Integer>[] g;
    int[] dis; // dis[i] 表示从 start 到 i 的最短路长度
    public int findShortestCycle(int n, int[][] edges) {
        g = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for(int[] e : edges){
            int x = e[0], y = e[1];
            g[x].add(y);
            g[y].add(x);
        }
        dis = new int[n];
        int res = Integer.MAX_VALUE;
        for(int i = 0; i < n; i++){
            // 枚举每个起点跑 BFS
            res = Math.min(res, bfs(i));
        }
        return res < Integer.MAX_VALUE ? res : -1;
    }

    // 若存在环返回最短环长度，否则返回maxint
    public int bfs(int start){
        Arrays.fill(dis, -1);
        dis[start] = 0;
        Deque<int[]> dq = new ArrayDeque<>(); // i, pre
        dq.add(new int[]{start, -1});
        while(!dq.isEmpty()){
            int[] p = dq.pollFirst();
            int x = p[0], fa = p[1];
            for(int y : g[x]){
                if(dis[y] < 0){ // 第一次遇到
                    dis[y] = dis[x] + 1;
                    dq.addLast(new int[]{y, x});
                } else if (y != fa){ // 第二次遇到
                    // 由于是BFS，后面不会遇到更短的环了
                    return dis[x] + dis[y] + 1;
                }
            }
        }
        return Integer.MAX_VALUE; // 该连通块无环
    }
}