LeetCode笔记：Weekly Contest 342

• LeetCode笔记：Weekly Contest 342
  • 1. 题目一
    • 1. 解题思路
    • 2. 代码实现
  • 2. 题目二
    • 1. 解题思路
    • 2. 代码实现
  • 3. 题目三
    • 1. 解题思路
    • 2. 代码实现
  • 4. 题目四
    • 1. 解题思路
    • 2. 代码实现

• 比赛链接：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 = 0
        for i in range(1, n+1):
            if i % 3 == 0 or i % 5 == 0 or i % 7 == 0:
                res += i
        return 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 + 1
        for i in range(n-1):
            d, cnt = nums[i], 0
            for j in range(i+1, n):
                d = gcd(d, nums[j])
                cnt += 1
                if d == 1:
                    break
            if d == 1:
                res = min(res, cnt)
        return -1 if res == n+1 else n + res - 1

提交代码评测得到：耗时51ms，占用内存16.2MB。