957. 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:

1. cells.length == 8
2. cells[i] is in {0, 1}
3. 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。 比较坑