LeetCode Contest 342

6387. Calculate Delayed Arrival Time

给你一个正整数 arrivalTime 表示列车正点到站的时间（单位：小时），另给你一个正整数 delayedTime 表示列车延误的小时数。

返回列车实际到站的时间。

注意，该问题中的时间采用 24 小时制。

测试样例

输入：arrivalTime = 15, delayedTime = 5

输出：20

解释：列车正点到站时间是 15:00 ，延误 5 小时，所以列车实际到站的时间是 15 + 5 = 20（20:00）。

解答：2个输入相加，mod 24就行了

class Solution {
    public int findDelayedArrivalTime(int arrivalTime, int delayedTime) {
        return (arrivalTime + delayedTime) % 24;
    }
}

6391. Sum Multiples

给你一个正整数 n ，请你计算在 [1，n] 范围内能被 3、5、7 整除的所有整数之和。

返回一个整数，用于表示给定范围内所有满足约束条件的数字之和。

测试样例：

输入：n = 7

输出：7

解释：在 [1, 7] 范围内能被 3、5、7 整除的所有整数分别是 3、5、6、7 。数字之和为 21 。

解答：按题意遍历相加就能获得答案

class Solution {
    public int sumOfMultiples(int n) {
        int res = 0;
        for (int i = 1; i <= n; ++i) {
            if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0) {
                res += i;
            }
        }
        return res;
    }
}

6390. Sliding Subarray Beauty

给你一个长度为 n 的整数数组 nums ，请你求出每个长度为 k 的子数组的 美丽值 。

一个子数组的 美丽值 定义为：如果子数组中第 x 小整数 是 负数 ，那么美丽值为第 x 小的数，否则美丽值为 0 。

请你返回一个包含 n - k + 1 个整数的数组，依次 表示数组中从第一个下标开始，每个长度为 k 的子数组的 美丽值 。

• 子数组指的是数组中一段连续 非空 的元素序列。

测试样例

输入：nums = [1,-1,-3,-2,3], k = 3, x = 2

输出：[-1,-2,-2]

解释：

总共有 3 个 k = 3 的子数组。第一个子数组是 [1, -1, -3] ，第二小的数是负数 -1 。第二个子数组是 [-1, -3, -2] ，第二小的数是负数 -2 。第三个子数组是 [-3, -2, 3] ，第二小的数是负数 -2 。

解答：这题和数据流中寻找中位数和滑动窗口中位数类似480. Sliding Window Median。用优先队列或者红黑树动态记录排序后的数组，然后计算。大概也算是老Hard下放了

class Solution {
    private class CustQueue {
        private TreeMap<Integer, Integer> map;
        private int count;

        public CustQueue() {
            map = new TreeMap<>();
            count = 0;
        }

        public void add(int val) {
            count += 1;
            map.put(val, map.getOrDefault(val, 0) + 1);
        }

        public int size() {
            return count;
        }

        public int firstNum() {
            return map.firstKey();
        }

        public int lastNum() {
            return map.lastKey();
        }

        public boolean removeKey(int val) {
            if (map.containsKey(val)) {
                int c = map.get(val);
                --count;
                if (c == 1) {
                    map.remove(val);
                } else {
                    map.put(val, c - 1);
                }
                return true;
            }
            return false;
        }
    }

    public int[] getSubarrayBeauty(int[] nums, int k, int x) {
        CustQueue left = new CustQueue(), right = new CustQueue();
        int[] res = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; ++i) {
            right.add(nums[i]);
            int rightFirst = right.firstNum();
            right.removeKey(rightFirst);
            left.add(rightFirst);
            if (left.count > x) {
                int leftLast = left.lastNum();
                left.removeKey(leftLast);
                right.add(leftLast);
            }
            if (i >= k - 1) {
                res[i - k + 1] = Math.min(left.lastNum(), 0);
                if (!left.removeKey(nums[i - k + 1])) {
                    right.removeKey(nums[i - k + 1]);
                }
            }
        }
        return res;
    }
}

6392. Minimum Number of Operations to Make All Array Elements Equal to 1

给你一个下标从 0 开始的 正 整数数组 nums 。你可以对数组执行以下操作 任意 次：

• 选择一个满足 0 <= i < n - 1 的下标 i ，将 nums[i] 或者 nums[i+1] 两者之一替换成它们的最大公约数。

请你返回使数组 nums 中所有元素都等于 1 的 最少 操作次数。如果无法让数组全部变成 1 ，请你返回 -1 。

两个正整数的最大公约数指的是能整除这两个数的最大正整数。

测试样例

输入：nums = [2,6,3,4]

输出：4

解释：

我们可以执行以下操作：

• 选择下标 i = 2 ，将 nums[2] 替换为 gcd(3,4) = 1 ，得到 nums = [2,6,1,4] 。
• 选择下标 i = 1 ，将 nums[1] 替换为 gcd(6,1) = 1 ，得到 nums = [2,1,1,4] 。
• 选择下标 i = 0 ，将 nums[0] 替换为 gcd(2,1) = 1 ，得到 nums = [1,1,1,4] 。
• 选择下标 i = 2 ，将 nums[3] 替换为 gcd(1,4) = 1 ，得到 nums = [1,1,1,1] 。

解答：我能一下子能想到的解法是二维的动态规划，利用动态规划记录各个区间的最小操作数。这题目范围很小：2 <= nums.length <= 50。估摸着二维动态规划遍历的时候可以暴力一点。

既然选定了动态规划，接下来就是要计算转移方程。规则是：

1. 如果当前范围最大公约数不是1，那么跳过
2. 如果当前范围最大公约数是1，那么先赋值(范围长度 - 1） * 2，即最差情况完成操作的数量
3. 然后遍历左右区间，查看当前操作数是否可以进一步减少。

具体可以看我的代码。性能不是很好，但是对于这个数据集大小也是够用了

class Solution {
    public int minOperations(int[] nums) {
        if (!isValid(nums, 0, nums.length - 1)) return -1;
        int len = nums.length;
        Integer[][] dp = new Integer[len][len];
        for (int i = 0; i < len; ++i) {
            int st = 0, ed = st + i;
            while (ed < len) {
                if (isValid(nums, st, ed)) {
                    dp[st][ed] = i * 2;
                    for (int t = st; t < ed; ++t) {
                        if (dp[st][t] != null && dp[t + 1][ed] != null) {
                            dp[st][ed] = Math.min(dp[st][t] + dp[t + 1][ed], dp[st][ed]);
                        }
                        if (dp[st][t] != null) {
                            dp[st][ed] = Math.min(dp[st][t] + (ed - t - 1 + 1), dp[st][ed]);
                        }
                        if (dp[t + 1][ed] != null) {
                            dp[st][ed] = Math.min((t - st + 1) + dp[t + 1][ed], dp[st][ed]);
                        }
                    }
                }
                ++st;
                ++ed;
            }
        }
        return dp[0][len - 1];
    }

    private boolean isValid(int[] nums, int st, int ed) {
        int n = nums[st];
        for (int i = st; i <= ed; ++i) {
            n = gcd(n, nums[i]);
        }
        if (n != 1) {
            return false;
        } else {
            return true;
        }
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int tmp = a % b;
            a = b;
            b = tmp;
        }
        return a;
    }
}