- LeetCode笔记：Weekly Contest 342
- 1. 题目一
- 1. 解题思路
- 2. 代码实现
- 2. 题目二
- 1. 解题思路
- 2. 代码实现
- 3. 题目三
- 1. 解题思路
- 2. 代码实现
- 4. 题目四
- 1. 解题思路
- 2. 代码实现
- 1. 题目一
- 比赛链接：https://leetcode.com/contest/weekly-contest-342
1. 题目一
给出题目一的试题链接如下：
- 2651. Calculate Delayed Arrival Time
1. 解题思路
这一题没啥好说的，就是相加之后对24进行一下求余即可。
2. 代码实现
给出python代码实现如下：
class Solution:def findDelayedArrivalTime(self, arrivalTime: int, delayedTime: int) -> int:return (arrivalTime + delayedTime) % 24
提交代码评测得到：耗时29ms，占用内存13.9MB。
2. 题目二
给出题目二的试题链接如下：
- 2652. Sum Multiples
1. 解题思路
这一题其实可以用容斥原理加等差数列求和公式求得更快速一些，不过这里我就偷了个懒，直接做了个循环拉倒了……
2. 代码实现
给出python代码实现如下：
class Solution:def sumOfMultiples(self, n: int) -> int:res = 0for i in range(1, n+1):if i % 3 == 0 or i % 5 == 0 or i % 7 == 0:res += ireturn res
提交代码评测得到：耗时66ms，占用内存13.9MB。
3. 题目三
给出题目三的试题链接如下：
- 2653. Sliding Subarray Beauty
1. 解题思路
这题我们就是用一个滑动窗口进行扫描即可，在滑动窗口当中，我们仅按大小排序保留负数即可。
2. 代码实现
给出python代码实现如下：
class Solution:def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:s = []res = []n = len(nums)for i in range(k):if nums[i] < 0:bisect.insort(s, nums[i])if len(s) >= x:res.append(s[x-1])else:res.append(0)for j in range(k, n):# print(nums, n, j)if nums[j] < 0:bisect.insort(s, nums[j])if nums[j-k] < 0:s.pop(bisect.bisect_left(s, nums[j-k]))if len(s) >= x:res.append(s[x-1])else:res.append(0)return res
提交代码评测得到：耗时3749ms，占用内存27.7MB。
4. 题目四
给出题目四的试题链接如下：
- 2654. Minimum Number of Operations to Make All Array Elements Equal to 1
1. 解题思路
这题挺伤心的，因为一开始没想出来，后来看了答案简直吐血……
这道题很显然的要想全变为1，那么必然要经过一系列变换之后使得相邻两数没有公因子，或者说互质，此时就可以将其中一个变为1，此时其他的数必然也能变为1。
当然，如果原数组当中本就有1的话就更方便了。
不过，我当时没想到的是，要想最快速的是一个数变为1，必然是一系列针对连续数的操作，这个可以用反证法快速说明的。
因此，我们用一个二重循环事实上就能够快速地得到我们的答案了。
2. 代码实现
给出python代码实现如下：
class Solution:def minOperations(self, nums: List[int]) -> int:if 1 in nums:return len(nums) - nums.count(1)n = len(nums)res = n + 1for i in range(n-1):d, cnt = nums[i], 0for j in range(i+1, n):d = gcd(d, nums[j])cnt += 1if d == 1:breakif d == 1:res = min(res, cnt)return -1 if res == n+1 else n + res - 1
提交代码评测得到：耗时51ms，占用内存16.2MB。
