原文链接: https://leetcode-cn.com/problems/prison-cells-after-n-days
英文原文
There are 8 prison cells in a row and each cell is either occupied or vacant.
Each day, whether the cell is occupied or vacant changes according to the following rules:
- If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied.
- Otherwise, it becomes vacant.
Note that because the prison is a row, the first and the last cells in the row can't have two adjacent neighbors.
You are given an integer array cells where cells[i] == 1 if the ith cell is occupied and cells[i] == 0 if the ith cell is vacant, and you are given an integer n.
Return the state of the prison after n days (i.e., n such changes described above).
Example 1:
Input: cells = [0,1,0,1,1,0,0,1], n = 7 Output: [0,0,1,1,0,0,0,0] Explanation: The following table summarizes the state of the prison on each day: 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]
Example 2:
Input: cells = [1,0,0,1,0,0,1,0], n = 1000000000 Output: [0,0,1,1,1,1,1,0]
Constraints:
cells.length == 8cells[i]is either0or1.1 <= n <= 109
中文题目
8 间牢房排成一排，每间牢房不是有人住就是空着。
每天，无论牢房是被占用或空置，都会根据以下规则进行更改：
- 如果一间牢房的两个相邻的房间都被占用或都是空的，那么该牢房就会被占用。
- 否则，它就会被空置。
（请注意，由于监狱中的牢房排成一行，所以行中的第一个和最后一个房间无法有两个相邻的房间。）
我们用以下方式描述监狱的当前状态：如果第 i 间牢房被占用，则 cell[i]==1，否则 cell[i]==0。
根据监狱的初始状态，在 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 == 8cells[i]的值为0或11 <= N <= 10^9
通过代码
官方题解
方法 1：模拟
想法
模拟每一天监狱的状态。
由于监狱最多只有 256 种可能的状态，所以状态一定会快速的形成一个循环。我们可以当状态循环出现的时候记录下循环的周期 t 然后跳过 t 的倍数的天数。
算法
实现一个简单的模拟，每次迭代一天的情况。对于每一天，我们减少剩余的天数 N，然后将监狱状态改变成（state -> nextDay(state)）。
如果我们到达一个已经访问的状态，并且知道距当前过去了多久，设为 t，那么由于这是一个循环，可以让 N %= t。这确保了我们的算法只需要执行 $O(2^{\text{cells.length}})$ 步。
[]class Solution { public int[] prisonAfterNDays(int[] cells, int N) { Map<Integer, Integer> seen = new HashMap(); // state = integer representing state of prison int state = 0; for (int i = 0; i < 8; ++i) { if (cells[i] > 0) state ^= 1 << i; } // While days remaining, simulate a day while (N > 0) { // If this is a cycle, fast forward by // seen.get(state) - N, the period of the cycle. if (seen.containsKey(state)) { N %= seen.get(state) - N; } seen.put(state, N); if (N >= 1) { N--; state = nextDay(state); } } // Convert the state back to the required answer. int[] ans = new int[8]; for (int i = 0; i < 8; ++i) { if (((state >> i) & 1) > 0) { ans[i] = 1; } } return ans; } public int nextDay(int state) { int ans = 0; // We only loop from 1 to 6 because 0 and 7 are impossible, // as those cells only have one neighbor. for (int i = 1; i <= 6; ++i) { if (((state >> (i-1)) & 1) == ((state >> (i+1)) & 1)) { ans ^= 1 << i; } } return ans; } }
[]class Solution(object): def prisonAfterNDays(self, cells, N): def nextday(cells): return [int(i > 0 and i < 7 and cells[i-1] == cells[i+1]) for i in xrange(8)] seen = {} while N > 0: c = tuple(cells) if c in seen: N %= seen[c] - N seen[c] = N if N >= 1: N -= 1 cells = nextday(cells) return cells
复杂度分析
- 时间复杂度：$O(2^N)$，其中 $N$ 是监狱房间的个数。
- 空间复杂度：$O(2^N * N)$。
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 14638 | 40586 | 36.1% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
