957. Prison Cells After N Days

题解

从题目描述看出，总共有8个牢房。n的大小是n^9，如果O(n)的时间复杂度会超时。
由于每个牢房的状态只有0或者1，所以8个牢房总共的状态只有256个，因此可以预见，在牢房转换的过程中，一定会出现循环。
问题在于，循环起始位置和结束位置是不固定的，所以我们假设起始位置是loop_start，结束位置是loop_end，那么最后的状态分两种情况，n < loop_start，则直接返回对应状态，如果n >= loop_start，则从循环状态中找到对应的状态，。
我们通过两个hash表记录每个状态出现的位置，和每个位置对应的状态。

代码

  • 小知识点，循环从loop_start开始，loop_end结束，n的转态为：

    1. if (n < loop_start) {
    2.   return n;
    3. } else {
    4.   return loop_start + (n - loop_start) % (loop_end - loop_start);
    5. }
    1. class Solution {
    2. public:
    3.   // 数组转换为数字
    4.   int get_num(vector<int> &cells) {
    5.       int n = 0;
    6.       for (int i = 0; i < cells.size(); i ++) {
    7.           n = n*2 + cells[i];
    8.       }
    9.       return n;
    10.   }
    12.   // 状态转换
    13.   void transform(vector<int>& cells) {
    14.       vector<int> tmp = cells;
    15.       cells[0] = 0, cells[cells.size() - 1] = 0;
    16.       for (int i = 1; i < cells.size() - 1; i ++) {
    17.           if (tmp[i - 1] == tmp[i + 1]) {
    18.               cells[i] = 1;
    19.           } else {
    20.               cells[i] = 0;
    21.           }
    22.       }
    23.   }
    25.   vector<int> prisonAfterNDays(vector<int>& cells, int n) {
    26.       unordered_map<int, int> order;
    27.       unordered_map<int, vector<int>> hash;
    29.       int loop_start = -1, loop_end = -1;
    30.       for (int i = 1; i <= 256; i ++) {
    31.           transform(cells);
    32.           int n = get_num(cells);
    33.           if (order.count(n)) {
    34.               // 当有循环出现时，记录loop_start和loop_end
    35.               loop_end = i;
    36.               loop_start = order[n];
    37.               break;
    38.           } else {
    39.               // 记录状态n的位置为i
    40.               order[n] = i;
    41.               // 记录位置i的状态是cells
    42.               hash[i] = cells;
    43.           }
    44.       }
    46.       if (n < loop_start) {
    47.           return hash[n];
    48.       }
    49.       return hash[loop_start + (n - loop_start) % (loop_end - loop_start)];
    50.   }
    51. };