LeetCode 289. 生命游戏

Categories:

题目描述
思路分析
1. 解法一：原地状态编码（推荐）
相似题目

题目描述

✅ 289. 生命游戏

思路分析

解法一：原地状态编码（推荐）

核心思路：

使用状态编码避免额外空间：0 死->死，1 活->活，2 活->死，3 死->活。

统计邻居时只看原始状态：1 和 2 都代表原来是活细胞。

第二次遍历将 2 置为 0、3 置为 1。

复杂度分析：

时间复杂度：O(mn)，其中 m、n 为网格行列数。

空间复杂度：O(1)，原地修改。

class Solution {
    public void gameOfLife(int[][] board) {
        int m = board.length;
        int n = board[0].length;
        int[] dirs = {-1, 0, 1};

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int live = 0;
                for (int dx : dirs) {
                    for (int dy : dirs) {
                        if (dx == 0 && dy == 0) {
                            continue;
                        }
                        int x = i + dx;
                        int y = j + dy;
                        if (x < 0 || x >= m || y < 0 || y >= n) {
                            continue;
                        }
                        if (board[x][y] == 1 || board[x][y] == 2) {
                            live++;
                        }
                    }
                }

                if (board[i][j] == 1 && (live < 2 || live > 3)) {
                    board[i][j] = 2;
                } else if (board[i][j] == 0 && live == 3) {
                    board[i][j] = 3;
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 2) {
                    board[i][j] = 0;
                } else if (board[i][j] == 3) {
                    board[i][j] = 1;
                }
            }
        }
    }
}

func gameOfLife(board [][]int) {
    m := len(board)
    n := len(board[0])
    dirs := []int{-1, 0, 1}

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            live := 0
            for _, dx := range dirs {
                for _, dy := range dirs {
                    if dx == 0 && dy == 0 {
                        continue
                    }
                    x := i + dx
                    y := j + dy
                    if x < 0 || x >= m || y < 0 || y >= n {
                        continue
                    }
                    if board[x][y] == 1 || board[x][y] == 2 {
                        live++
                    }
                }
            }

            if board[i][j] == 1 && (live < 2 || live > 3) {
                board[i][j] = 2
            } else if board[i][j] == 0 && live == 3 {
                board[i][j] = 3
            }
        }
    }

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if board[i][j] == 2 {
                board[i][j] = 0
            } else if board[i][j] == 3 {
                board[i][j] = 1
            }
        }
    }
}

相似题目

题目	难度	考察点
73. 矩阵置零	中等	原地标记
130. 被围绕的区域	中等	DFS
200. 岛屿数量	中等	网格遍历
994. 腐烂的橘子	中等	BFS
827. 最大人工岛	困难	网格

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/36562291