Python程式：查詢監獄牢房在k天后的狀態

假設我們有一個二進位制列表（列表中包含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]，我們可以注意到第一個和最後一個索引永遠不會被佔用，因為它們永遠不可能有兩個鄰居。

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

• 定義一個函式next_day_state()。這將接收cells作為引數
• new_cells := cells的副本
• new_cells[0] := 0, new_cells[7] := 0
• 對於j從1到6，執行以下操作
  • 如果cells[j - 1]與cells[j + 1]相同，則
    • new_cells[j] := 1
  • 否則，
    • new_cells[j] := 0
• 返回new_cells
• 從主方法執行以下操作
• seen := 一個新的對映
• flag := False, i := 0
• 當i < N時，執行以下操作
  • ns := next_day_state(cells)
  • 如果ns不在seen中，則
    • 將ns標記為已見
  • 否則，
    • flag := True
    • 退出迴圈
  • cells := ns
  • i := i + 1
• 如果flag為真，則
  • N := N mod (已見項的數量)
  • i := 0
  • 當i < N且不為零時，執行以下操作
    • ns := next_day_state(cells)
    • i := i + 1
    • cells := ns
• 返回cells

讓我們看看以下實現以獲得更好的理解

示例

線上演示

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]

Arnab Chakraborty

更新於: 2020年11月26日

327 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習