[LeetCode] Game of Life

简介: 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

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):

1. Any live cell with fewer than two live neighbors dies, as if caused by under-population.
2. Any live cell with two or three live neighbors lives on to the next generation.
3. Any live cell with more than three live neighbors dies, as if by over-population..
4. 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:

1. 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.
2. 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?

解题思路

题目要求就地解决问题,所以不能计算出结果之后马上更新该位置的值。因此我们考虑用十位个位分别表示下一代的值和当前代的值,计算live成员个数时,我们累加board[i][j] % 10的值,等用十位把所有位置都标记完后统一更新所有位置的值(board[i][j] /= 10)。

实现代码

C++:

// Runtime: 4 ms
class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        for (int i = 0; i < board.size(); i++)
        {
            for (int j = 0; j < board[0].size(); j++)
            {
                int num = numOfLive(board, i, j);
                if (board[i][j] == 1 && (num == 2 || num == 3) ||
                    board[i][j] == 0 && num == 3)
                {
                    board[i][j] += 10;
                }
            }
        }

        for (int i = 0; i < board.size(); i++)
        {
            for (int j = 0; j < board[0].size(); j++)
            {
                board[i][j] /= 10;
            }
        }
    }
private:
    int numOfLive(vector<vector<int>> board, int m, int n)
    {
        int res = 0;
        for (int i = m - 1; i <= m + 1; i++)
        {
            for (int j = n - 1; j <= n + 1; j++)
            {
                if (i < 0 || j < 0 || i > board.size() - 1 ||
                    j > board[0].size() - 1 || (i == m && j == n))
                {
                    continue;
                }
                res += board[i][j] % 10;
            }
        }

        return res;
    }
};

Java:

// Runtime: 1 ms
public class Solution {
    public void gameOfLife(int[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                int num = numOfLive(board, i, j);
                if (board[i][j] == 1 && (num == 2 || num == 3) ||
                        board[i][j] == 0 && num == 3) {
                    board[i][j] += 10;
                }
            }
        }

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                board[i][j] /= 10;
            }
        }
    }

    private int numOfLive(int[][] board, int m, int n) {
        int res = 0;
        for (int i = m - 1; i <= m + 1; i++) {
            for (int j = n - 1; j <= n + 1; j++) {
                if (i < 0 || j < 0 || i > board.length - 1 ||
                        j > board[0].length - 1 || (i == m && j == n)) {
                    continue;
                }
                res += board[i][j] % 10;
            }
        }

        return res;
    }
}
目录
相关文章
LeetCode 390. Elimination Game
给定一个从1 到 n 排序的整数列表。 首先,从左到右,从第一个数字开始,每隔一个数字进行删除,直到列表的末尾。 第二步,在剩下的数字中,从右到左,从倒数第一个数字开始,每隔一个数字进行删除,直到列表开头。 我们不断重复这两步,从左到右和从右到左交替进行,直到只剩下一个数字。 返回长度为 n 的列表中,最后剩下的数字。
78 0
LeetCode 390. Elimination Game
LeetCode 292. Nim Game
你和你的朋友,两个人一起玩 Nim游戏:桌子上有一堆石头,每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。 你们是聪明人,每一步都是最优解。 编写一个函数,来判断你是否可以在给定石头数量的情况下赢得游戏。
61 0
LeetCode 292. Nim Game
|
存储 算法
LeetCode 289. Game of Life
如果活细胞周围八个位置的活细胞数少于两个,则该位置活细胞死亡; 如果活细胞周围八个位置有两个或三个活细胞,则该位置活细胞仍然存活; 如果活细胞周围八个位置有超过三个活细胞,则该位置活细胞死亡; 如果死细胞周围正好有三个活细胞,则该位置死细胞复活;
58 0
LeetCode 289. Game of Life
|
算法 索引
LeetCode 55. Jump Game
给定一个非负整数数组,您最初定位在数组的第一个索引处。 数组中的每个元素表示该位置的最大跳转长度。 确定您是否能够到达最后一个索引。
78 0
LeetCode 55. Jump Game
|
算法 索引
LeetCode 45. Jump Game II
给定一个非负整数数组,初始位置在索引为0的位置,数组中的每个元素表示该位置的能够跳转的最大部署。目标是以最小跳跃次数到达最后一个位置(索引)。
62 0
LeetCode 45. Jump Game II
LeetCode contest 200 5476. 找出数组游戏的赢家 Find the Winner of an Array Game
LeetCode contest 200 5476. 找出数组游戏的赢家 Find the Winner of an Array Game
|
决策智能
LeetCode之Nim Game
LeetCode之Nim Game
111 0