专栏首页小浩算法漫画:生命游戏(头条、Google 面试题)

漫画:生命游戏(头条、Google 面试题)

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

01

PART

生命游戏

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

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

每个细胞与其八个相邻位置(水平,垂直,对角线)的细胞都遵循以下四条生存定律:

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

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

题目有点复杂,举例说明:

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

02

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题 矩阵置零,也是类似的解法。

03

PART

每日算法

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

我要开始认认真真的写题解了~

啦啦啦啦啦啦

嘿吼!

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员小浩

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-31

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剑指offer 03:二维数组中的查找

    在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个...

    程序员小浩
  • 万字长文!位运算面试看这篇就够了!

    祝大家五一快乐。今天是小浩算法 “365刷题计划” 位运算超长 - 整合篇。估计五一期间,大家也没有什么心思好好做题。所以我就把之前已经出过的位运算系列,进行了...

    程序员小浩
  • 漫画:算法如何验证合法数独 | 全世界最难的数独?

    今天是小浩算法 “365刷题计划” 第95天 。数独相信在座的各位都玩过,那我们如何使用程序去验证一个 9×9 的数独是有效的呢?一起看下!

    程序员小浩
  • 力扣309——最佳买卖股票时机含冷冻期

    设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

    健程之道
  • Spring 的 AOP 概述和底层实现

    所谓连接点是指那些可以被拦截的点。在 spring 中,这些点指的是方法,因为 spring 只支持方法类型的连接点。

    希希里之海
  • 动态代理的介绍(非aop) 基于接口 基于子类 举例说明

    举例:卖东西 前提:有一个接口IProducer,一个实现类Producer(最后我会附上这部分的代码(“动态代理介绍”) IProducer proxyPro...

    韦恩少爷的背
  • HDU-5558-Alice's Classified Message

    ACM模版 描述 ? 题解 image.png 参考博客:Gatevin’s blog 代码 #include <iostream> #include <alg...

    f_zyj
  • Less Coin Tosses(Gym - 102346L)【打表+找规律】

    1.题意说的是给定你n位的二进制串,除了成对的(就是指那些1的个数相同或0的个数相同的),那些不成对的数有几个。比如n为3时,可以有000,001,010,01...

    _DIY
  • nature文章也要挖掘单细胞公共数据

    组会课题组的博士后分享了一篇nature文章,发表于2019年6月,题目是:CD24 signalling through macrophage Siglec-...

    生信技能树jimmy
  • Android App启动图启动界面(Splash)的简单实现代码

    p 第三步:将准备好的启动图片放到drawable目录下,并修改Splash的xml布局文件,如下图所示

    砸漏

扫码关注云+社区

领取腾讯云代金券