Prison Cells After N Days

这是我第一次参加 LeetCode (力扣) 的每月挑战题组，希望留下点笔记，大家可以参考和互相讨论。😃

第三天问：

现在有 1行8个 囚犯监仓，每个仓只可以有一人住或者沒人住。 每天，这些监仓都会根据以下规则決定有沒有人住进去:

如果在前一天，该监仓前后都有人住 (或者都沒人住)，该监仓这一天便一定有人住。否则，它这天一定沒有人住。

题目例子 (引用自LeetCode)：

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] Notes: cells.length == 8 cells[i] is in {0, 1} 1 <= N <= 10^9

解题思路：

一开始，好像挺容易的，用 for-loop 不就可以做到了吗？先迭代日数 (N)，如果日数为零就返回 cells 自己 (不够一天不用换监仓)；如果 N > 0，那就在每一天根据前一天的排列判断每个监仓有沒有人住，纪录好了就把它换成新的监仓列表就完成了。

失败代码 (时间复杂度：O(8N) = O(N))

class Solution: def prisonAfterNDays(self, cells: List[int], N: int) -> List[int]: if N == 0: return cells for day in range(N): new_cells = [] for i in range(len(cells)): if i == 0 or i == 7: new_cells.append(0) elif cells[i - 1] == cells[i + 1]: new_cells.append(1) else: new_cells.append(0) cells = new_cells return cells

但是，居然报超时了?! 我们看到，题目要求的 N 可以是很大的 (N $⩽$ 10⁹)。所以，为了減低时间复杂度，我做了個实验： 细心的读者可能已经看出来，其实这个算法是有规律的，从第1天开始，每隔14天排列就会重复一遍。由此推断，只要知道 N 对 14 的模数 (modulus)，整个计算就可以简化成最多只要14次迭代就可以。

代码 (时间复杂度： O(1))

class Solution: def prisonAfterNDays(self, cells: List[int], N: int) -> List[int]: if N == 0: return cells template = cells days = N % 14 # 找出模数 if days == 0: days = 14 #如果是0，即是需耍迭代14次 for day in range(days): new_cells = [] for i in range(len(cells)): if i == 0 or i == 7: new_cells.append(0) elif cells[i - 1] == cells[i + 1]: new_cells.append(1) else: new_cells.append(0) cells = new_cells return cells