LeetCode 957. N 天后的牢房（查找循环节）Michael是个半路程序员-

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