{"id":4510,"date":"2018-12-19T23:23:09","date_gmt":"2018-12-20T07:23:09","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4510"},"modified":"2018-12-20T21:49:08","modified_gmt":"2018-12-21T05:49:08","slug":"leetcode-957-prison-cells-after-n-days","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/uncategorized\/leetcode-957-prison-cells-after-n-days\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 957. Prison Cells After N Days"},"content":{"rendered":"\n<p>There are 8 prison cells in a row, and each cell is either occupied or vacant.<\/p>\n\n\n\n<p>Each day, whether the cell is occupied or vacant changes according to the following rules:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>If a cell has two adjacent neighbors that are both occupied or both vacant,&nbsp;then the cell becomes occupied.<\/li><li>Otherwise, it becomes vacant.<\/li><\/ul>\n\n\n\n<p>(Note that because the prison is a row, the first and the last cells in the row can&#8217;t have two adjacent neighbors.)<\/p>\n\n\n\n<p>We describe the current state of the prison&nbsp;in the following way:&nbsp;<code>cells[i] == 1<\/code>&nbsp;if the&nbsp;<code>i<\/code>-th cell is occupied, else&nbsp;<code>cells[i] == 0<\/code>.<\/p>\n\n\n\n<p>Given the initial state of the prison, return the state of the prison after&nbsp;<code>N<\/code>&nbsp;days (and&nbsp;<code>N<\/code>&nbsp;such changes described above.)<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input: <\/strong>cells = [0,1,0,1,1,0,0,1], N = 7<br><strong>Output: <\/strong>[0,0,1,1,0,0,0,0]<br><strong>Explanation: <\/strong>The following table summarizes the state of the prison on each day:<br>Day 0: [0, 1, 0, 1, 1, 0, 0, 1]<br>Day 1: [0, 1, 1, 0, 0, 0, 0, 0]<br>Day 2: [0, 0, 0, 0, 1, 1, 1, 0]<br>Day 3: [0, 1, 1, 0, 0, 1, 0, 0]<br>Day 4: [0, 0, 0, 0, 0, 1, 0, 0]<br>Day 5: [0, 1, 1, 1, 0, 1, 0, 0]<br>Day 6: [0, 0, 1, 0, 1, 1, 0, 0]<br>Day 7: [0, 0, 1, 1, 0, 0, 0, 0]<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input: <\/strong>cells = [1,0,0,1,0,0,1,0], N = 1000000000<br><strong>Output: <\/strong>[0,0,1,1,1,1,1,0]<\/pre>\n\n\n\n<p><strong>Note:<\/strong><\/p>\n\n\n\n<ol class=\"wp-block-list\"><li><code>cells.length == 8<\/code><\/li><li><code>cells[i]<\/code>&nbsp;is in&nbsp;<code>{0, 1}<\/code><\/li><li><code>1 &lt;= N &lt;= 10^9<\/code><\/li><\/ol>\n\n\n\n<h1 class=\"wp-block-heading\"><strong>Solution: Simulation<\/strong><\/h1>\n\n\n\n<p>Simulate the process, since there must be loops, record the last day when a state occurred.&nbsp;<\/p>\n\n\n\n<p>Time complexity: O(2^8)<br>Space complexity: O(2^8)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre>\n\/\/ Author: Huahua, running time: 4 ms\nclass Solution {\npublic:\n  vector<int> prisonAfterNDays(vector<int>& cells, int N) {\n    vector<int> seen(1 << 8, -1);\n    auto getKey = [] (const vector<int>& cells) {\n      int key = 0;\n      for (int i = 0; i < 8; ++i)\n        key |= cells[i] << i;\n      return key;\n    };\n    while (N > 0) {      \n      const int key = getKey(cells);\n      if (seen[key] > 0)\n        N %= seen[key] - N;\n      seen[key] = N--;\n      if (N < 0) break;\n      vector<int> c(8);\n      for (int i = 1; i < 7; ++i)\n        c[i] = cells[i - 1] == cells[i + 1];\n      cells.swap(c);\n    }\n    return cells;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>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&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-4510","post","type-post","status-publish","format-standard","hentry","category-uncategorized","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4510","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=4510"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4510\/revisions"}],"predecessor-version":[{"id":4514,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4510\/revisions\/4514"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4510"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4510"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4510"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}