檢查是否可以在 Python 中使用不同的鈔票為客戶佇列提供服務

假設我們有一個名為 notes 的陣列，表示排隊等候的客戶持有的不同面值的盧比鈔票。他們都在等待購買價值 50 盧比的票。這裡可能的鈔票是 [50、100 和 200]。我們必須檢查是否可以按順序向人們出售門票，最初我們手中有 0 盧比。

因此，如果輸入類似於 notes = [50, 50, 100, 100]，則輸出將為 True，對於前兩個，我們不需要返回任何內容，但現在我們有兩張 50 盧比的鈔票。因此，對於最後兩個，我們可以退還他們 50 盧比的鈔票並按順序出售所有門票。

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

• freq := 一個空對映
• i := 0
• 當 i < notes 的大小 時，執行以下操作：
  • 如果 notes[i] 等於 50，則
    • freq[50] := freq[50] + 1
  • 否則，當 notes[i] 等於 100 時，則
    • freq[100] := freq[100] + 1
    • 如果 freq[50] 為 0，則
      • 退出迴圈
    • freq[50] := freq[50] - 1
  • 否則，
    • 如果 freq[100] > 0 且 freq[50] > 0，則
      • freq[100] := freq[100] - 1
      • freq[50] := freq[50] - 1
    • 否則，當 freq[50] >= 3 時，則
      • freq[50] := freq[50] - 3
    • 否則，
      • 退出迴圈
  • i := i + 1
• 如果 i 等於 notes 的大小，則
  • 返回 True
• 返回 False

示例

讓我們看看以下實現以獲得更好的理解：

 即時演示

from collections import defaultdict
def solve(notes):
   freq = defaultdict(int)
   i = 0
   while i < len(notes):
      if notes[i] == 50:
         freq[50] += 1
      elif notes[i] == 100:
         freq[100] += 1
         if freq[50] == 0:
            break
         freq[50] -= 1
      else:
         if freq[100] > 0 and freq[50] > 0:
            freq[100] -= 1
            freq[50] -= 1
         elif freq[50] >= 3:
            freq[50] -= 3
         else:
            break
      i += 1
   if i == len(notes):
      return True
   return False
notes = [50, 50, 100, 100]
print(solve(notes))

輸入

[50, 50, 100, 100]

輸出

True

Arnab Chakraborty

更新於: 2021-01-19

65 次檢視

啟動您的 職業生涯

透過完成課程獲得認證

開始