ChunNote
0%

leetCode-289:Game of Life

发表于 分类于

问题描述

给定一个二维数组，数组每个元素表示一个细胞，数组值 0 表示细胞死亡，数组值 1 表示细胞生存。细胞在经过一轮细胞周期会根据下面规则改变其生存状态。

  • 如果细胞周围的八个细胞中的生存数量小于2个，则细胞死亡
  • 如果细胞周围的八个细胞中的生存数量有两个或三个，则活细胞仍然生存
  • 如果细胞周围的八个细胞中的生存数量大于3个，则细胞死亡
  • 如果细胞周围的八个细胞中的生存数量刚好是3个，则死亡细胞会复活。

给定一组细胞状态，要求在 O(1) 的空间复杂度内求出经过一轮细胞周期后的细胞状态，注意细胞状态变更是同时发生的，不能依赖于上一轮的变更。题目链接：**点我**

样例输入输出

输入：[[0,1,0],[0,0,1],[1,1,1],[0,0,0]]

输出：[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

输入：[[1,1],[1,0]]

输出：[[1,1],[1,1]]

问题解法

此题不难，主要是读懂规则，其实就是周围的活细胞数量是 2 时状态保持不变，周围活细胞数量是 3 时细胞变活，其他情况细胞变死。另外需要注意的是需要 O(1) 的空间复杂度，也就是说不能新建数组，需要在原有的数组基础上进行修改，由于细胞状态的变更是同时发生的，因此不能在循环中直接将 0 变成 1，也不能在循环中将 1 直接变成 0，不然某个位置发生了变更，周围的细胞在进行判断时就会变成依赖变更后的状态了。针对此种情况，可以新增两个状态：活转死、死转活。在进行活细胞的判断时，把 “活转死” 这个状态考虑进去即可。最后再遍历数组把 “活转死” 状态变成 0， 把 “死转活” 状态变成 1。代码如下

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
class Solution {
    private static final int DIE_TO_LIVE = 2;

    private static final int LIVE_TO_DIE = 3;

    public void gameOfLife(int[][] board)
    {
        for (int i = 0; i < board.length; i++)
        {
            for (int j = 0; j < board[0].length; j++)
            {
                int count = calcLiveNeighbors(board, i, j);
                if (count == 2)
                {
                    continue;
                }
                else if (count == 3)
                {
                    if (board[i][j] == 0)
                    {
                        board[i][j] = DIE_TO_LIVE;
                    }
                }
                else
                {
                    if (board[i][j] == 1)
                    {
                        board[i][j] = LIVE_TO_DIE;
                    }
                }
            }
        }

        for (int i = 0; i < board.length; i++)
        {
            for (int j = 0; j < board[0].length; j++)
            {
                if (board[i][j] == DIE_TO_LIVE)
                {
                    board[i][j] = 1;
                }
                else if (board[i][j] == LIVE_TO_DIE)
                {
                    board[i][j] = 0;
                }
            }
        }
    }

    private int calcLiveNeighbors(int[][] board, int i, int j)
    {
        int liveCount = 0;
        if (isValidCellLive(board, i - 1, j))
        {
            liveCount++;
        }

        if (isValidCellLive(board, i - 1, j + 1))
        {
            liveCount++;
        }

        if (isValidCellLive(board, i, j + 1))
        {
            liveCount++;
        }

        if (isValidCellLive(board, i + 1, j + 1))
        {
            liveCount++;
        }

        if (isValidCellLive(board, i + 1, j))
        {
            liveCount++;
        }

        if (isValidCellLive(board, i + 1, j - 1))
        {
            liveCount++;
        }

        if (isValidCellLive(board, i, j - 1))
        {
            liveCount++;
        }

        if (isValidCellLive(board, i - 1, j - 1))
        {
            liveCount++;
        }

        return liveCount;
    }

    private boolean isValidCellLive(int[][] board, int i, int j)
    {
        return i >=0 && i < board.length && j >= 0 && j < board[0].length && isLive(board[i][j]);
    }

    private boolean isLive(int cell)
    {
        return cell == 1 || cell == LIVE_TO_DIE;
    }
}