Python程序：检查给定条件下将处理的请求数量

假设我们有一份请求列表，每个列表元素包含 [uid, time_sec] （uid是用户ID，time_sec是时间戳）。这表示用户ID为uid的用户在时间戳time_sec向网站发出了请求。我们还有两个值u和g，u表示在任何小于60秒的时间段内，给定uid允许的最大请求数，g表示在任何小于60秒的时间段内，全局允许的最大请求数。现在，如果我们想逐个处理每个请求并对其进行速率限制，如果多个用户同时发出请求，则将优先处理uid较小的请求，否则该请求将被丢弃。我们必须找到将成功处理的请求总数。

因此，如果输入类似于 requests = [[0, 1],[1, 2],[1,3]] u = 1 g = 5，则输出将为2，因为用户0和1可以在时间1和2发送请求，但用户1的第二个请求将不会被处理，因为一个用户在60秒内最多只能发送1个请求。

为了解决这个问题，我们将遵循以下步骤：

  • last := 一个空的映射
  • total := 一个空的双端队列
  • windowtime := 60
  • 根据时间对请求进行排序，如果时间相同，则根据uid进行排序
  • amount := 0
  • 对于requests中的每个r，执行以下操作：
    • [uid, time] := r
    • 当total的大小>0并且total[0] + windowtime <= time时，执行以下操作：
      • 删除total的左侧元素
    • 当last[uid]的大小>0并且last[uid, 0] + windowtime <= time时，执行以下操作：
      • 删除last[uid]的左侧元素
    • 如果total的大小< g并且last[uid]的大小< u，则：
      • 将time插入last[uid]的末尾
      • 将time插入total的末尾
      • amount := amount + 1
  • 返回amount

让我们来看下面的实现，以便更好地理解：

示例

在线演示

from collections import defaultdict, deque
class Solution:
   def solve(self, requests, u, g):
      last = defaultdict(deque)
      total = deque()

      windowtime = 60
      requests.sort(key=lambda x: [x[1], x[0]])

      amount = 0
      for r in requests:
         uid, time = r

         while len(total) > 0 and total[0] + windowtime <= time:
            total.popleft()

         while len(last[uid]) > 0 and last[uid][0] + windowtime <= time:
            last[uid].popleft()

         if len(total) < g and len(last[uid]) < u:
            last[uid].append(time)
            total.append(time)
            amount += 1
      return amount
     
ob = Solution()
requests = [[0, 1],[1, 2],[1,3]]
u = 1
g = 5
print(ob.solve(requests, u, g))

输入

[[0, 1],[1, 2],[1,3]], 1, 5

输出

2

更新于：2020年12月3日

浏览量：355

开启您的职业生涯

完成课程获得认证

开始学习
广告
© . All rights reserved.