1些己、題目鏈接

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

2蜗细、解題思路

題目意思是說豺谈，一個監(jiān)獄有8個牢房（一個數(shù)組）脚祟，這8個牢房在一排且首尾不相連仔蝌，如果在第一天某個牢房左右相鄰的兩個牢房同時有人（數(shù)組的值為1）或者同時沒人（數(shù)組的值為0）沙热，第二天該牢房就算有人博烂，這么說可能有點繞木西，解析一下

我用3個牢房來比喻一下，只有以下這幾種情況找筝，牢房才會有人（即數(shù)組的值為1）：

day1：

0——>0——>0
1——>0——>1
0——>1——>0
1——>1——>1

day2：

待定——>1——>待定
待定——>1——>待定
待定——>1——>待定
待定——>1——>待定

給你一個數(shù)組表示這8個牢房的初始狀態(tài)蹈垢，讓你求出第N天這8個牢房的狀態(tài)是怎樣的，N<=2的9次方袖裕〔芴В看到數(shù)字這么大的，如果直接用循環(huán)來把每次的狀態(tài)都遍歷出來那肯定會超時急鳄，這個是毫無疑問的谤民，通過這個我們也可以從側(cè)面的知道這個肯定是有循環(huán)的，所以疾宏，循環(huán)遍歷所有的肯定會重復(fù)遍歷张足，對于這種情況我們通常的做法就是將狀態(tài)保存在hashmap中，一遍歷到hashmap中存在的狀態(tài)坎藐，那么該節(jié)點就是循環(huán)的一個節(jié)點为牍，我們就可以直接通過取模運算來算出結(jié)果。

3岩馍、代碼

public int[] prisonAfterNDays(int[] cells, int N) {
    Map<Integer, String> map = new HashMap<>();
    int[] prisons = new int[cells.length];
    int count = N;
    int index = 1;
    while (count > 0) {
        int flag = 0;
        for (int i = 0; i < cells.length; i++) {
            if (i == 0) {
                prisons[flag] = 0;
            } else if (i == cells.length - 1) {
                prisons[flag] = 0;
            } else if (cells[i - 1] == cells[i + 1]) {
                prisons[flag] = 1;
            } else {
                prisons[flag] = 0;
            }
            flag++;
        }
        count--;
        String value = intToString(prisons, cells);
        if (map.containsValue(value)) {
            flag = 0;
            value = map.get(N % map.size() == 0 ? map.size() : N % map.size());
            String[] keys = value.split("");
            for (String k : keys) {
                prisons[flag++] = Integer.valueOf(k);
            }
            return prisons;
        } else {
            map.put(index++, value);
        }
    }
    return prisons;
}
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();
}

4碉咆、提交結(jié)果

4211155D-09C3-4E1B-B137-DB26698393C3.png