Leetcode第342场周赛解题报告

本次题目太简单，基本没有什么难度，不清楚lc为什么这样设计，没有什么区分度

2651. 计算列车到站时间

知识点：智商
复杂度：$O(1)$
lc之顶级凑合事

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

2652. 倍数求和

知识点：模拟
复杂度：$O(n)$
lc脸都不要了.jpg

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

2653. 滑动子数组的美丽值

知识点：滑动窗口/模拟
复杂度：$O(101 * n)$
首先是值的更新过程，可以使用滑动窗口按照题意模拟更新，即每次移动窗口，删除第一个值，增加新的值，形成新的窗口
然后就是取窗口中的第x小的数，也就是说需要排序（要么是优先队列等） 注意数组中值的取值范围，也就是说本题的场景是属于搜索次数较多，但是取值范围较小
因此使用“桶排序”等非比较排序方法比较好

class Solution:
    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:
        cnt = [0] * 101
        def fnd_par(x):
            s = 0
            for i in range(0,101):
                s += cnt[i]
                if s >= x:
                    if i - 50 >= 0:
                        return 0
                    return i - 50
        ans = []
        for i in range(k):
            cnt[nums[i] + 50] += 1 #cnt
        ans.append(fnd_par(x))
        # 滑动窗口
        for i in range(k, len(nums)):
            cnt[nums[i-k] + 50] -= 1
            cnt[nums[i] + 50] += 1
            ans.append(fnd_par(x))
        return ans

2654. 使数组所有元素变成 1 的最少操作次数

知识点：数学
复杂度：$O(n * n)$
只要出现一个1，那么可以把剩下所有数变成1，也就是说1是可以传播的
所以问题转化为在所有数中间出现第一个1的最小步数，然后就可以把剩下所有数变为1
也就是说，进行$O(n * n)$次操作，分别把所有数的gcd求出来，假如有1，则清楚了出现1的模式，然后开始1的传播

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        def cnt(arr):
            res = 0
            for i in arr:
                if i == 1:
                    res += 1
            return res

        cnt1 = cnt(nums)

        stp = 0
        if cnt1 > 0:
            return len(nums)-cnt1
        while cnt1 == 0 and stp <= 1000:
            flg = False
            for i in range(0,len(nums)-1):
                nv = math.gcd(nums[i], nums[i+1])
                if nv != nums[i]:
                    flg = True
                nums[i] = nv
            cnt1 = cnt(nums)
            stp += 1
            if not flg:
                return -1
        return stp + len(nums) - 1