Prison Cells After N Days
(Active and Inactive Cells After k Days)
Array
Medium
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] == 1if thei-th cell is occupied, elsecells[i] == 0.
Given the initial state of the prison, return the state of the prison afterNdays (andNsuch 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
Analysis & Solution
这个本身逻辑也就是状态转移很直白，但是挑战在于如何处理边界条件以及如何更优化时间（和空间）复杂度。
Brute-force Simulation
用prevVal记录上一个时间的左边cell的状态，nextVal记录上一个时间右边cell的状态，要注意的是nextVal在判断前就可以确定好，而prevVal要在判断完当前cell的更改方案后，再更新。
Space: Extra Space: O(1) 不算返回答案所需的List
Time: O(n * m), n - number of cells, m - days
但是，这种方法会TLE。
！！注意：下面的代码在LeetCode会Time Limit Exceeded ！！
// IMPORT LIBRARY PACKAGES NEEDED BY YOUR PROGRAM
import java.util.List;
import java.util.LinkedList;
import java.util.Arrays;
// SOME CLASSES WITHIN A PACKAGE MAY BE RESTRICTED
// DEFINE ANY CLASS AND METHOD NEEDED
// CLASS BEGINS, THIS CLASS IS REQUIRED
public class Solution
{
// METHOD SIGNATURE BEGINS, THIS METHOD IS REQUIRED
public List<Integer> cellCompete(int[] states, int days)
{
// WRITE YOUR CODE HERE
if (states.length != 8 || days < 1) {
return convertToList(states);
}
int n = states.length;
int prevVal, nextVal;
while (days-- > 0) {
prevVal = 0;
nextVal = 0;
for (int i = 0; i < n; i++) {
if (i < n - 1) {
nextVal = states[i + 1];
} else if (i == n - 1) {
nextVal = 0;
}
if (nextVal == prevVal) {
prevVal = states[i];
states[i] = 0;
} else {
prevVal = states[i];
states[i] = 1;
}
}
}
return convertToList(states);
}
private List<Integer> convertToList(int[] arr) {
List<Integer> output = new LinkedList<Integer>();
for (int a: arr) {
output.add(a);
}
return output;
}
// METHOD SIGNATURE ENDS
}这个也会TLE
class Solution {
public int[] prisonAfterNDays(int[] cells, int days) {
if (cells.length != 8 || days < 1) {
return cells;
}
int n = cells.length;
int prevVal, nextVal;
while (days-- > 0) {
prevVal = 0;
nextVal = 0;
for (int i = 0; i < n; i++) {
if (i == 0 || i == n - 1) {
prevVal = cells[i];
cells[i] = 0;
continue;
}
if (i < n - 1) {
nextVal = cells[i + 1];
} else if (i == n - 1) {
nextVal = 0;
}
if (nextVal == prevVal) {
prevVal = cells[i];
cells[i] = 1;
} else {
prevVal = cells[i];
cells[i] = 0;
}
}
}
return cells;
}
}时间优化：找pattern
用signature作为hashmap的key记录当前的cells，找到循环之后直接days - period。
Time: O(n * m / k)
Space: O(n * k) - k 是循环周期，n是cells数，m是days
5069 ms, faster than 1.05%
class Solution {
public int[] prisonAfterNDays(int[] cells, int days) {
if (cells.length != 8 || days < 1) {
return cells;
}
int n = cells.length;
int prevVal, nextVal;
HashMap<String, Integer> map = new HashMap();
int period = -1;
while (days > 0) {
prevVal = 0;
nextVal = 0;
for (int i = 0; i < n; i++) {
if (i == 0 || i == n - 1) {
prevVal = cells[i];
cells[i] = 0;
continue;
}
if (i < n - 1) {
nextVal = cells[i + 1];
} else if (i == n - 1) {
nextVal = 0;
}
if (nextVal == prevVal) {
prevVal = cells[i];
cells[i] = 1;
} else {
prevVal = cells[i];
cells[i] = 0;
}
}
if (period < 0 ) {
String signature = Arrays.toString(cells);
if (map.containsKey(signature)) {
period = map.get(signature) - days;
while (period > 0 && days - period > 0) {
days -= period;
}
} else {
map.put(signature, days);
}
}
days--;
}
return cells;
}
}时间优化才是重点，不做不必要的空间优化可以让代码更简洁：
而且空间本身也只有8个元素的数组，每次也只需要这么多，因此可以接受。
13 ms, faster than 60.41%; 37.6 MB, less than 100.00%
class Solution {
public int[] prisonAfterNDays(int[] cells, int N) {
Map<String, Integer> seen = new HashMap<>();
while (N-- > 0) {
int[] cells2 = new int[8];
seen.put(Arrays.toString(cells), N);
for (int i = 1; i < 7; ++i) {
cells2[i] = cells[i - 1] == cells[i + 1] ? 1 : 0;
}
cells = cells2;
if (seen.containsKey(Arrays.toString(cells))) {
N %= seen.get(Arrays.toString(cells)) - N + 1;
}
}
return cells;
}
}假设已经找到循环的Pattern周期为14之后，可以用如下方法：
因为重复从第15天开始，因此 N = (N - 1) % 14 + 1
public int[] prisonAfterNDays(int[] cells, int N) {
for (N = (N - 1) % 14 + 1; N > 0; --N) {
int[] cells2 = new int[8];
for (int i = 1; i < 7; ++i)
cells2[i] = cells[i - 1] == cells[i + 1] ? 1 : 0;
cells = cells2;
}
return cells;
}Reference
https://www.knowsh.com/Notes/250480/Active-And-Inactive-Cells-After-K-Days
Last updated
Was this helpful?