周赛342

6387. 计算列车到站时间

难度简单1

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

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

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

示例 1：

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

示例 2：

输入：arrivalTime = 13, delayedTime = 11
输出：0
解释：列车正点到站时间是 13:00 ，延误 11 小时，所以列车实际到站的时间是 13 + 11 = 24（在 24 小时制中表示为 00:00 ，所以返回 0）。

提示：

• 1 <= arrivaltime < 24
• 1 <= delayedTime <= 24

模拟

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

6391. 倍数求和

难度简单0

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

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

示例 1：

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

示例 2：

输入：n = 10
输出：40
解释：在 [1, 10] 范围内能被 3、5、7 整除的所有整数分别是 3、5、6、7、9、10 。数字之和为 40 。

示例 3：

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

提示：

• 1 <= n <= 103

模拟

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

进阶：数据范围1e9？

题解：https://leetcode.cn/problems/sum-multiples/solution/o1-rong-chi-yuan-li-by-endlesscheng-yxc4/

容斥原理，m的倍数有n/m个，用等差数列求和可以O(1)的算出这些数的和

class Solution {// 1~n 中 m 的倍数的和private int sub(int bound, int num) {// 3 6 9 12 15if (bound < num) return 0;        // - 等差数列通项公式：An = a1 + (n - 1) * d// - 等差数列求和公式：(a1 + an) * n / 2int n = bound / num;int a1 = num;int an = a1 + (n - 1) * num;return (a1 + an) * n / 2;}public int sumOfMultiples(int n) {// 容斥原理return sub(n, 3) + sub(n, 5) + sub(n, 7) - sub(n, 3 * 5) - sub(n, 5 * 7) - sub(n, 3 * 7) + sub(n, 3 * 5 * 7);}
}

😣6390. 滑动子数组的美丽值

难度中等7

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

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

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

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

示例 1：

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

示例 2：

输入：nums = [-1,-2,-3,-4,-5], k = 2, x = 2
输出：[-1,-2,-3,-4]
解释：总共有 4 个 k = 2 的子数组。
[-1, -2] 中第二小的数是负数 -1 。
[-2, -3] 中第二小的数是负数 -2 。
[-3, -4] 中第二小的数是负数 -3 。
[-4, -5] 中第二小的数是负数 -4 。

示例 3：

输入：nums = [-3,1,2,-3,0,-3], k = 2, x = 1
输出：[-3,0,-3,-3,-3]
解释：总共有 5 个 k = 2 的子数组。
[-3, 1] 中最小的数是负数 -3 。
[1, 2] 中最小的数不是负数，所以美丽值为 0 。
[2, -3] 中最小的数是负数 -3 。
[-3, 0] 中最小的数是负数 -3 。
[0, -3] 中最小的数是负数 -3 。

提示：

• n == nums.length
• 1 <= n <= 105
• 1 <= k <= n
• 1 <= x <= k
• -50 <= nums[i] <= 50

题解：

• 第 x 大的数意味着从小到大累计出现次数，到该数时总和（前缀和）大于等于 x，可以直接暴力逐个计算，也可以用二分查找第 x 个数+ 树状数组计算前缀和。

class Solution {/思想：滑动窗口 + 计数排序第x小的定义：假设区间内第 x 小的整数叫做：num(x 从 1 开始)则=> 1.  < num 的个数  < x    2. <= num 的个数 >= x（存在重复元素）题解来源：xhchen滑动窗口：因为数组值域[-50,50]范围很小，所以可以使用滑动窗口枚举大小为k的子数组，同时维护每个值在子数组中出现的次数cnt(val)，假设cnt(val)的前缀和为s(val)，满足s(val)>=x的最小val即为当前子数组的第x小数*/public int[] getSubarrayBeauty(int[] a, int k, int x) {int n = a.length;int[] cnt = new int[105];int diff = 50; // 值域[-50,50]，偏移量difffor(int i = 0; i < k-1; i++){ //统计区间[0,k-1]上的元素出现次数，使得处理第一个区间和后面区间方式相同cnt[diff + a[i]]++;}int[] res = new int[n - k + 1];for(int l = 0, r = k-1; r < n; l++, r++){ // 枚举每个窗口cnt[diff + a[r]]++;int s = 0;for(int i = -50; i <= 50; i++){s += cnt[diff + i];if(s >= x){ // 第x小的定义：<= num 的个数 >= x（存在重复元素）res[l] = Math.min(i, 0);break;}}cnt[diff + a[l]]--;}return res;}
}

😣6392. 使数组所有元素变成 1 的最少操作次数

难度中等4

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

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

请你返回使数组 nums 中所有元素都等于 1 的 最少 操作次数。如果无法让数组全部变成 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 = [2,10,6,14]
输出：-1
解释：无法将所有元素都变成 1 。

提示：

• 2 <= nums.length <= 50
• 1 <= nums[i] <= 106

方法一：暴力枚举每个区间，计算区间最小gcd值

class Solution {public int minOperations(int[] nums) {int n = nums.length, gcdAll = 0, cnt1 = 0;for(int x : nums){gcdAll = gcd(gcdAll, x); // 获得整个数组的gcd值if(x == 1) cnt1++;}if(gcdAll > 1) return -1; // 整个数组gcd != 1if(cnt1 > 0) return n - cnt1; // 1和其他数gcd = 1int minsize = n; // 找到最小的连续子数组，使其gcd=1// 暴力枚举每个区间for(int i = 0; i < n; i++){int g = 0;for(int j = i; j < n; j++){g = gcd(g, nums[j]); if(g == 1){minsize = Math.min(minsize, j-i+1);break;}}}// 10 5 2 : n = 3// gcd(10,5)=5  : 5 5 2// gcd(5,2)=1   : 5 5 1// minsize-1次能操作出1，然后将数组剩下元素变成1 n-1// 操作次数 minsize-1 + n-1return minsize + n - 2;}public int gcd(int x, int y){return y == 0 ? x : gcd(y , x%y);}
}

方法二：利用gcd的性质

class Solution {public int minOperations(int[] nums) {int n = nums.length, gcdAll = 0, cnt1 = 0;for(int x : nums){gcdAll = gcd(gcdAll, x); // 获得整个数组的gcd值if(x == 1) cnt1++;}if(gcdAll > 1) return -1; // 整个数组gcd != 1if(cnt1 > 0) return n - cnt1; // 1和其他数gcd = 1int minsize = n; // 找到最小的连续子数组，使其gcd=1/GCD 要么不变，要么减半不同GCD的个数 = O(logU)2 6 3 4枚举 以i为结尾的区间的gcdg = [2]g = [2, 6]g = [1, 3, 3] = [1, 3]g = [1, 1, 4] = [1, 4]还要记录gcd上一次出现的下标（计算出子数组长度）*/List<int[]> g = new ArrayList<int[]>(); // [GCD，相同 GCD 闭区间的右端点(最晚出现位置)]for(int i = 0; i < n; i++){for(int[] p : g) // 和list中每个数求一个gcdp[0] = gcd(p[0], nums[i]);g.add(new int[]{nums[i], i}); // 将当前元素加入list中int j = 0; // 去重，因为相同的 GCD 都相邻在一起for(int[] p : g){ // 去重采用双指针思想（如果相同j,p++，不相同j++,p++）if(g.get(j)[0] == p[0])g.get(j)[1] = p[1];  // 合并相同值，下标取最小的（保留相同的两个数 右边数的下标）else{g.set(++j, p); // 不相同，自增后保存p}}g.subList(j+1, g.size()).clear();if(g.get(0)[0] == 1){minsize = Math.min(minsize, i - g.get(0)[1] + 1);}}// 10 5 2 : n = 3// gcd(10,5)=5  : 5 5 2// gcd(5,2)=1   : 5 5 1// minsize-1次能操作出1，然后将数组剩下元素变成1 n-1// 操作次数 minsize-1 + n-1return minsize + n - 2;}public int gcd(int x, int y){return y == 0 ? x : gcd(y , x%y);}
}

原地去重

class Solution {public int minOperations(int[] nums) {int n = nums.length, gcdAll = 0, cnt1 = 0;for(int x : nums){gcdAll = gcd(gcdAll, x); // 获得整个数组的gcd值if(x == 1) cnt1++;}if(gcdAll > 1) return -1; // 整个数组gcd != 1if(cnt1 > 0) return n - cnt1; // 1和其他数gcd = 1int minsize = n; // 找到最小的连续子数组，使其gcd=1/GCD 要么不变，要么减半不同GCD的个数 = O(logU)2 6 3 4枚举 以i为结尾的区间的gcdg = [2]g = [2, 6]g = [1, 3, 3] = [1, 3]g = [1, 1, 4] = [1, 4]还要记录gcd上一次出现的下标（计算出子数组长度）*/List<int[]> g = new ArrayList<int[]>(); // [GCD，相同 GCD 闭区间的右端点(最晚出现位置)]for(int i = 0; i < n; i++){g.add(new int[]{nums[i], i}); // 将当前元素加入list中int j = 0;// 原地去重，因为相同的 GCD 都相邻在一起for(int[] p : g){ // 和list中每个数求一个gcdp[0] = gcd(p[0], nums[i]);if(g.get(j)[0] == p[0])g.get(j)[1] = p[1];  // 合并相同值，下标取最小的（保留相同的两个数 右边数的下标）else{g.set(++j, p); // 不相同，自增后保存p}}g.subList(j+1, g.size()).clear();if(g.get(0)[0] == 1){minsize = Math.min(minsize, i - g.get(0)[1] + 1);}}// 10 5 2 : n = 3// gcd(10,5)=5  : 5 5 2// gcd(5,2)=1   : 5 5 1// minsize-1次能操作出1，然后将数组剩下元素变成1 n-1// 操作次数 minsize-1 + n-1return minsize + n - 2;}public int gcd(int x, int y){return y == 0 ? x : gcd(y , x%y);}
}