LeetCode957,Prison Cells After N

题目

Prison Cells After N Days

题目描述

8 间牢房排成一排，每间牢房不是有人住就是空着。
每天，无论牢房是被占用或空置，都会根据以下规则进行更改：
如果一间牢房的两个相邻的房间都被占用或都是空的，那么该牢房就会被占用。
否则，它就会被空置。
（请注意，由于监狱中的牢房排成一行，所以行中的第一个和最后一个房间无法有两个相邻的房间。）
我们用以下方式描述监狱的当前状态：如果第 i 间牢房被占用，则 cell[i]==1，否则 cell[i]==0。
根据监狱的初始状态，在 N 天后返回监狱的状况（和上述 N 种变化）。

题解

8间房最大可能是2^8 256种但是实际上只有 2^6 64种，然后我们通过for找到循环节
最后对N进行取余 输出结果列表

代码

class lc957 {

    public static void main(String[] args) {
        int[] cle = {0,1,0,0,1,0,0,1};
        prisonAfterNDays(cle, 10);
        System.out.println("  "+7%13);
    }

    static int[][] map = new int[257][8];
    int[] sums = new int[257];
    static HashMap<Integer, Integer> hashMap = new HashMap<>();
    static int s;
    static int e;

    public static int[] prisonAfterNDays(int[] cells, int N) {
        map[0] = cells;
        hashMap.clear();
        hashMap.put(cacl(cells), 0);
        findN();
        System.out.println("s:" + s + "  e:" + e);
        int count = e - s;
        N = N % count == 0 ? count : N % count;

        return map[N];
    }

    public static int findN() {
        boolean flag = false;
        int i = 1;

        while (!flag) {
            map[i + 1][0] = 0;
            map[i + 1][7] = 0;

            for (int j = 1; j < 7; j++) {
                if (map[i - 1][j - 1] == map[i - 1][j + 1])
                    map[i][j] = 1;
                else
                    map[i][j] = 0;
            }
            int sum = cacl(map[i]);
            if (hashMap.get(sum) != null) {
                e = i;
                s = hashMap.get(sum);
                flag = true;
            } else {
                hashMap.put(sum, i);
            }
            i++;
        }
        return 1;
    }

    public static int cacl(int[] nums) {
        int sum = 0;
        for (int i = 0; i < 8; i++) {
            sum = sum + (int) Math.pow(2, i) * nums[i];
        }
        return sum;
    }

}

结果

image.png