N 天后的牢房

标签: 位运算 数组 哈希表 数学

难度: Medium

监狱中 8 间牢房排成一排，每间牢房可能被占用或空置。

每天，无论牢房是被占用或空置，都会根据以下规则进行变更：

  • 如果一间牢房的两个相邻的房间都被占用或都是空的，那么该牢房就会被占用。
  • 否则，它就会被空置。

注意：由于监狱中的牢房排成一行，所以行中的第一个和最后一个牢房不存在两个相邻的房间。

给你一个整数数组 cells ，用于表示牢房的初始状态：如果第 i 间牢房被占用，则 cell[i]==1，否则 cell[i]==0 。另给你一个整数 n 。

请你返回 n 天后监狱的状况（即，按上文描述进行 n 次变更）。

示例 1：

输入：cells = [0,1,0,1,1,0,0,1], n = 7
输出：[0,0,1,1,0,0,0,0]
解释：下表总结了监狱每天的状况：
Day 0: [0, 1, 0, 1, 1, 0, 0, 1]
Day 1: [0, 1, 1, 0, 0, 0, 0, 0]
Day 2: [0, 0, 0, 0, 1, 1, 1, 0]
Day 3: [0, 1, 1, 0, 0, 1, 0, 0]
Day 4: [0, 0, 0, 0, 0, 1, 0, 0]
Day 5: [0, 1, 1, 1, 0, 1, 0, 0]
Day 6: [0, 0, 1, 0, 1, 1, 0, 0]
Day 7: [0, 0, 1, 1, 0, 0, 0, 0]

示例 2：

输入：cells = [1,0,0,1,0,0,1,0], n = 1000000000
输出：[0,0,1,1,1,1,1,0]

提示：

  • cells.length == 8
  • cells[i] 为 0 或 1
  • 1 <= n <= 109

Submission

运行时间: 24 ms

内存: 0.0 MB

class Solution:
    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:
        indexState = {}
        cycle = 0
        old_cells = cells
        for i in range(n):
            new_cells = [-1]*len(cells)
            for j in range(len(cells)):
                if j-1 < 0 or j+1 >= len(cells):
                    new_cells[j] = 0
                    continue
                else:
                    new_cells[j] = 0
                if (old_cells[j-1] == 0 and old_cells[j+1] == 0) or (old_cells[j-1] == 1 and old_cells[j+1] == 1):
                    new_cells[j] = 1
                else:
                    new_cells[j] = 0
            old_cells = new_cells
            # cells_state = "".join(map(str, new_cells))
            cells_state = tuple(new_cells)
            if cells_state not in indexState:
                indexState[cells_state] = i+1
                cycle += 1
            else:
                break
        states = list(indexState.keys())
        # print(states, len(states), n, cycle)
        return states[-1] if n == cycle else states[n%cycle-1]

Explain

题解通过模拟牢房状态的变化，并使用哈希表来检测循环出现的状态，从而优化长周期的模拟过程。首先，算法模拟了牢房状态的每日变化，根据题目规则更新每个牢房。然后，使用一个元组来存储每日牢房的状态，用哈希表记录每个状态第一次出现的天数。如果某个状态已经在哈希表中，则意味着找到了循环周期，可以停止模拟。最后，根据天数 n 与周期长度，利用取余操作确定最终的牢房状态。

时间复杂度: O(1)

空间复杂度: O(1)

# 定义解决方案类

class Solution:
    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:
        indexState = {}  # 用于记录每种状态第一次出现的日子
        cycle = 0  # 记录状态变化的周期
        old_cells = cells  # 当前牢房的状态
        for i in range(n):  # 模拟n天的状态变化
            new_cells = [-1]*len(cells)  # 初始化新的一天的牢房状态
            for j in range(len(cells)):  # 更新每个牢房的状态
                if j-1 < 0 or j+1 >= len(cells):  # 特殊处理第一个和最后一个牢房
                    new_cells[j] = 0
                    continue
                # 根据相邻牢房的状态更新当前牢房状态
                new_cells[j] = 1 if (old_cells[j-1] == old_cells[j+1]) else 0
            old_cells = new_cells  # 更新旧状态为当前状态
            cells_state = tuple(new_cells)  # 将状态转换为元组以便存储和比较
            if cells_state not in indexState:  # 如果状态是首次出现
                indexState[cells_state] = i+1
                cycle += 1  # 更新周期
            else:  # 如果状态重复，说明找到了循环
                break
        states = list(indexState.keys())  # 获取所有独特的状态
        # 根据n和周期计算最终状态
        return states[-1] if n == cycle else states[n%cycle-1]

Explore

根据题目的规则，牢房状态的更新依赖于相邻两个牢房的状态。对于第一个和最后一个牢房，由于它们分别只有右侧和左侧邻居，不存在两个有效的相邻牢房，因此在模拟状态更新时，无法按照正常规则进行更新。为了简化处理，直接将这两个牢房的状态设置为0。这种处理方式符合题目中对边界情况的默许规则，即边界外没有牢房被视为状态为0。

在题解中，使用哈希表来记录每一个牢房状态第一次出现的天数。每次生成新的牢房状态后，会将其转换为元组形式并检查这个状态是否已存在于哈希表中。如果这个状态之前已被记录，那么意味着状态开始重复，从而形成了一个循环。由于状态重复出现的那一天与这一状态首次出现的天数之间，牢房的变化状态将会周期性重复，因此一旦检测到重复状态，就可以确定状态的循环周期已经形成。

一旦确定了循环周期，题解首先计算出循环开始前非循环状态的天数（即首次出现重复状态的天数与循环周期的关系）。当总天数n小于循环开始的天数时，直接从记录的状态中获取第n天的状态。如果n大于或等于循环开始的天数，首先确定循环周期的长度，然后使用 n 对循环周期长度进行取余操作，得到的结果指出在循环周期中的具体位置。最后，根据这个位置从循环周期中的状态列表获取最终的牢房状态。