class Solution {
public:
vector<int> prisonAfterNDays(vector<int>& cells, int n) {
}
};
957. N 天后的牢房
监狱中 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 == 8cells[i] 为 0 或 11 <= n <= 109原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 2.1 MB, 提交时间: 2023-09-07 00:08:43
func prisonAfterNDays(cells []int, N int) []int {
N %= 14
if N == 0 {
N = 14
}
for i := 0; i < N; i++ {
t := make([]int, 8)
for j := 1; j < 7; j++ {
if cells[j-1] == cells[j+1] {
t[j] = 1
}
}
cells = t
}
return cells
}
java 解法, 执行用时: 1 ms, 内存消耗: 40.4 MB, 提交时间: 2023-09-07 00:08:25
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;
}
}
python3 解法, 执行用时: 36 ms, 内存消耗: 16.1 MB, 提交时间: 2023-09-07 00:08:02
class Solution:
def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:
def nextday(cells):
return [int(i > 0 and i < 7 and cells[i-1] == cells[i+1])
for i in range(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