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.