LeetCode 289 Game of Life

    
        标签：
        
            数组类题目
        
            LeetCode
        
    发布于：2022-03-07 15:36:55
    编辑于：2022-03-07 15:54:08
    浏览量：765

概述

https://leetcode.com/problems/game-of-life/

分配额外数组的解法

维护一个 counter 矩阵，用来存储该处的存活邻居数目。

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        vector<vector<int>> counter(board.size(), vector<int>(board[0].size()));
        for (int i = 0 ; i < board.size(); i ++) {
            for (int j = 0; j < board[0].size(); j ++) {
                if (board[i][j] == 1) {
                    for (int m = -1; m <= 1; m ++) {
                        for (int n = -1; n <= 1; n ++) {
                            if (m == 0 && n == 0) continue;
                            if (i + m >= 0 && i + m < board.size() && j + n >= 0 && j + n < board[0].size()) {
                                counter[i+m][j+n] ++;
                            }
                        }
                    }
                }
            }
        }
        for (int i = 0 ; i < board.size(); i ++) {
            for (int j = 0; j < board[0].size(); j ++) {
                if (counter[i][j] == 3) {
                    board[i][j] = 1;
                } else if (board[i][j] == 1 && counter[i][j] == 2) {
                    board[i][j] = 1;
                } else {
                    board[i][j] = 0;
                }
            }
        }
    }
};

位运算

想不到吧，原本的 int 数组只用了 1 个bit，我们可以用右起第二个 bit 来存储未来的值，之后右移就好了。

https://leetcode.com/problems/game-of-life/discuss/73230/C%2B%2B-O(1)-space-O(mn)-time

实现的时候，

可以用 max 和 min 来搞掉那些恶心的边界检查。
计数的时候把自己也统计进去也没关系，我们减掉就好了。

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int h = board.size(), w = board[0].size();
        for (int i = 0 ; i < h; i ++) {
            for (int j = 0; j < w; j ++) {
                int count = 0;
                for (int m = max(0, i - 1); m < min(h, i + 2); m ++) {
                    for (int n = max(0, j - 1); n < min(w, j + 2); n ++) {
                        count += board[m][n] & 1;
                    }
                }
                if (count == 3 || count - board[i][j] == 3) {
                    board[i][j] |= 2;
                }
            }
        }
        for (int i = 0 ; i < h; i ++) {
            for (int j = 0; j < w; j ++) {
                board[i][j] >>= 1;
            }
        }
    }
};

Links: leetcode-289-game-of-life