[LeetCode] 957. Prison Cells After N Days

[grandyang]

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

这道题给了一个只由0和1构成的数组，数组长度固定为8，现在要进行N步变换，变换的规则是若一个位置的左右两边的数字相同，则该位置的数字变为1，反之则变为0，让求N步变换后的数组的状态。需要注意的数组的开头和结尾的两个位置，由于一个没有左边，一个没有右边，默认其左右两边的数字不相等，所以不管首尾数字初始的时候是啥，在第一次变换之后一定会是0，而且一直会保持0的状态。博主最开始做的时候，看题目标记的是 Medium，心想应该不需要啥特别的技巧，于是就写了一个暴力破解的，但是超时了 Time Limit Exceeded。给了一个超级大的N，不得不让博主怀疑是否能够直接遍历N，又看到了本题的标签是 Hash Table，说明了数组的状态可能是会有重复的，就是说可能是有一个周期循环的，这样就完全没有必要每次都算一遍。正确的做法的应该是建立状态和当前N值的映射，一旦当前计算出的状态在 HashMap 中出现了，说明周期找到了，这样就可以通过取余来快速的缩小N值。为了使用 HashMap 而不是 TreeMap，这里首先将数组变为字符串，然后开始循环N，将当前状态映射为 N-1，然后新建了一个长度为8，且都是0的字符串。更新的时候不用考虑首尾两个位置，因为前面说了，首尾两个位置一定会变为0。更新完成了后，便在 HashMap 查找这个状态是否出现过，是的话算出周期，然后N对周期取余。最后再把状态字符串转为数组即可，参见代码如下：

解法一：

class Solution {
public:
    vector<int> prisonAfterNDays(vector<int>& cells, int N) {
        vector<int> res;
        string str;
        for (int num : cells) str += to_string(num);
        unordered_map<string, int> m;
        while (N > 0) {
            m[str] = N--;
            string cur(8, '0');
            for (int i = 1; i < 7; ++i) {
                cur[i] = (str[i - 1] == str[i + 1]) ? '1' : '0';
            }
            str = cur;
            if (m.count(str)) {
                N %= m[str] - N;
            }
        }
        for (char c : str) res.push_back(c - '0');
        return res;
    }
};

下面的解法使用了 TreeMap 来建立状态数组和当前N值的映射，这样就不用转为字符串了，写法是简单了一点，但是运行速度下降了许多，不过还是在 OJ 许可的范围之内，参见代码如下：

解法二：

class Solution {
public:
    vector<int> prisonAfterNDays(vector<int>& cells, int N) {
        map<vector<int>, int> m;
        while (N > 0) {
            m[cells] = N--;
            vector<int> cur(8);
            for (int i = 1; i < 7; ++i) {
                cur[i] = (cells[i - 1] == cells[i + 1]) ? 1 : 0;
            }
            cells = cur;
            if (m.count(cells)) {
                N %= m[cells] - N;
            }
        }
        return cells;
    }
};

下面这种解法是看 lee215 大神的帖子 中说的这个循环周期是 1，7，或者 14，知道了这个规律后，直接可以在开头就对N进行缩小处理，取最大的周期 14，使用 (N-1) % 14 + 1 的方法进行缩小，至于为啥不能直接对 14 取余，是因为首尾可能会初始化为1，而一旦N大于0的时候，返回的状态首尾一定是0。为了不使得正好是 14 的倍数的N直接缩小为0，所以使用了这么个小技巧，参见代码如下：

解法三：

class Solution {
public:
    vector<int> prisonAfterNDays(vector<int>& cells, int N) {
        for (N = (N - 1) % 14 + 1; N > 0; --N) {
            vector<int> cur(8);
            for (int i = 1; i < 7; ++i) {
                    cur[i] = (cells[i - 1] == cells[i + 1]) ? 1 : 0;
            }
            cells = cur;
        }
        return cells;
    }
};

Github 同步地址:

#957

类似题目：

参考资料：

https://leetcode.com/problems/prison-cells-after-n-days/

https://leetcode.com/problems/prison-cells-after-n-days/discuss/266854/Java%3A-easy-to-understand

https://leetcode.com/problems/prison-cells-after-n-days/discuss/205684/JavaPython-Find-the-Loop-or-Mod-14

LeetCode All in One 题目讲解汇总(持续更新中...)