Saturday, September 19, 2020

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。 比较坑




    No comments:

    Post a Comment