LeetCode 289 Game of Life(生命游戏)(Array)

简介: 版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/52122735 翻译根据维基百科的文章介绍:“Game of Life,简称为Life,是一个被英国数学家John Conway在1970年提出的细胞自动分裂器。
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/52122735

翻译

根据维基百科的文章介绍:“Game of Life,简称为Life,是一个被英国数学家John Conway在1970年提出的细胞自动分裂器。”

给定一个m x n的空间,每个细胞有一个初始状态live(1)或dead(0)。每个细胞通过下面4种方式和周围的8个邻居交互(垂直、水平、交叉):

1,当前细胞为存活状态时,当周围低于2个(不包含2个)存活细胞时, 该细胞变成死亡状态。(模拟生命数量稀少)
2,当前细胞为存活状态时,当周围有2个或3个存活细胞时, 该细胞保持原样。
3,当前细胞为存活状态时,当周围有3个以上的存活细胞时,该细胞变成死亡状态。(模生命数量过多)
4,当前细胞为死亡状态时,当周围有3个存活细胞时,该细胞变成存活状态。 (模拟繁殖)

写一个函数用于计算空间的给定状态的下一个状态(当某个更新后)。

跟进:
1,你可以就地解决吗?记住这空间需要同时更新:你不能只首先更新一部分,然后用这些新的状态去更新别的细胞。
2,在这个问题,我们使用了二维数组。原则上,这个空间是无限大的,当这些变化影响到边界时,你是如何解决的?

原文

According to the Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”

Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

Any live cell with fewer than two live neighbors dies, as if caused by under-population.
Any live cell with two or three live neighbors lives on to the next generation.
Any live cell with more than three live neighbors dies, as if by over-population..
Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
Write a function to compute the next state (after one update) of the board given its current state.

Follow up:
Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?

分析

好久没有写算法了,都不习惯了。所以也就没解出来,参考了网上的答案,但还是说说分析过程吧。

细胞变为“活”,只有两种可能。当它本来为存活态时,邻居有2或3个时保持原来的状态,也就是“活”。还有一种是,当原本为死亡态时,邻居有3个时,也会变为“活”。

其余状态,要么是由存活态变为死亡态,要么就是保持死亡态。

我们通过加上10来保存这个细胞的状态,最后统一进行刷新,这也就是这个问题的核心。

if (count == 3 || (count == 2 && board[r][c] == 1)) board[r][c] += 10;

但因为是数组,所以也有边界。以后再用可变的数组修改吧,挺有意思的题目。两年前就听说了康威生命游戏,大家可以去看看它的Wiki。

代码

C Plus Plus

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        for (int r = 0; r < board.size() ; r++) {
            for (int c = 0; c < board[r].size(); c++) {
                int count = countNeighbors(board, r, c);
                if (count == 3 || (count == 2 && board[r][c] == 1)) board[r][c] += 10;
            }
         }
         flashBoard(board);
    }
    int countNeighbors(const vector<vector<int>>& board, int r, int c) {
         int count = 0;
         for (int row  = max(r - 1, 0) ; row <= min(r + 1, (int) board.size() - 1); row ++) {
              for (int col = max(c - 1, 0); col <= min(c + 1, (int) board[row].size() - 1); col ++) {
                 if (row != r || col != c) count += board[row][col] % 10;
              }
         }
         return count;
    }
    void flashBoard(vector<vector<int>>& board) {
         for (int i = 0; i < board.size(); i++) {
             for (int j = 0; j < board[i].size(); j++) {
                 board[i][j] = board[i][j] / 10;
             }
        }
    }
};

Java

updated at 2016/09/04
    public void gameOfLife(int[][] board) {
        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c <board[r].length; c++) {
                int count = countNeighbors(board, r, c);
                if (count == 3 || (count == 2 && board[r][c] == 1))
                    board[r][c] += 10;
            }
        }
        flashBoard(board);
    }

    int countNeighbors(int[][] board, int r, int c) {
        int count = 0;
        for (int row = Math.max(r - 1, 0); row <= Math.min(r + 1, (int)board.length - 1); row++) {
            for (int col = Math.max(c - 1, 0); col <= Math.min(c + 1, (int)board[row].length - 1); col++) {
                if (row != r || col != c)
                    count += board[row][col] % 10;
            }
        }
        return count;
    }

    void flashBoard(int[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                board[i][j] = board[i][j] / 10;
                System.out.println("b = " + board[i][j]);
            }
        }
    }
目录
相关文章
|
2月前
|
算法
Leetcode第45题(跳跃游戏II)
这篇博客文章讨论了如何使用贪心算法解决LeetCode第45题“跳跃游戏II”,目的是找到使用最少跳跃次数到达数组末尾的策略。
91 8
Leetcode第45题(跳跃游戏II)
|
4月前
|
算法
LeetCode第55题跳跃游戏
LeetCode第55题"跳跃游戏"的解题方法,通过记录当前最远可达到的位置并判断每个位置是否可达以及能否到达末尾,有效解决了跳跃至数组末尾的可行性问题。
LeetCode第55题跳跃游戏
|
2月前
Leetcode第55题(跳跃游戏)
LeetCode第55题“跳跃游戏”要求判断在一个非负整数数组中,从第一个位置出发,是否能够到达最后一个位置,其中每个位置的元素代表可跳跃的最大长度。
33 0
|
4月前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
54 1
|
4月前
|
算法
LeetCode第45题跳跃游戏 II
LeetCode第45题"跳跃游戏 II"的解题方法,通过一次循环和选择每个位置的最大可跳距离,有效减少了跳跃次数,简化了问题。
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
63 6
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
125 2
|
1月前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
43 1
|
3月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口