1. LeetCode957题目链接链接

https://leetcode-cn.com/problems/prison-cells-after-n-days/

2.题目解析

该题中可以看到一共有八个牢房，每个牢房只有两个状态，n个cell一共有2^n，N大于这个值的时候必定存在循环,所以我门可以先找循环，找到循环后，就好办了很多。

    private static void test(int[] cells, int N) {
        int[] result = new int[cells.length];
        int index = 0;
        for (int i = 0; i < N; i++) {
            next[0] = 0;
            next[cells.length - 1] = 0;
            for (int j = 1; j < cells.length - 1; j++) {
                if (cells[j - 1] == cells[j + 1]) {
                    next[j] = 1;
                } else {
                    next[j] = 0;
                }
            }
            String toString = intToString(next, cells);
            System.out.println(toString);
            if (hashMap.containsValue(toString)) {
                System.out.println(i);
            } else {
                hashMap.put(i, toString);
            }
        }
    }

上面代码可以打印出14一循环，由此我们就可以继续进行下去。

找到循环次数就好办很多，直接对N去余，然后找对应对数组就好啦。

public int[] prisonAfterNDays(int[] cells, int N) {
         Map<Integer, String> map = new HashMap<>();

        int[] next = new int[cells.length];

        HashMap<Integer, String> hashMap = new HashMap<>();
        int count = N;
        for (int i = 0; i < count; i++) {
            next[0] = 0;
            next[cells.length - 1] = 0;
            for (int j = 1; j < cells.length - 1; j++) {
                if (cells[j - 1] == cells[j + 1]) {
                    next[j] = 1;
                } else {
                    next[j] = 0;
                }
            }
            count--;
            String value = intToString(next, cells);
            System.out.println(value);
            if (map.containsValue(value)) {
                value = map.get(N % map.size() == 0 ? map.size() : N % map.size());
                System.out.println(N % map.size());
                System.out.println(N);
                System.out.println(value);
                System.out.println(map.size());
                String[] keys = value.split("");
                for (int j = 0; j < keys.length; j++) {
                    next[j] = Integer.valueOf(keys[j]);
                }
                return next;
            } else {
                map.put(i, value);
            }
        }
        return next;
    }
     public  String intToString(int[] prisons, int[] cells) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < prisons.length; i++) {
            cells[i] = prisons[i];
            sb.append(prisons[i]);
        }
        return sb.toString();
    }

3.提交结果