My C++ code (0ms, O(Row * Col) time, in place)


  • 3
    D

    Use the second bit of board[][] to save the new state

    class Solution {
    private:
        int countLiveNeighbor(vector<vector<int>>& board, int i, int j, int row, int col)
        {
            int m,n, count= -(board[i][j] & 0x1);
            for(m=max(0,i-1); m<min(row, i+2); ++m)
                for(n=max(0,j-1); n<min(col, j+2); ++n)
                    count += (board[m][n] & 0x1);
            return count ;
        }
    public:
        void gameOfLife(vector<vector<int>>& board) {
            int i, j, row, col;
            if( !(row=board.size()) || !(col=board[0].size()) ) return;
            
            for(i=0; i<row; ++i)
                for(j=0; j<col;j++)
                {
                    int liveN = countLiveNeighbor(board, i, j, row, col);
                    if(board[i][j]) board[i][j] += (liveN==3 || liveN ==2)? 2:0 ;
                    else board[i][j] = liveN==3?2:0;
                }
    
            for(i=0; i<row; ++i)
                for(j=0; j<col;j++)
                    board[i][j] = board[i][j]>>1 ;
        }
    };

Log in to reply
 

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