957.Prison Cells After N Days¶
Tags: Medium Hash Table
Links: https://leetcode.com/problems/prison-cells-after-n-days/
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
解法一：哈希表
这道题的第一想法是暴力模拟，但是看到数据范围，N最大可能达到10^9，暴力模拟不可取，并且暗示一定存在一些规律。看到cells的长度为8，可以知道状态最多有256种，所以很快就会重复，那么我们可以用一个哈希表去记录某一个状态离目前最近的出现天数，这样我们就知道某一个状态的循环周期了。
在进行哈希的时候有两种思路，第一种就是将cells的状态看成字符串，然后采用字符串哈希的办法（自然溢出法），用一个unordered_map<ull, int>来记录状态；第二种思路就是，我们可以用整数的二进制位来表示cells每一位的状态，这样就可以用一个数组来代替unordered_map了。
在计算cells的下一个状态的时候，有两种想法，第一种是用一个新数组记录状态，产生新的cells后在用新的cells覆盖原来的，但是这样会需要一个额外的数组；联想之前的289.Games of life，我们可以在原数组上直接生成结果，我们进行如下定义：
cells[i]原来为0，现在为0，cells[i] = 0
cells[i]原来为1，现在为1，cells[i] = 1
cells[i]原来为0，现在为1，cells[i] = 2
cells[i]原来为1，现在为0，cells[i] = 3
那么某一个cells[i]成为1的可能情况是：
cells[i - 1] = 0, cells[i + 1] = 0;
cells[i - 1] = 1, cells[i + 1] = 1;
cells[i - 1] = 2, cells[i + 1] = 0;
cells[i - 1] = 3, cells[i + 1] = 1;
cells[i + 1]只可能是0或1，因为我们是从前往后去修改状态的。发现规律，如果cells[i]的最终状态为1，那么必然存在cells[i - 1] + cells[i + 1]的和为偶数。
循环节最大长度为2^n，每次计算哈希值和产生下一状态需要遍历数组，时间复杂度O(n2^n)。
class Solution {
public:
vector<int> prisonAfterNDays(vector<int>& cells, int N) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n = cells.size();
vector<int> visit(1 << n, -1);
int val = getHashValue(cells);
visit[val] = 0;
for (int i = 1; i <= N; ++i) {
getNext(cells);
val = getHashValue(cells);
if (visit[val] != -1) {
int period = i - visit[val];
i = N - (N - visit[val]) % period;
}
visit[val] = i;
}
return cells;
}
int getHashValue(vector<int> & cells)
{
int res = 0;
for (int i = 0; i < cells.size(); ++i) {
if (cells[i]) res += 1 << i;
}
return res;
}
void getNext(vector<int> & cells)
{
int n = cells.size();
for (int i = 1; i < n - 1; ++i) {
if (!((cells[i - 1] + cells[i + 1]) & 1)) {
cells[i] = cells[i] ? 1 : 2;
}
else cells[i] = cells[i] ? 3 : 0;
}
cells[0] = 0, cells[n - 1] = 0;
for (int i = 1; i < n - 1; ++i) {
if (cells[i] == 2) cells[i] = 1;
else if (cells[i] == 3) cells[i] = 0;
}
}
};
如果采用字符串哈希的办法：
class Solution {
typedef unsigned long long ull;
static constexpr ull Base = 13331;
public:
vector<int> prisonAfterNDays(vector<int>& cells, int N) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n = cells.size();
unordered_map<ull, int> um;
ull val = getHashValue(cells);
um[val] = 0;
for (int i = 1; i <= N; ++i) {
getNext(cells);
val = getHashValue(cells);
if (um.find(val) != um.end()) {
int period = i - um[val];
i = N - (N - um[val]) % period;
}
um[val] = i;
}
return cells;
}
ull getHashValue(vector<int> & cells)
{
ull res = 0;
for (const auto & e : cells) res = res * Base + e + 48;
return res;
}
void getNext(vector<int> & cells)
{
int n = cells.size();
for (int i = 1; i < n - 1; ++i) {
if (!((cells[i - 1] + cells[i + 1]) & 1)) {
cells[i] = cells[i] ? 1 : 2;
}
else cells[i] = cells[i] ? 3 : 0;
}
cells[0] = 0, cells[n - 1] = 0;
for (int i = 1; i < n - 1; ++i) {
if (cells[i] == 2) cells[i] = 1;
else if (cells[i] == 3) cells[i] = 0;
}
}
};
解法二：矩阵乘法 + 快速幂