Leetcode 957.N天后的牢房

Leetcode 957.N天后的牢房

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

每天，无论牢房是被占用或空置，都会根据以下规则进行更改：

如果一间牢房的两个相邻的房间都被占用或都是空的，那么该牢房就会被占用。

否则，它就会被空置。

（请注意，由于监狱中的牢房排成一行，所以行中的第一个和最后一个房间无法有两个相邻的房间。）

我们用以下方式描述监狱的当前状态：如果第 i 间牢房被占用，则 cell[i]1，否则 cell[i]0。

根据监狱的初始状态，在 N 天后返回监狱的状况（和上述 N 种变化）。

输入:

cells = [1,0,0,1,0,0,1,0], N = 1000000000

输出:

[0,0,1,1,1,1,1,0]

思路

总共有八间牢房，只有空或非空两种状态，共2^8 = 256状态

N则有1e9，显然存在相同的状态，那么只要找到循环节就可以了。

题目链接

class Solution

{

public:

    int hashTable1[300]; //记录这个状态是否出现过

    int hashTable2[300]; //记录这个状态出现在第几天

    vector<int> prisonAfterNDays(vector<int>& cells, int N)

    {

        int id = 0;

        for(int i=0; i<cells.size(); i++)

        {

            if(cells[i])id += (1<<i);

        }

        hashTable1[id]=1;

        hashTable2[id]=0;

        int i=0,flag = 0;

        while(N--)

        {

            vector<int>temp;

            id = 0;

            for(int j=0; j<cells.size(); j++)

            {

                if(j==0||j==cells.size()-1)

                    temp.push_back(0);

                else

                {

                    if(cells[j-1]==cells[j+1])

                    {

                        temp.push_back(1);

                        id += (1<<j);

                    }

                    else

                        temp.push_back(0);

                }

            }

            cells = temp;

            if(flag)continue;

            if(flag==0&&hashTable1[id])  ///找到出现过的点

            {

                flag = 1;

                int repetend = i+1 - hashTable2[id];

                N%=repetend; ///去除循环

            }

            hashTable1[id]=1;

            hashTable2[id]=i+1;

            i++;

        }

        return cells;

    }

};