โปรแกรมเช็คว่าทุกคนสามารถนั่งได้หรือไม่ใน Python

สมมติว่าเรามีหมายเลข n มีคนจำนวน n ค้นหาที่นั่ง เรายังมีรายการของบิตที่ 1 หมายถึงที่นั่งที่ถูกครอบครองแล้ว และ 0 หมายถึงที่นั่งว่าง ไม่มีใครนั่งติดกันสองคนได้ เราจึงต้องตรวจสอบว่าคนทั้ง n หาที่นั่งได้หรือไม่

ดังนั้น หากอินพุตเป็น n =2 ที่นั่ง =[1, 0, 0, 0, 1, 0, 0] เอาต์พุตจะเป็น True เพราะสามารถนั่งที่ดัชนี 2 และ 6

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ใส่ 0 ที่จุดเริ่มต้นของที่นั่งและใส่ [0, 1] ที่ส่วนท้ายของที่นั่ง
• res :=0, gap :=0
• สำหรับ i แต่ละคนในที่นั่ง ทำ
  • ถ้าฉันเหมือนกับ 0 แล้ว
    • ช่องว่าง :=ช่องว่าง + 1
  • มิฉะนั้น เมื่อช่องว่าง> 0 แล้ว
    • res :=res + floor of (ช่องว่าง - 1)/2
    • ช่องว่าง :=0
• คืนค่า จริง เมื่อ res>=n มิฉะนั้น เท็จ

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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