Prison Cells After N Days (M)
題目
There are 8 prison cells in a row, and each cell is either occupied or vacant.
Each day, whether the cell is occupied or vacant changes according to the following rules:
- If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied.
- Otherwise, it becomes vacant.
(Note that because the prison is a row, the first and the last cells in the row can't have two adjacent neighbors.)
We describe the current state of the prison in the following way: cells[i] == 1 if the i-th cell is occupied, else cells[i] == 0.
Given the initial state of the prison, return the state of the prison after N days (and N such changes described above.)
Example 1:
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]
Example 2:
Input: cells = [1,0,0,1,0,0,1,0], N = 1000000000
Output: [0,0,1,1,1,1,1,0]
Note:
cells.length == 8cells[i]is in{0, 1}1 <= N <= 10^9
題意
給定一個一維陣列cells，進行N次回圈，每次回圈中如果cells[i]鄰接的兩個元素都為1或都為0，則cells[i]變為1，否則cells[i]變為0，首元素和末元素只會變為0，求N次回圈后陣列的狀態，
思路
和 0289. Game of Life (M) 有點類似，每次狀態的變更都是同時發生的，不能用前一個變化后的值去影響后一個將要改變的值，每次回圈可以直接復制一個陣列進行操作，同時，打表可以發現陣列的狀態是有規律的，以14作為一個周期，因此N等效于(N-1)%14+1，
代碼實作
Java
class Solution {
public int[] prisonAfterNDays(int[] cells, int N) {
N = (N - 1) % 14 + 1;
for (int i = 1; i <= N; i++) {
int[] aux = Arrays.copyOf(cells, 8);
for (int j = 1; j < 7; j++) {
cells[j] = aux[j - 1] == aux[j + 1] ? 1 : 0;
}
cells[0] = cells[7] = 0;
}
return cells;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/27696.html
標籤：其他
上一篇：讓我們純手寫一個js繼承吧