สมมติว่าเรามีรายการที่นั่งที่มีเลข 0 และ 1 เท่านั้น โดยที่ seat[i] หมายถึงที่นั่ง เมื่อเป็น 1 ก็จะถูกครอบครอง มิฉะนั้น จะว่าง มีที่นั่งว่างอย่างน้อยหนึ่งที่นั่งและที่นั่งว่างอย่างน้อยหนึ่งที่นั่ง เราต้องหาระยะทางสูงสุดจากที่นั่งว่างไปยังที่นั่งว่างที่ใกล้ที่สุด
ดังนั้น หากอินพุตเหมือนกับที่นั่ง =[1, 0, 1, 0, 0, 0, 1] เอาต์พุตจะเป็น 2 เนื่องจากเราสามารถครอบครองที่นั่งได้[4] ระยะห่างคือ 2
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
res :=0
-
สุดท้าย :=-1
-
n :=ขนาดที่นั่ง
-
สำหรับฉันอยู่ในช่วง 0 ถึง n - 1 ทำ
-
ถ้าที่นั่ง[i] คือ 1 แล้ว
-
res :=สูงสุดของ res และ (i ถ้าสุดท้าย <0 มิฉะนั้น ชั้นของ (i-last)/2)
-
สุดท้าย :=ฉัน
-
-
-
คืนค่าสูงสุดของ 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
