Python程序：检查所有人是否都能获得座位

假设我们有一个数字n，有n个人正在寻找座位，我们还有一个位列表，其中1表示已占用座位，0表示空座位。不允许两个人坐在相邻的位置，因此我们必须检查是否所有n个人都能找到座位。

因此，如果输入类似于n = 2，seats = [1, 0, 0, 0, 1, 0, 0]，则输出为True，因为他们可以坐在索引2和6。

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

• 在seats的开头插入0，并在seats的末尾插入[0, 1]
• res := 0，gap := 0
• 对于seats中的每个i，执行：
  • 如果i等于0，则
    • gap := gap + 1
  • 否则，当gap > 0时，则
    • res := res + floor((gap - 1)/2)
    • gap := 0
• 如果res >= n则返回true，否则返回false

示例

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

def solve(n, seats):
   seats = [0] + seats + [0, 1]
   res = 0
   gap = 0
   for i in seats:
      if i == 0:
         gap += 1
      elif gap > 0:
         res += (gap - 1) // 2
         gap = 0
   return res >= n

n = 2
seats = [1, 0, 0, 0, 1, 0, 0]
print(solve(n, seats))

输入

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

输出

True

Arnab Chakraborty

更新于：2021年10月14日

467 次浏览

开启你的职业生涯

完成课程获得认证

开始学习