【Leetcode题解】Weekly Contest 342 周赛题目解析

Posted on Sun 23 April 2023 in Leetcode

Weekly Contest 342

第 342 场力扣周赛

前两周难的一比，今天却又来一个手速摆烂场。有点看不懂这个操作。最后一题可以总结为找 1。

题目列表

2651. Calculate Delayed Arrival Time 计算列车到站时间

根据题意，暴力模拟即可。

代码

class Solution:
    def findDelayedArrivalTime(self, arrivalTime: int, delayedTime: int) -> int:
        return (arrivalTime + delayedTime) % 24

2652. Sum Multiples 倍数求和

根据题意，暴力模拟即可。

但是这道题确实有一个数学解法。首先，我们可以用等差数列求出所有小于n且倍数为3，5和7的数字的和。但是简单相加起来会重复算一些元素，根据容斥原理（inclusion-exclusion principle），我们可以排除重复计算的元素。令\(g(n, a)\)为包含x <= n且x为a的倍数的所有x的集合，则本题的答案为

$$ f(n, \{3,5,7\}) = g(n, \{3\}) + g(n, \{5\}) + g(n, \{7\}) - g(n, \{3, 5\}) - g(n, \{3, 7\}) - g(n, \{5, 7\}) + g(n, \{3,5,7\}) $$

代码

class Solution:
    def sumOfMultiples(self, n: int) -> int:
        result = 0
        for i in range(1, n + 1):
            if i % 3 == 0 or i % 5 == 0 or i % 7 == 0:
                result += i

        return result

2653. Sliding Subarray Beauty 滑动子数组的美丽值

给定一个数组nums，找到这个数组的每一个长度为k的子数组的美丽值。子数组的美丽值定义为子数组里包含的数字中第k小的负数；若子数组第k大的数字不为负数，则为0。

根据题意进行模拟，我们知道我们要用一个数据结构维护nums里某个长度为k的子数组里面的数字。此外我们还要能快速有效的找到这个数组里第k大的数字。因为数据范围较小，实际上用列表存然后顺序遍历也是可以AC的。但在这里我们考虑用B树来处理，插入，查找和删除都是O(log(k))。

代码

class Solution:
    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:
        from sortedcontainers import SortedList
        result = [0] * (len(nums) - k + 1)
        window = SortedList()

        for i in range(len(nums)):
            if len(window) == k:
                window.remove(nums[i - k])
            window.add(nums[i])

            if len(window) == k and window[x - 1] < 0:
                # print(i, window, window[x - 1])
                result[i - k + 1] = window[x - 1]

        return result

2654. Minimum Number of Operations to Make All Array Elements Equal to 1 使数组所有元素变成 1 的最少操作次数

给定一个只包含正整数的数组nums，你可以对立面任意索引i求gcd(nums[i], nums[i + 1])并将nums[i]或nums[i + 1]替换为前面求的最大公约数。找到最少的操作次数使得数组的所有元素都变成1。

我们知道，所有数字和1的最大公约数都是1。因此只要数组里存在至少一个1，最少操作次数就为1。此外，若两个正整数互质的话，他们的最大公约数就是1。这里我们分两步走：首先构造第一个1的出现，则可知剩下的非1数字都可以跟这个1抵消，进而求出结果。

那么怎么构造第一个1的出现呢。我们可以考虑用DFS。没想到吧，这也可以D。 无论如何，我们对数组里的每一个数字，循环迭代两两求最大公约数，总能够收敛到一个结果。若在中间我们找到一个1的话，那么我们就可以通过x步找到一个1。

代码

class Solution:
    def minOperations(self, nums: List[int]) -> int:

        def find():
            steps = 0
            q = list(nums)
            while q:
                qq = []
                for i in range(len(q) - 1):
                    curr = gcd(q[i], q[i + 1])
                    if curr == 1:
                        return steps

                    qq.append(curr)

                q = qq
                steps += 1
            return -1

        steps = find()

        if steps == -1:
            return -1

        return steps + len(nums) - sum([i == 1 for i in nums])

小结

如果你想变强的话，可以做做

Contest