leetcode957. N 天后的牢房

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/prison-cells-after-n-days

题目描述

监狱中 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

解题思路

讲解这个题之前先复习下二进制算法的异或算法:
1 ^ 0 = 1
0 ^ 1 = 1
1 ^ 1 = 0
0 ^ 0 = 0
推论： 0 ^ N = N ,N ^ N = 0 (N 代表整数)
当我们看到相邻的房间同时为0 或者同时为1 时,第二天是满的,也即是1,有没有想到用异或算法.
同时为0 或者 1 异或后还是0,再和1异或,就是1了,
如果相邻的两个房间是一个空的一个满的,那异或后就是1,再和1异或后,就是0了,
所以推出状态转移公式为:
i 和 j 代表天数和房间
DP[i][j] = DP[i-1][j-1] ^ DP[i-1][j+1] ^ 1（if 0<j<6），
DP[i][j] = 0 （if j0 or j7）

寻找周期
从第一天到第N天，第1个房间和第8个房间永远为闲置状态（状态为0）
设8个房间的第1天的状态为：s1, s2, s3, s4, s5, s6, s7, s8
那么接下来第1～N天，最左边的s1和最后边的s8永远是0
第1天状态为：0, s2, s3, s4, s5, s6, s7, 0
第2天第2个房间的状态为：0^s31 = s3^1
第3天第3个房间的状态为：s3¹s3^s51^1 = (s3^s3)1^s5(1^1) = 0¹s5^0 = s5^1

在这里插入图片描述
由推导可知，每14天为1个循环周期

Java 代码演示

    /*** N 天后的房间* @param cells* @param n* @return*/public int[] prisonAfterNDays(int[] cells, int n) {//14 天一个周期,求余n = n % 14;//刚好整除时,代表最后一天if (n == 0){n = 14;}//记录下一天的情况,int[] newList = new int[cells.length];for (int day = 0;day < n;day++ ){for (int i = 1; i < cells.length - 1;i++){newList[i] = cells[i - 1] ^ cells[i + 1] ^ 1;}//把下一天的情况拷贝回去,进行下一次的判断cells = deepCopyList(newList);}return newList;}/*** 拷贝数组* @param cells* @return*/private  int[] deepCopyList(int[]cells) {int[] newList = new int[cells.length];for (int i = 0; i < cells.length;i++){newList[i] = cells[i];}return newList;}