957.N天后的牢房

N 天后的牢房

8 间牢房排成一排，每间牢房可能被占用或空置。根据规则变更 N 天后返回牢房状态。

规则：若一间牢房的两个相邻牢房都被占用或都是空的，则该牢房下一状态为占用；否则为空。

示例 1:

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

提示:

• cells.length == 8
• cells[i] 为 0 或 1
• 1 <= n <= 10^9

解析

状态每 14 天会循环。使用数学方法快速跳过完整的循环周期。

var prisonAfterNDays = function (cells, n) {
  const seen = new Map();
  let isFirst = true;

  while (n > 0) {
    const key = cells.join('');
    if (seen.has(key) && isFirst) {
      n %= seen.get(key) - n;
      isFirst = false;
    }
    if (n <= 0) break;
    seen.set(key, n);

    const next = new Array(8).fill(0);
    for (let i = 1; i < 7; i++) {
      next[i] = cells[i - 1] === cells[i + 1] ? 1 : 0;
    }
    cells = next;
    n--;
  }

  return cells;
};

时间复杂度 O(2^8 * n)，空间复杂度 O(2^8)。