1. 題目

8 間牢房排成一排，每間牢房不是有人住就是空著。

每天，無論牢房是被占用或空置，都會根據以下規則進行更改：

• 如果一間牢房的兩個相鄰的房間都被占用或都是空的，那么該牢房就會被占用。
  否則，它就會被空置。

（請注意，由于監獄中的牢房排成一行，所以行中的第一個和最后一個房間無法有兩個相鄰的房間。）

我們用以下方式描述監獄的當前狀態：如果第 i 間牢房被占用，則 cell[i]==1，否則 cell[i]==0。

根據監獄的初始狀態，在 N 天后返回監獄的狀況（和上述 N 種變化）。

示例 1： 輸入：cells = [0,1,0,1,1,0,0,1], N = 7 輸出：[0,0,1,1,0,0,0,0] 解釋： 下表概述了監獄每天的狀況： 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]示例 2： 輸入：cells = [1,0,0,1,0,0,1,0], N = 1000000000 輸出：[0,0,1,1,1,1,1,0]提示： cells.length == 8 cells[i] 的值為 0 或 1 1 <= N <= 10^9

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/prison-cells-after-n-days
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

類似題目：
LeetCode 466. 統計重復個數（循環節）
機器人大冒險

• 看數據規模，模擬肯定會超時的
• 需要找到循環的部分，跳過循環的狀態

class Solution { public:vector<int> prisonAfterNDays(vector<int>& cells, int N) {int state = 0, nextstate = 0, i, gap;for(i = 0; i < 8; i++){if(cells[i])state |= 1<<(i);//記錄初始狀態到int}unordered_map<int,int> rec;//狀態，天數unordered_map<int,int> day_state;//天數,狀態rec[state] = 0;day_state[0] = state;for(int day = 1; day <= N; day++){for(i = 1; i < 7; i++)//兩端為0，不用遍歷{if( ( ((state>>(i-1))&1) && ((state>>(i+1))&1) ) || ( ((state>>(i-1))&1)==0 && ((state>>(i+1))&1)==0 ) )nextstate |= 1<<(i);//下一個狀態}state = nextstate;day_state[day] = state;if(rec.count(state))//找到了循環出現的狀態{gap = day - rec[state];//周期間隔break;}rec[state] = day;nextstate = 0;}//進入循環前有 rec[state] 天//剩余的 天數 N-rec[state] 有多少個循環 (N-rec[state])/gap 個//還剩余多少 N-rec[state] - (N-rec[state])/gap*gap//加上 進入 循環前的 天數 rec[state]+N-rec[state]-(N-rec[state])/gap*gap//最后的狀態跟 那天的狀態是一樣的state = day_state[rec[state]+N-rec[state]-(N-rec[state])/gap*gap];vector<int> ans(8,0);for(i = 1; i < 7; i++){if((state>>i)&1)ans[i] = 1;//轉成數組答案}return ans;} };

8 ms 12.3 MB

總結

以上是生活随笔為你收集整理的LeetCode 957. N 天后的牢房（查找循环节）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。