C++ AC Code O(1) space, O(mn) time


  • 46
    L
    // Game of Life
    /*
    状态: 前一位表示下一代的状态,后一位表示当前的状态
    00: 死->死
    10: 死->活
    01: 活->死
    11: 活->活
    */
    class Solution {
    public:
        void gameOfLife(vector<vector<int>>& board) {
            int d[][2] = {{1,-1},{1,0},{1,1},{0,-1},{0,1},{-1,-1},{-1,0},{-1,1}};
            for(int i = 0; i < board.size(); i++){
                for(int j = 0; j < board[0].size(); j++){
                    int live = 0;
                    for(int k = 0; k < 8; k++){
                        int x = d[k][0] + i;
                        int y = d[k][1] + j;
                        if(x < 0 || x >= board.size() || y < 0 || y >= board[0].size()) {
                            continue;
                        }
                        if(board[x][y] & 1) {
                            live++;
                        }
                    }
                    // 死的
                    if(board[i][j] == 0) {
                        if(live == 3){
                            board[i][j] = 2; // 2 : (10)
                        }
                    }
                    // 活的
                    else {
                        if(live < 2 || live > 3){
                            board[i][j] = 1; // 1 : (01)
                        }else{
                            board[i][j] = 3; // 3 : (11)   
                        }
                    }
                }
            }
            for(int i = 0; i < board.size(); i++){
                for(int j=0; j < board[0].size(); j++){
                    board[i][j] >>=1;
                }
            }
        }
    };enter code here

  • 0
    R
    This post is deleted!

  • 0
    G

    wow, it is clever to use the higher bit to store info for previous round!
    I used extra two rows to store the latest status of current and previous row.


  • 0
    C

    Better translate the Chinese into English


  • 0
    T

    00: 死->死 :die->die
    10: 死->活: die->alive
    01: 活->死: alive->die
    11: 活->活: alive->alive
    The left digit means next state, and right digit means current state.


  • 0
    A

    Lol at the chinese comments....lol.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.