Pythonで空席と空席の間の最大距離を見つけるプログラム

シートと呼ばれる0と1のみのリストがあるとします。ここで、seats[i]は座席を表します。 1の場合は占有され、それ以外の場合は解放されます。少なくとも1つのフリーシートと少なくとも1つの占有シートがあり、フリーシートから最も近い占有シートまでの最大距離を見つける必要があります。

したがって、入力が座席=[1、0、1、0、0、0、1]の場合、座席の座席[4]を占有できるため、出力は2になり、距離は2になります。

これを解決するには、次の手順に従います-

• res：=0

• 最後：=-1

• n：=シートのサイズ

• 0からn-1の範囲のiの場合、実行

  • Seats [i]が1の場合、

    • res：=resの最大値および（最後の場合はi <0、それ以外の場合は（i-last）/ 2のフロア）

    • 最後：=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