[LeetCode做题记录] 957. N天后的牢房 (MEDIUM)

时间: | 分类: LeetCode做题记录

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

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

如果一间牢房的两个相邻的房间都被占用或都是空的,那么该牢房就会被占用。
否则,它就会被空置。
(请注意,由于监狱中的牢房排成一行,所以行中的第一个和最后一个房间无法有两个相邻的房间。)

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

根据监狱的初始状态,在 N 天后返回监狱的状况(和上述 N 种变化)。

示例 1:

输入:cells = [0,1,0,1,1,0,0,1], N = 7
输出:[0,0,1,1,0,0,0,0]
解释:
下表概述了监狱每天的状况:
Day 0: [0, 1, 0, 1, 1, 0, 0, 1]
Day 1: [0, 1, 1, 0, 0, 0, 0, 0]
Day 2: [0, 0, 0, 0, 1, 1, 1, 0]
Day 3: [0, 1, 1, 0, 0, 1, 0, 0]
Day 4: [0, 0, 0, 0, 0, 1, 0, 0]
Day 5: [0, 1, 1, 1, 0, 1, 0, 0]
Day 6: [0, 0, 1, 0, 1, 1, 0, 0]
Day 7: [0, 0, 1, 1, 0, 0, 0, 0]

示例 2:

输入:cells = [1,0,0,1,0,0,1,0], N = 1000000000
输出:[0,0,1,1,1,1,1,0]
提示:

cells.length == 8
cells[i] 的值为 0 或 1 
1 <= N <= 10^9

还是很丢人的想了很久,结束后两分钟做出来了。。。
首先是想到线性做法,直接TLE了,本来想打表过,发现太多样例,遂放弃,结束前五分钟试了下找规律,发现每14次就会重复,所以循环次数为1~14次
QQ图片20181218104857.jpg
(所以认真看题也很重要(

个人解答: 12~22ms/排名未知

class Solution {
    //判断此索引位置是否有人
    public static int hasPerson(int[] cells, int index) {
        if (index < 1 || index >= cells.length - 1) {
            return 0;
        }
        return (cells[index - 1] == cells[index + 1]) ? 1 : 0;
    }

    public int[] prisonAfterNDays(int[] cells, int N) {

        //注意要用clone,否则似乎会拷贝引用?
        int[] cellCache = cells.clone();
        cellCache[0] = 0;
        cellCache[cellCache.length - 1] = 0;

        N = N % 14;
        if (N == 0) {
            N = 14;
        }
        //由于每14次运算就重复一次,所以只要求余14的值就行
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < cells.length; j++) {
                cellCache[j] = hasPerson(cells, j);
            }
            cells = cellCache.clone();
        }
        return cells;
    }
}

LeetCode Java



白咲美绘瑠's blog