漫画：生命游戏（头条、Google 面试题）

程序员小浩

发布于 2020-06-03 15:52:54

5940

发布于 2020-06-03 15:52:54

文章被收录于专栏：小浩算法

今天是小浩算法“365刷题计划”第102天。每个人的起点和终点都是一样的，但过程却各不相同。我们无法主宰生死却可以选择如何让生命有意义。我们如何用算法来进行一场生命的游戏呢！

PART

生命游戏

生命游戏，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1 即为活细胞（live），或 0 即为死细胞（dead）。

每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
如果死细胞周围正好有三个活细胞，则该位置死细胞复活；

根据当前状态，写一个函数来计算面板上所有细胞的下一个（一次更新后的）状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。

题目有点复杂，举例说明：

注意：面板上所有格子需要同时被更新：你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。

PART

题解分析

这道题目的关键点是：面板上所有格子需要同时被更新

本题的复杂主要复杂在 4 个更新规则，所以我们需要先对 4 个规则进行掌握（我们仅对下面绿色标出的元素进行说明）

R1：细胞数少于两个，则该位置活细胞死亡

R2：有两个或三个活细胞，则该位置活细胞仍然存活

R3：有超过三个活细胞，则该位置活细胞死亡

R4：有三个活细胞，则该位置死细胞复活

四个规则理解起来并不复杂，现在考虑如何解决问题。最自然的想法是：一个个的更新细胞状态。

但是这里我们会遇到一个问题：假设你每次更新完毕后，都把更新后的结果填入数组。那么当前轮其他格子的更新就会引用到你已经更新的结果。啥意思呢：

比如上面这个就是错误的：我们先依据规则4更新了绿色框处的状态，此时蓝色框色周围同样满足规则4。已更新细胞的状态会影响到周围其他还未更新细胞状态的计算。这明显不是我们想要的！

那我们最简单的思路：是不是只要我们能一直获取原始数组的数据，不就可以保证更新一直正确了吗！至于在哪里，其实不管是copy一个数组，还是说用hashmap存一下数值其实都ok。

因为这种思路相对比较简单，我就直接上 leetcode 官方题解的代码了：

//JAVA
class Solution {
    public void gameOfLife(int[][] board) {

        int[] neighbors = {0, 1, -1};

        int rows = board.length;
        int cols = board[0].length;

        // 创建复制数组 copyBoard
        int[][] copyBoard = new int[rows][cols];

        // 从原数组复制一份到 copyBoard 中
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                copyBoard[row][col] = board[row][col];
            }
        }

        // 遍历面板每一个格子里的细胞
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {

                // 对于每一个细胞统计其八个相邻位置里的活细胞数量
                int liveNeighbors = 0;

                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {

                        if (!(neighbors[i] == 0 && neighbors[j] == 0)) {
                            int r = (row + neighbors[i]);
                            int c = (col + neighbors[j]);

                            // 查看相邻的细胞是否是活细胞
                            if ((r < rows && r >= 0) && (c < cols && c >= 0) && (copyBoard[r][c] == 1)) {
                                liveNeighbors += 1;
                            }
                        }
                    }
                }

                // 规则 1 或规则 3      
                if ((copyBoard[row][col] == 1) && (liveNeighbors < 2 || liveNeighbors > 3)) {
                    board[row][col] = 0;
                }
                // 规则 4
                if (copyBoard[row][col] == 0 && liveNeighbors == 3) {
                    board[row][col] = 1;
                }
            }
        }
    }
}

然后有意思的事情发生了，大神之所以是大神，就是大神的思路和普通人不一样。大神说，你这种方法可以是可以，但是占用了新的空间。

你不就想既可以保存原数组的状态，还可以更新新的状态吗？这些统统都可以在原有数组上搞。具体怎么搞呢？

原来的 0 和 1 不就是代表死和生吗？但是你要更新新的状态，无非就是从生->死，从死->生。那我们加个状态 2，代表生->死，加个状态 3 表示从死>生。
对于一个节点来说，如果它周边的点是 1 或者 2，就说明该点上一轮是活的。
整体策略是完成原始状态->过渡状态->真实状态的过程。
过渡状态到真实状态，代码就是把 0 和 2 变回 0，1 和 3 变回1的过程。用模只是代码技巧。
策略实现的第一步是先找到当前节点周围的存活节点数。

代码大概就是这样：

//JAVA
public class Solution {
    public void gameOfLife(int[][] board) {
        int m = board.length, n = board[0].length;
        // 原始状态 -> 过渡状态
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                int liveNeighbors  = 0;
                // 判断上边
                if(i > 0){
                    liveNeighbors  += board[i - 1][j] == 1 || board[i - 1][j] == 2 ? 1 : 0;
                }
                // 判断左边
                if(j > 0){
                    liveNeighbors  += board[i][j - 1] == 1 || board[i][j - 1] == 2 ? 1 : 0;
                }
                // 判断下边
                if(i < m - 1){
                    liveNeighbors  += board[i + 1][j] == 1 || board[i + 1][j] == 2 ? 1 : 0;
                }
                // 判断右边
                if(j < n - 1){
                    liveNeighbors  += board[i][j + 1] == 1 || board[i][j + 1] == 2 ? 1 : 0;
                }
                // 判断左上角
                if(i > 0 && j > 0){
                    liveNeighbors  += board[i - 1][j - 1] == 1 || board[i - 1][j - 1] == 2 ? 1 : 0;
                }
                //判断右下角
                if(i < m - 1 && j < n - 1){
                    liveNeighbors  += board[i + 1][j + 1] == 1 || board[i + 1][j + 1] == 2 ? 1 : 0;
                }
                // 判断右上角
                if(i > 0 && j < n - 1){
                    liveNeighbors  += board[i - 1][j + 1] == 1 || board[i - 1][j + 1] == 2 ? 1 : 0;
                }
                // 判断左下角
                if(i < m - 1 && j > 0){
                    liveNeighbors  += board[i + 1][j - 1] == 1 || board[i + 1][j - 1] == 2 ? 1 : 0;
                }
                // 根据周边存活数量更新当前点，结果是 0 和 1 的情况不用更新
                if(board[i][j] == 0 && liveNeighbors  == 3){
                    board[i][j] = 3;
                } else if(board[i][j] == 1){
                    if(liveNeighbors  < 2 || liveNeighbors  > 3) board[i][j] = 2;
                }
            }
        }
        // 过渡状态 -> 真实状态
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                board[i][j] = board[i][j] % 2;
            }
        }
    }
}

细心的读者也许会想到，这不就是卡诺图吗？是的。在大多数的矩阵状态变化类题目中，卡诺图、状态机等都是一些常用的技巧。

一般的通用解法为：

1、大部分都是遍历两次矩阵，第一遍引入中间值（中间状态），存储一些原矩阵不包含的额外信息。

2、通过原始矩阵->过渡矩阵->真实矩阵的策略，在结尾处将中间状态置成真实状态。

3、当遍历到某个位置时，需要查看它周边的位置，此时如果每一个周围的位置都手写，然后再判断是否越界，就很麻烦。一般用一个数组，保存向周边位置变化的坐标偏移值。

4、如果是 0 和 1 的状态置换，可以使用位运算来秀操作。如果涉及状态过多，考虑是否可以简化状态。

总之：这是一道相对比较经典的题目，如果大家有兴趣，大家可以练习一下第73题矩阵置零，也是类似的解法。

PART

每日算法

宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。