检查是否可以在 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

更新于: 2021-01-19

65 次查看

启动您的 职业生涯

通过完成课程获得认证

开始
广告