讨论/题目交流/🐱 第 19 场夜喵双周赛/
🐱 第 19 场夜喵双周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 将数字变成 0 的操作次数
4 分 - 大小为 K 且平均值大于等于阈值的子数组数目
5 分 - 时钟指针的夹角
6 分 - 跳跃游戏 IV

展开讨论
力扣 (LeetCode)发起于 2020-02-08

分享下我四道题的代码和思路
第一题很简单,就不具体说明了

class Solution:
    def numberOfSteps (self, num: int) -> int:
        step = 0
        while num:
            step += 1
            if num & 1:
                num -= 1
            else:
                num >>= 1
        return step

第二题,我竟然花了很长时间在理清题目意思上。
我开始以为子数组是可以不连续的,所以看example1有点看不懂。后来想到说“最大子数组之和”那道题,子数组就是连续的,才搞明白。
然后我又陷入了新的迷思:遍历一遍是O(n),如果用二分只要O(logn)。用二分写了一大半后,发现数组不是sorted!那光是sort就要O(nlogn)了。
然后很快用正确的方法写出来了。
好吧,教训就是要认真读题目,不要盲目敲代码。

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        answer = 0
        sum_value = sum(arr[:k])
        if sum_value >= k * threshold:
            answer += 1
        for i in range(len(arr) - k):
            sum_value += arr[i+k] - arr[i]
            if sum_value >= k * threshold:
                answer += 1
        return answer

第三题很简单,简单到不像第三题的难度。

class Solution:
    def angleClock(self, hour: int, minutes: int) -> float:
        mi = minutes / 60 * 360
        hr = (hour + minutes / 60) / 12 * 360
        temp = abs(hr - mi)
        if temp <= 180:
            return temp
        else:
            return 360 - temp

第四题说难不算很难,我一上来就想用bfs,也确实用bfs做出来的。但说简单也不算很简单,有一些细节的地方要注意,并且我一直超时,折腾了很久。直到找到了那个貌似不起眼的错误。

第四题的思路就是把每一步可以达到的所有点给找出来。第1步可以到的就是起点,第2步可以到的是起点的前一位(不存在)、后一位和所有值相同的其他位置,第3步就是第2步所有点的前一位、后一位和所有值相同的其他位置……以此类推

为了求值相同的位置,我们用一个词典把值作为key,把数组的index装在一个set或者list里作为value。

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        # 建立字典,用set类型或者list类型都是可以的
        mapping = defaultdict(set)
        for i, num in enumerate(arr):
            mapping[num].add(i)

        # 判断特例:数组只有一个元素的情况
        if len(arr) == 1:
            return 0

        # 然后是常规的bfs写法,count记录第几步,queue记录每一步所有的位置,开始当然只有[0],new_queue表示下一步有哪些位置
        count = 0
        queue = [0]
        while queue:
            count += 1
            new_queue = []
            # 对queue里的每一个值,都可以走到3个地方,前一位、后一位和值相同的其他位置
            for i in queue:
                # 情况一:值相同的其他位置。这里有个小技巧就是如果处理过某个值,就把字段里的这个值的key-value对删掉,以后就不要重复处理了。当然另一个做法是你可以设一个visited集合,放处理过的值。我觉得删key-value比设visited集合要好一些,开销更小。
                if arr[i] in mapping:
                    for j in mapping[arr[i]]:
                        if j == len(arr) - 1:
                            return count
                        new_queue.append(j)
                    # !!!我的问题就是漏写了这句,导致一直超时。注意是值相同的“其它”位置,要把原位置去掉
                    new_queue.remove(i)
                    del mapping[arr[i]]
                # 情况二:前一位。
                if i + 1 < len(arr) and arr[i+1] in mapping:
                    if i + 1 == len(arr) - 1:
                        return count
                    new_queue.append(i+1)
                # 情况三:后一位。
                if i - 1 >= 0 and arr[i-1] in mapping:
                    new_queue.append(i-1)
                # 还有个小技巧是,情况二和情况三要写在情况一后面,这样的话如果当前位置的前一位/后一位和当前位置值相同,你就不会在new_queue里重复记录。因为在情况一的时候已经del mapping[arr[i]]了。当然如果把情况一写在后面,也不影响结果正确性,无非时间开销大一点,并且也能提交成功,属于很微小的影响。
                # 当然如果你用的是设visited集合的方法,就没有这个问题,也不需要这个小技巧。


            queue = new_queue
2
展开全部 14 讨论