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 == 8
cells[i]
is in{0, 1}
1 <= N <= 10^9
A:
这个题目就是找到重复的,然后取模就可以了。
class Solution { public: vector<int> prisonAfterNDays(vector<int>& cells, int N) { unordered_map<string, int> M; vector<vector<int>> V{cells}; // put day 0 first string key; while (true) { // at most 2^6 = 64 vector<int> next(8, 0); for (int i = 1; i <= 6; i++) { next[i] = V.back()[i - 1] == V.back()[i + 1] ? 1 : 0; } key = string(next.begin(), next.end()); if (M.find(key) != M.end()) { // if this new key already been found break; } M[key] = V.size(); // prsion status --> day(index based on 0 ) V.push_back(next); } if (N > V.size() -1) { // -1 because we have day 0 int circleLen = V.size() - M[key];// this is always 14, can mathmatically prove it N = (N - M[key]) % circleLen; // first remove leading status ahead of circle return V[M[key] + N ];// NO need to minus 1, since N after mod is already 0 based }else { return V[N]; } } };
其实有个数学方法, 证明了circle 只可能是1,7,14,那么我们直接%14就好了
N = (N - 1) % 14 + 1;
Mistakes:
1: unordered_map已经不允许用vector<> 来做key 了。 这个给我造成了点儿麻烦。
因此我们只能用 string str(V.begin(), V.end()); 也就是把0/1 当成 char值来对待(当然可视化后,显示的string并不是01101001等形式。)
2: 在2个不同的Return 中, 一个N是0 based(after mod operation). 一个是1 based。 比较坑
No comments:
Post a Comment