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 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習