【leetcode】289. 生命游戏

题目内容

思路分析

感觉本题最大的难点在于游戏规则，代码里很大一部分都是为了去描述游戏规则。其次如何把空间优化到O(1)也比较难想，本题的状态法就比较巧妙。

方法一：复制数组法

为避免新状态造成老状态的误判，直接将结果存至新的数组中。这样做一个很显然的缺点是很费空间，但是是可以通过的。

方法二：状态法

为避免新生成一个额外的数组，有一种聪明的办法是使用除0和1的数字来代表该细胞之前的状态。如：

过去	现在	状态码
死	活	-2
死	死	-1
活	死	2
活	活	3

这里有一个自认为自己比较聪明的设计是把过去是死的状态设为-2，-1，而初始就是死的状态是0，这样判断状态时直接一个≤0就能把这些都判断了。而过去是活的的状态是2和3，初始活的状态是1，也是直接一个≥1就判断了。

代码

#include <vector>
#include <math.h>
#include <limits.h>
#include <iostream>


using namespace std;

// 复制数组法
// 时间复杂度O(m*n),m、n为二维数组的两个维度大小
// 空间复杂度O(m*n)
class Solution1 {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int m = board.size();
        int n = board[0].size();
        vector<vector<int>> new_board(m);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int live_cell_num = 0;
                // 左上
                if (i != 0 && j != 0 && board[i - 1][j - 1] == 1) 
                    ++live_cell_num;
                // 上
                if (i != 0 && board[i - 1][j] == 1)
                    ++live_cell_num;
                // 右上
                if (i != 0 && j != n - 1 && board[i - 1][j + 1])
                    ++live_cell_num;
                // 左
                if (j != 0 && board[i][j - 1] == 1)
                    ++live_cell_num;
                // 右
                if (j != n - 1 && board[i][j + 1] == 1)
                    ++live_cell_num;
                // 左下
                if (i != m - 1 && j != 0 && board[i + 1][j - 1] == 1)
                    ++live_cell_num;
                // 下
                if (i != m - 1 && board[i + 1][j] == 1)
                    ++live_cell_num;
                // 右下
                if (i != m - 1 && j != n - 1 && board[i + 1][j + 1] == 1)
                    ++live_cell_num;
                // 判断下个状态
                if (board[i][j] == 1) {
                    if (live_cell_num < 2)
                        new_board[i].push_back(0);
                    else if (live_cell_num == 2 || live_cell_num == 3)
                        new_board[i].push_back(1);
                    else
                        new_board[i].push_back(0);
                } else {
                    if (live_cell_num == 3)
                        new_board[i].push_back(1);
                    else 
                        new_board[i].push_back(0);
                }
            }
        }
        board = new_board;
    }
};

// 状态法
// 时间复杂度O(m*n)
// 空间复杂度O(1)
class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int m = board.size();
        int n = board[0].size();
        // 过去 现在 状态
        // 死   活   -2
        // 死   死   -1
        // 活   死   2
        // 活   活   3
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int live_cell_num = 0;
                // 左上
                if (i != 0 && j != 0 && board[i - 1][j - 1] >= 1) 
                    ++live_cell_num;
                // 上
                if (i != 0 && board[i - 1][j] >= 1)
                    ++live_cell_num;
                // 右上
                if (i != 0 && j != n - 1 && board[i - 1][j + 1] >= 1)
                    ++live_cell_num;
                // 左
                if (j != 0 && board[i][j - 1] >= 1)
                    ++live_cell_num;
                // 右
                if (j != n - 1 && board[i][j + 1] >= 1)
                    ++live_cell_num;
                // 左下
                if (i != m - 1 && j != 0 && board[i + 1][j - 1] >= 1)
                    ++live_cell_num;
                // 下
                if (i != m - 1 && board[i + 1][j] >= 1)
                    ++live_cell_num;
                // 右下
                if (i != m - 1 && j != n - 1 && board[i + 1][j + 1] >= 1)
                    ++live_cell_num;
                // 判断下个状态
                if (board[i][j] == 1) {
                    if (live_cell_num < 2)
                        board[i][j] = 2;
                    else if (live_cell_num == 2 || live_cell_num == 3)
                        board[i][j] = 3;
                    else
                        board[i][j] = 2;
                } else {
                    if (live_cell_num == 3)
                        board[i][j] = -2;
                    else 
                        board[i][j] = -1;
                }
            }
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == -2 or board[i][j] == 3) 
                    board[i][j] = 1;
                else
                    board[i][j] = 0; 
            }
        }
    }
};

int main() {
   Solution s;
   vector<vector<int>> input = {{0,1,0},{0,0,1},{1,1,1},{0,0,0}};
//    vector<vector<int>> input = {{1,1},{1,0}};
   s.gameOfLife(input);
   cout << 1 << endl;
}

收获

状态法还是挺神奇的，就是不知道有没有其它用武之处。