您现在的位置是:首页 >学无止境 >LeetCode笔记:Weekly Contest 342网站首页学无止境

LeetCode笔记:Weekly Contest 342

Espresso Macchiato 2023-07-01 04:00:02
简介LeetCode笔记:Weekly Contest 342

1. 题目一

给出题目一的试题链接如下:

1. 解题思路

这一题没啥好说的,就是相加之后对24进行一下求余即可。

2. 代码实现

给出python代码实现如下:

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

提交代码评测得到:耗时29ms,占用内存13.9MB。

2. 题目二

给出题目二的试题链接如下:

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. 题目三

给出题目三的试题链接如下:

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. 题目四

给出题目四的试题链接如下:

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。

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。