力扣第 342 场周赛题解

题目链接：https://leetcode.cn/contest/weekly-contest-342

# T1. 计算列车到站时间

链接：https://leetcode.cn/problems/calculate-delayed-arrival-time/

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

链接：https://leetcode.cn/problems/sum-multiples/

	class Solution {
	public int sumOfMultiples(int n) {
	int sum = 0;

	for (int i = 3; i <= n; ++i) {
	if (i % 3 == 0 \|\| i % 5 == 0 \|\| i % 7 == 0) {
	sum += i;
	}
	}

	return sum;
	}
	}

请参见下图：

tujie

	class Solution {
	public int sumOfMultiples(int n) {
	// 3 的倍数有：3, 6, 9, 12, 15, ..., 3 * n/3
	// 5 的倍数有：5, 10, 15, 20, 25, 30, 35, ... , 5 * n/5
	// 7 的倍数有：7, 14, 21, 28, 35, ... , 7 * n / 7;
	return sum(n, 3) + sum(n, 5) + sum(n, 7)
	- sum(n, 15) - sum(n , 21) - sum(n, 35) + sum(n, 105);
	}

	// 求 1...n 中 m 的所有倍数之和
	private int sum(int n, int m) {
	// 等差数列求和
	return (1 + n / m) * (n / m) / 2 * m;
	}
	}

链接：https://leetcode.cn/problems/sliding-subarray-beauty/

模拟 + 计数排序

	class Solution {
	public int[] getSubarrayBeauty(int[] nums, int k, int x) {
	int n = nums.length;
	// 排序数组
	int[] heap = new int[101];
	int[] arr = new int[n - k + 1];
	for (int i = 0; i < n; ++i) {
	++heap[nums[i] + 50];
	if (i >= k - 1) {
	// 获取 heap 中第 x 小的数
	int xth = smallXth(heap, x);
	arr[i - k + 1] = Math.min(xth, 0);
	--heap[nums[i - k + 1] + 50];
	}
	}

	return arr;
	}

	private int smallXth(int[] cnt, int x) {
	int sum = 0;
	for (int i = 0; i < cnt.length; ++i) {
	sum += cnt[i];
	if (sum < x) continue;
	return i - 50;
	}
	return 0;
	}
	}

链接：https://leetcode.cn/problems/minimum-number-of-operations-to-make-all-array-elements-equal-to-1/

求子数组的 gcd：

分情况：

数组中存在 1，答案就是： nums.length - 1的个数
整个数组的GCD > 1 ，直接返回 -1
求最短 GCD=1的子数组 ：
1. 将某个数线先通过不断取 gcd 的值，变成 1，需要的次数就是 len(子数组) - 1
2. 用该数将其它数直接通过 gcd 赋值成 1，即每个数需要花费一次操作，即总共需要 len(整个数组) - 1 次

	class Solution {
	public int minOperations(int[] nums) {
	int n = nums.length;
	int gg = 0;
	int oneCnt = 0;

	for (int num : nums) {
	gg = gcd(gg, num);
	if (num == 1) ++oneCnt;
	}

	// 所有数的最大公因数 > 1 直接返回
	if (gg > 1) return -1;

	// 数组中就存在 1
	if (oneCnt > 0) return n - oneCnt;

	// 最短 gcd () = 1 的子数组
	int minLen = n;
	for (int i = 0; i < n - 1; ++i) {
	int g = 0;
	for (int j = i; j < n; ++j) {
	g = gcd(g, nums[j]);
	if (g == 1) {
	minLen = Math.min(minLen, j - i + 1);
	break;
	}
	}
	}

	// 经过 minLen 次将一个数变成 1，再用这个 1 将其它的元素直接变成 1
	return (minLen - 1) + n - 1;
	}

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