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

  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 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation