957. N 天后的牢房

墨蓝 2023-10-04 09:05 30阅读 0赞

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]

**提示：**

1.  `cells.length == 8`
2.  `cells[i]` 的值为 `0` 或 `1`
3.  `1 <= N <= 10^9`

输出一段时间状态，观察循环周期；

package Solution957;
    
    import java.util.Arrays;
    
    class Solution {
    	public int[] prisonAfterNDays(int[] cells, int n) {
    		if (cells.length < 3) {
    			return new int[] { 0, 0 };
    		}
    		for (int d = 0; d < n; d++) {
    			int[] cellscopy = cells.clone();
    			for (int i = 1; i < cells.length - 1; i++) {
    				if ((cells[i - 1] == 0 && cells[i + 1] == 0) || (cells[i - 1] == 1 && cells[i + 1] == 1)) {
    					cellscopy[i] = 1;
    				} else {
    					cellscopy[i] = 0;
    				}
    			}
    			cellscopy[0] = 0;
    			cellscopy[cellscopy.length - 1] = 0;
    			cells = cellscopy.clone();
    			System.out.println((d + 1) + Arrays.toString(cells));
    		}
    
    		return cells;
    	}
    
    	public static void main(String[] args) {
    		Solution sol = new Solution();
    		int[] cells = { 1, 0, 0, 1, 0, 0, 1, 0 };
    		int n = 30;
    		System.out.println(Arrays.toString(sol.prisonAfterNDays(cells, n)));
    	}
    
    }

1\[0, 0, 0, 1, 0, 0, 1, 0\]  
2\[0, 1, 0, 1, 0, 0, 1, 0\]  
3\[0, 1, 1, 1, 0, 0, 1, 0\]  
4\[0, 0, 1, 0, 0, 0, 1, 0\]  
5\[0, 0, 1, 0, 1, 0, 1, 0\]  
6\[0, 0, 1, 1, 1, 1, 1, 0\]  
7\[0, 0, 0, 1, 1, 1, 0, 0\]  
8\[0, 1, 0, 0, 1, 0, 0, 0\]  
9\[0, 1, 0, 0, 1, 0, 1, 0\]  
10\[0, 1, 0, 0, 1, 1, 1, 0\]  
11\[0, 1, 0, 0, 0, 1, 0, 0\]  
12\[0, 1, 0, 1, 0, 1, 0, 0\]  
13\[0, 1, 1, 1, 1, 1, 0, 0\]  
14\[0, 0, 1, 1, 1, 0, 0, 0\]  
15\[0, 0, 0, 1, 0, 0, 1, 0\]  
16\[0, 1, 0, 1, 0, 0, 1, 0\]  
17\[0, 1, 1, 1, 0, 0, 1, 0\]  
18\[0, 0, 1, 0, 0, 0, 1, 0\]  
19\[0, 0, 1, 0, 1, 0, 1, 0\]  
20\[0, 0, 1, 1, 1, 1, 1, 0\]  
21\[0, 0, 0, 1, 1, 1, 0, 0\]  
22\[0, 1, 0, 0, 1, 0, 0, 0\]  
23\[0, 1, 0, 0, 1, 0, 1, 0\]  
24\[0, 1, 0, 0, 1, 1, 1, 0\]  
25\[0, 1, 0, 0, 0, 1, 0, 0\]  
26\[0, 1, 0, 1, 0, 1, 0, 0\]  
27\[0, 1, 1, 1, 1, 1, 0, 0\]  
28\[0, 0, 1, 1, 1, 0, 0, 0\]  
29\[0, 0, 0, 1, 0, 0, 1, 0\]  
30\[0, 1, 0, 1, 0, 0, 1, 0\]

可以观察到周期为14天

package Solution957;
    
    import java.util.Arrays;
    
    class Solution {
    	public int[] prisonAfterNDays(int[] cells, int n) {
    		if (cells.length < 3) {
    			return new int[] { 0, 0 };
    		}
    		int x = n % 14;
    		if (x == 0) {
    			x = 14;
    		}
    		for (int d = 0; d < x; d++) {
    			int[] cellscopy = cells.clone();
    			for (int i = 1; i < cells.length - 1; i++) {
    				if ((cells[i - 1] == 0 && cells[i + 1] == 0) || (cells[i - 1] == 1 && cells[i + 1] == 1)) {
    					cellscopy[i] = 1;
    				} else {
    					cellscopy[i] = 0;
    				}
    			}
    			cellscopy[0] = 0;
    			cellscopy[cellscopy.length - 1] = 0;
    			cells = cellscopy.clone();
    		}
    		return cells;
    	}
    
    	public static void main(String[] args) {
    		Solution sol = new Solution();
    		int[] cells = { 1, 0, 0, 1, 0, 0, 1, 0 };
    		int n = 1000000000;
    		System.out.println(Arrays.toString(sol.prisonAfterNDays(cells, n)));
    	}
    
    }