LeetCode: N天后的监狱牢房

Question

堆栈，我不能把我的头绕到这个奇怪的地方。我每次都在评估数组中的位置。为什么每次收到不同的结果时都初始化数组.如果有人能解释这件事我会很感激的。

时间循环中的：正确的

0，1，0，1，1，1，0，1

0,1,1,0,0,0,0,0

0,0,0,0,1,1,1,0

0，1，1，0，0，1，0

0，0，0，0，0，1，0

0，1，1，1，1，1，0

0，0，1，0，1，1，0

0,0,1,1,0,0,0,0

外部While循环(初始化一次)：不正确的

0，1，0，1，1，1，0，1

0,1,1,0,0,0,0,0

0，0，1，1，1，1，0

0,0,1,1,0,0,1,0

0,0,0,1,0,0,1,0

0，1，1，0，1，1，0

0，0，1，1，1，1，0

0，0，0，0，0，1，1，0

问题详细信息

一排有8个牢房，每个牢房要么有人住，要么空着。

每一天，无论牢房是被占用还是空置，都会根据以下规则进行更改：

如果一个单元格有两个相邻的邻居，它们都被占用或都是空的，那么单元格就会被占用。否则，它就会变得空置。(请注意，由于监狱是一行，行中的第一个和最后一个单元格不能有两个相邻的邻居。)

我们用以下方式描述监狱的当前状态:细胞== 1，如果第一个细胞被占据，否则细胞== 0。

鉴于监狱的最初状态，在N天后返回监狱的状态(以及上面描述的N个这样的变化)。

示例1:预期输出

输入:单元格=0，1，0，1，1，0，1，1，N=7

产出:0，0，1，1 0，0，0，0

解释：

下表汇总了每天监狱的状况：

第0天: 0，1，0，1，1，0，0

第一天: 0，1，1，0，0，0，0

第2天: 0 0 0 1 1 1 0

第3天: 0，1，1，0，0，1，0

第4天: 0，0，0，0，0，1，0，

第5天: 0，1，1，1，0，1，0

第6天: 0，0，1，0，1，1，0

第7天: 0 0 1 1 0 0 0

方法

    static public int[] PrisonAfterNDays(int[] cells, int N) 
    {
        int counter = 0;
        //Doesn't work if it's here
        //int[] temp = new int[8];
        while(counter < N)
        {
            Console.WriteLine(String.Join(",",cells));

            //Works if it's here ?!?!?!
            int[] temp = new int[8];
            for(int j = 1; j < 8-1; j++)
            {
                if(cells[j-1] == cells[j+1])
                {
                    temp[j] = 1;
                }
                else
                {
                    temp[j] = 0;
                }

            }

            cells = temp;
            counter++;
        }

        return cells;
    }

Answer 1

请记住，即使int是值类型，数组也是引用类型，因此int[]是引用类型。(见What is the difference between a reference type and value type in c#?)

执行cells = temp;时，可以将cells和temp指向完全相同的数组！您可以使用以下代码对此进行测试：

int[] a = new int[2];
int[] b = a;

b[0] = 85;
b[1] = 3;

Console.WriteLine(a[0]); // prints 85
Console.WriteLine(a[1]); // prints 3

因此，这意味着在外部循环的第二次迭代中，以下代码同时更改了cells[j]和temp[j]

temp[j] = 1;

这显然意味着你会得到奇怪的结果。

因此，我认为您应该在循环中定义temp。

Answer 2

class Solution:
    def prisonAfterNDays(self, states: List[int], n: int) -> List[int]:
        # Since we have 6 cells moving cells (two wil remain unchaged at anytime) 
        # the cycle will restart after 14 iteration
        # 1- The number of days if smaller than 14 -> you brute force O(13)
        # 2- The number is bigger than 14
        #                       - You do a first round of 14 iteration
        #                       - Than you do a second round of n%14 iteration
        #                       ===> O(27)
        if n < 14:
            # iif n
            for _ in range(n):
                states = self.getNewStates(states)
        else:
            for _ in range(14):
                states = self.getNewStates(states)
            
            for _ in range(n%14):
                states = self.getNewStates(states)
                
        return states
    
    def getNewStates(self, states: List[int]) -> List[int]:
        newStates = ["0"] * len(states)
        for i in range(1, len(states)):
            if i != 0 and i != len(states) - 1 and states[i-1] == states[i+1]:
                newStates[i] = "1"
        return newStates