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 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习