957. Prison Cells After N Days 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public int[] prisonAfterNDays(int[] cells, int n) {
        int initialState = 0;
        for (int i = cells.length - 1; i >= 0; i--) {
            initialState = (initialState << 1) + cells[i];
        }

        int firstState = getNextState(initialState);
        Map<Integer, Integer> indexToStateCache = new HashMap<>();
        indexToStateCache.put(0, firstState);

        int state = firstState;
        int resultState = state;

        for (int i = 1; i < n; i++) {
            int nextState = getNextState(state);
            if (nextState == firstState) {
                // 出现了循环
                resultState = indexToStateCache.get((n - 1) % i);
                break;
            } else {
                indexToStateCache.put(i, nextState);
                resultState = state = nextState;
            }
        }

        int[] res = new int[cells.length];
        for (int i = 1; i <= 6; i++) {
            res[i] = (resultState >> i) & 1;
        }
        return res;
    }

    private int getNextState(int state) {
        return (~((state << 1) ^ (state >> 1))) & 0b01111110;
    }
}

References

957. Prison Cells After N Days