2651. 计算列车到站时间
题目大意：
- 给你一个正整数
arrivalTime表示列车正点到站的时间（单位：小时），另给你一个正整数delayedTime表示列车延误的小时数。 - 返回列车实际到站的时间。
- 注意，该问题中的时间采用 24 小时制。
思想：
- 签到题
- 返回
(arrivalTime delayedTime) % 24
代码：
代码语言：javascript复制class Solution {
public int findDelayedArrivalTime(int arrivalTime, int delayedTime) {
return (arrivalTime delayedTime) % 24;
}
}2652. 倍数求和
题目大意：
- 给你一个正整数 n ，请你计算在 [1，n] 范围内能被 3、5、7 整除的所有整数之和。
- 返回一个整数，用于表示给定范围内所有满足约束条件的数字之和。
思想：
- 签到题
i从1遍历到n，将所有满足i % k == 0,k = 3, 5, 7条件的i累加即可。
代码：
代码语言：javascript复制class Solution {
public int sumOfMultiples(int n) {
int sum = 0;
for(int i = 1; i <= n; i ){
if(i % 3 == 0 || i % 5 == 0 || i % 7 == 0) sum = i;
}
return sum;
}
}2653. 滑动子数组的美丽值
题目大意：
- 给你一个长度为 n 的整数数组 nums ，请你求出每个长度为 k 的子数组的 美丽值 。
- 一个子数组的 美丽值 定义为：如果子数组中第 x 小整数 是 负数 ，那么美丽值为第 x 小的数，否则美丽值为 0 。
- 请你返回一个包含 n - k 1 个整数的数组，依次 表示数组中从第一个下标开始，每个长度为 k 的子数组的 美丽值 。
思想：
- 滑动窗口
- 将所有的数添加偏移量
base = 50，以使得所有当前窗口中出现过的数i可以利用vis[i]记录其数量； - 先将前
k - 1个数加入vis[]； - 从
i = k - 1开始，每次循环将nums[i]统计到vis中，即vis[nums[i] base]； - 由于
nums[i]的范围很小，遍历vis[]累加窗口中出现的数的数量，保存在cnt中； - 当
cnt >= x时，说明当前遍历到的数即为排序中第x小的数； - 判断减去偏移量
base后将对应美丽值返回。 - 窗口向后移动，将左边界的
nums[i - k 1]移出窗口，即vis[nums[i - k 1] base] --。
代码：
代码语言：javascript复制class Solution {
public int[] getSubarrayBeauty(int[] nums, int k, int x) {
int n = nums.length;
int[] res = new int[n - k 1]; // 答案数组
int[] vis = new int[1010]; // 记录窗口中存在数的数量
final int base = 50; // 偏移量
for(int i = 0; i < k - 1; i ) vis[nums[i] base] ; // 初始化窗口
for(int i = k - 1; i < n; i ){
int cnt = 0; // 记录数量
vis[nums[i] base] ; // 移入右边界
for(int j = 0; j < 110; j ){
cnt = vis[j];
if(cnt >= x){
res[i - k 1] = j - base < 0 ? j - base : 0;
break;
}
}
vis[nums[i - k 1] base] --; // 移出左边界
}
return res; // 返回答案
}
}2654. 使数组所有元素变成 1 的最少操作次数
题目大意：
- 给你一个下标从 0 开始的 正 整数数组 nums 。你可以对数组执行以下操作 任意 次：
- 选择一个满足 0 <= i < n - 1 的下标 i ，将
nums[i]或者nums[i 1]两者之一替换成它们的最大公约数。 - 请你返回使数组
nums中所有元素都等于 1 的 最少 操作次数。如果无法让数组全部变成 1 ，请你返回 -1 。
思想：
- 最大公约数及其性质；
- 如果一个数列中所有数的最大公约数为 g，那么无论如替换数列中任意的两个数为其最大公约数，都无法操作出 h 使得 h < g
- 证明如下： 设原数列为 a_1, a_2, ..., a_n，最大公约数为 g，操作后得到的数列为 b_1, b_2, ..., b_n，最大公约数为 h，其中 h < gb_1 = h times k_1，其中 k_1 为一个整数。则可以将 b_1 = gcd(a_1, a_2) times (a_1 div gcd(a_1, a_2))。 其中 a_1 / gcd(a_1, a_2) 是一个整数，故 h 一定整除 b_1，即 h 是 a_1 和 a_2 的公约数。 同理，根据操作规则，a_2 和 a_3 的公约数也是 h，以此类推，即 a[i] 和 a[i 1] 的公约数都是 h。 由于 h < gh 一定不能整除 a_1，即将 a_1 和 a_2 替换为 h 的操作一定不能得到最大公约数为 h 且小于 g 的数列 b_n。
- 若可以通过操作得到： 当数列存在 1 时，需要操作所有非 1 的元素； 当不存在 1 时，需要找到一个最短的连续的子数组，使得通过操作得到 1。
代码：
代码语言：javascript复制class Solution {
public int minOperations(int[] nums) {
int n = nums.length;
int t = nums[0];
int cnt = t == 1 ? 1 : 0; // 判断第一个是否为 1
for(int i = 1; i < n; i ){
t = gcd(t, nums[i]);
if(nums[i] == 1) cnt ; // 记录 1 的元素个数
}
if(t != 1) return -1; // t != 1 说明不成立
if(cnt != 0) return n - cnt; // 存在 1，最少操作 n - cnt 次
int res = n; // 连续的子数组的长度
for (int i = 0; i < n; i ) {
int tt = nums[i];
for (int j = i 1; j < n; j ) { // 遍历查找
tt = gcd(tt, nums[j]);
if (tt == 1) { // 通过操作找到了可以变为 1 的连续子数组
res = Math.min(res, j - i 1); // 更新最短长度
break;
}
}
}
return res n - 2; // 去除掉连续子数组的两个边界操作
}
private int gcd(int n, int m){
return n % m == 0 ? m : gcd(m, n % m);
}
}
