Python程式：計算可滿足的轉讓請求數量

Python 伺服器端程式設計程式設計

假設有n個宿舍房間，編號從0到n-1。宿舍裡的學生想要換房間，他們為此提出了幾個請求。沒有空餘的宿舍床位，只有當另一個學生替換想要搬遷的學生時，才會處理轉讓請求。因此，給定這些請求，我們必須找出可以滿足多少個請求。

例如，如果輸入為n = 3，requests = [[0,2],[1,0],[2,1]]，則輸出為3。

0號房間的學生搬到2號房間。

1號房間的學生搬到0號房間。

2號房間的學生搬到1號房間。

為了解決這個問題，我們將遵循以下步驟：

對於k從requests大小-1到0迴圈遞減，執行：
- 對於所有(0到requests大小和k)的組合c，執行：
  - d := 一個大小為n，值為0的新陣列
  - 對於c中的每個i，執行：
    - d[requests[i, 0]] := d[requests[i, 0]] - 1
    - d[requests[i, 1]] := d[requests[i, 1]] + 1
  - 如果d中的所有元素都不為真（即都為0），則
    - 返回k
返回0

示例

讓我們看看下面的實現來更好地理解。

from itertools import combinations
def solve(n, requests):
   for k in range(len(requests), 0, -1):
      for c in combinations(range(len(requests)), k):
         d = [0] * n
         for i in c:
            d[requests[i][0]] -= 1
            d[requests[i][1]] += 1
         if not any(d):
            return k
   return 0

print(solve(3, [[0,2],[1,0],[2,1]]))

輸入

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

輸出

Arnab Chakraborty

更新於：2021年10月7日

63 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習