当前位置:   article > 正文

[英雄星球六月集训LeetCode解题日报] 第16日 队列

[英雄星球六月集训LeetCode解题日报] 第16日 队列

一、 933. 最近的请求次数

链接: 933. 最近的请求次数

1. 题目描述

写一个 RecentCounter 类来计算特定时间范围内最近的请求。

请你实现 RecentCounter 类:

RecentCounter() 初始化计数器,请求数为 0 。
int ping(int t) 在时间 t 添加一个新请求,其中 t 表示以毫秒为单位的某个时间,并返回过去 3000 毫秒内发生的所有请求数(包括新请求)。确切地说,返回在 [t-3000, t] 内发生的请求数。
保证 每次对 ping 的调用都使用比之前更大的 t 值。

2. 思路分析

队列模拟即可。
每次插入后把队首所有过远数据出队。
然后返回队长度。

3. 代码实现

class RecentCounter:

    def __init__(self):
        self.q = deque()

    def ping(self, t: int) -> int:
        q = self.q
        q.append(t)
        while q[0] < t - 3000:
            q.popleft()
        return len(q)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

二、 1700. 无法吃午餐的学生数量

链接: 1700. 无法吃午餐的学生数量

1. 题目描述

学校的自助午餐提供圆形和方形的三明治,分别用数字 0 和 1 表示。所有学生站在一个队列里,每个学生要么喜欢圆形的要么喜欢方形的。
餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个 栈 里,每一轮:

如果队列最前面的学生 喜欢 栈顶的三明治,那么会 拿走它 并离开队列。
否则,这名学生会 放弃这个三明治 并回到队列的尾部。
这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。

给你两个整数数组 students 和 sandwiches ,其中 sandwiches[i] 是栈里面第 i​​​​​​ 个三明治的类型(i = 0 是栈的顶部), students[j] 是初始队列里第 j​​​​​​ 名学生对三明治的喜好(j = 0 是队列的最开始位置)。请你返回无法吃午餐的学生数量。

2. 思路分析

这题队列模拟是N^2啊,数据规模不大就是了。最好还是计算。

  • 先计算学生数量n,两种学生数量分别为a,b.
  • 由于学生是循环的,前min(a,b)的三明治一定会被拿光;
  • 拿的过程中,不管当前三明治是哪种,只要这种学生没用完,这个三明治一定会被拿走。
  • 因此,我们从头开始数,直到当前三明治计数为此种学生总数+1,即学生用光了拿不了这个,
  • 那么剩下的三明治就没人能吃。
  • 由于三明治是0,1我们可以用一个长度2的数组储存计数,学生同样。

3. 代码实现

class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
        """
        先计算学生数量n,两种学生数量分别为a,b.
        由于学生是循环的,前min(a,b)的三明治一定会被拿光;
        拿的过程中,不管当前三明治是哪种,只要这种学生没用完,这个三明治一定会被拿走。
        因此,我们从头开始数,直到当前三明治计数为此种学生总数+1,即学生用光了拿不了这个,
        那么剩下的三明治就没人能吃。
        由于三明治是0,1我们可以用一个长度2的数组储存计数,学生同样。
        """
        stu=Counter(students)
        n = len(students)
        san=[0,0]
        for i in range(n):
            s = sandwiches[i]
            san[s] += 1
            if san[s] == stu[s]+1:
                return n - i                
        return 0
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

三、 2073. 买票需要的时间

链接: 2073. 买票需要的时间

1. 题目描述

有 n 个人前来排队买票,其中第 0 人站在队伍 最前方 ,第 (n - 1) 人站在队伍 最后方 。

给你一个下标从 0 开始的整数数组 tickets ,数组长度为 n ,其中第 i 人想要购买的票数为 tickets[i] 。

每个人买票都需要用掉 恰好 1 秒 。一个人 一次只能买一张票 ,如果需要购买更多票,他必须走到 队尾 重新排队(瞬间 发生,不计时间)。如果一个人没有剩下需要买的票,那他将会 离开 队伍。

返回位于位置 k(下标从 0 开始)的人完成买票需要的时间(以秒为单位)。

2. 思路分析

这题也不用队列模拟,直接计算很好想。
把k买完之前的人买票总时间加起来即可。
位于前边的人消耗的时间不会超过k本人,因为k买到就走了;位于后边的人同样不会,而且比k少一轮。

3. 代码实现

class Solution:
    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
        """第k个人要买a张票,
        我们分析排在他前边的人,要买b张票,
            如果b<=a,那么这些人花的时间就是b。
            如果b>a,那么这些人花了a之后,k就买到了,也就不计数。
            因此这些人花的时间是min(tickets[i], a)
        排在他后边的人类似,但是当k自己买到后,当前队列也不需要计算了
            因此是min(tickets[i], a-1)
        """
        a = tickets[k]
        s = 0
        for i in range(k+1):
            s += min(tickets[i], a)
        
        for i in range(k+1,len(tickets)):
            s += min(tickets[i], a-1)
        return s
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

四、239. 滑动窗口最大值

链接: 239. 滑动窗口最大值

1. 题目描述

给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

2. 思路分析

单调队列模板题。参考我的[python刷题模板] 单调队列
滑窗右移时,新数x入队,把队尾所有小于x的数据全弹出丢弃,这些数据对后续滑窗的贡献不会超过x。
然后判断一下队首是否出窗需要弹出,剩下的队首就是答案。

3. 代码实现

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        """单调队列模板
        维护单调递减队列,
        入队时,把队尾小于本数的全干掉,这些数对后续窗口的贡献不会超过本数。
        判断队首距离当前超过k则弹出,剩下的队首就是答案。        
        """
        q = deque()
        for i in range(k):
            while q and nums[i]>=nums[q[-1]]:
                q.pop()
            q.append(i)
        ans = []
        ans.append(nums[q[0]])
        for i in range(k,len(nums)):
            while q and nums[i]>=nums[q[-1]]:
                q.pop()
            q.append(i)
            if q[0] <= i-k:
                q.popleft()
            ans.append(nums[q[0]])
        return ans
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

五、参考链接

声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号