โปรแกรมค้นหาสถานะห้องขังหลัง k วันใน python

สมมติว่าเรามีรายการไบนารี (1 และ 0 ในรายการ) และค่าอื่น k แต่ละค่าเป็น nums แสดงถึงสถานะของเซลล์ในเรือนจำ โดยที่ 1 หมายถึงเซลล์ที่ถูกครอบครอง และ 0 หมายถึงเซลล์ว่าง ในแต่ละวันเมื่อเซลล์มีเซลล์ที่อยู่ติดกันสองเซลล์ซึ่งว่างทั้งสองเซลล์หรือว่างทั้งสองเซลล์ เซลล์นั้นจะถูกเซลล์ว่างอยู่ มิฉะนั้นจะว่างเปล่า เลยต้องหาสภาพห้องขังหลังจากผ่านไป k วัน

ดังนั้น หากอินพุตเป็น nums =[1, 0, 1, 0, 0, 0, 0, 0] k =1 ผลลัพธ์จะเป็น [0, 1, 1, 0, 1, 1, 1, 0] เนื่องจากเราสามารถสังเกตได้ว่าดัชนีแรกและดัชนีสุดท้ายไม่สามารถครอบครองได้เนื่องจากไม่มีเพื่อนบ้าน 2 ราย

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

• กำหนดฟังก์ชัน next_day_state() นี้จะใช้เวลาเซลล์
• new_cells :=สำเนาของเซลล์
• new_cells[0] :=0, new_cells[7] :=0
• สำหรับ j ในช่วง 1 ถึง 6 ให้ทำ
  • ถ้าเซลล์[j - 1] เหมือนกับเซลล์[j + 1] ดังนั้น
    • new_cells[j] :=1
  • มิฉะนั้น
    • new_cells[j] :=0
• ส่งคืนเซลล์ใหม่
• จากวิธีหลัก ให้ทำดังนี้:
• เห็น :=แผนที่ใหม่
• flag :=เท็จ ผม :=0
• ในขณะที่ฉัน
• ns :=next_day_state(เซลล์)
• ถ้าไม่เห็น ns แล้ว
  • ทำเครื่องหมายว่าเห็นแล้ว
• มิฉะนั้น
  • flag :=จริง
  • ออกมาจากวงจร
• เซลล์ :=ns
• ผม :=ผม + 1

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

ตัวอย่าง

import copy
class Solution:
   def next_day_state(self, cells):
      new_cells = copy.copy(cells)
      new_cells[0] = 0
      new_cells[7] = 0
      for j in range(1, 7):
         if cells[j - 1] == cells[j + 1]:
            new_cells[j] = 1
         else:
            new_cells[j] = 0
      return new_cells

   def solve(self, cells, N):
      seen = dict()
      flag, i = False, 0

      while i < N:
         ns = self.next_day_state(cells)
         if tuple(ns) not in seen:
            seen[tuple(ns)] = True
         else:
            flag = True
            break
         cells = ns
         i += 1

      if flag:
         N = N % len(seen)
         i = 0
         while i < N:
            ns = self.next_day_state(cells)
            i += 1
            cells = ns
      return cells

ob = Solution()
nums = [1, 0, 1, 0, 0, 0, 0, 0]
k = 1
print(ob.solve(nums, k))

อินพุต

[4, 7, 2, 5], 6

ผลลัพธ์

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