Python程式：查詢空座位和佔用座位之間的最大距離

假設我們有一個列表seats，其中只包含0和1，seats[i]表示一個座位。當它為1時，表示佔用，否則為空閒。至少有一個空座位和至少一個佔用座位，我們需要找到從一個空座位到最近的佔用座位的最大距離。

因此，如果輸入類似seats = [1, 0, 1, 0, 0, 0, 1]，則輸出將為2，因為我們可以佔用seats[4]，則距離為2。

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

  • res := 0

  • last := -1

  • n := seats的大小

  • 對於範圍從0到n-1的i，執行以下操作：

    • 如果seats[i]為1，則：

      • res := res和(如果last < 0則為i，否則為(i-last)/2的下取整)中的最大值

      • last := i

  • 返回res和(n-last-1)中的最大值

示例

讓我們看看下面的實現，以便更好地理解

def solve(seats):
   res, last, n = 0, -1, len(seats)
   for i in range(n):
      if seats[i]:
         res = max(res, i if last < 0 else (i - last) // 2)
         last = i
   return max(res, n - last - 1)

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

輸入

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

輸出

2

更新於: 2021年10月12日

425 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

開始學習
廣告