Easy state encoding to remember the old state as well as the new state, do not need bit manipulation


  • 0
    E

    define state change machine to remember the old state as well as the new result,
    case 1 -> 2 from live to dead
    case 2 -> 3 from live to live
    case 3 -> 4 from live to dead
    case 4 -> 5 from dead to live
    ask for in place, then count costs time...
    if ask for time efficiency, define a new 2D array for time saving

    public void gameOfLife(int[][] board) {
        if(board.length <= 0 && board[0].length <= 0) return;
        int m = board.length, n = board[0].length;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                int count = countNeighbor(board, i, j, m, n);
                if(board[i][j] == 1){
                    if(count < 2){
                        board[i][j] = 2;
                    }else if(count == 2 || count == 3){
                        board[i][j] = 3;
                    }else{
                        board[i][j] = 4;
                    }
                }else{
                    if(count == 3) board[i][j] = 5;
                }
            }
        }
        
        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;
                }else if(board[i][j] == 4){
                    board[i][j] = 0;
                }else if(board[i][j] == 5){
                    board[i][j] = 1;
                }
            }
        }
        return;
    }
    
    public int countNeighbor(int[][] board, int i, int j, int m, int n){
        int count = 0;
        // board[i][j] in [1, 4] means it is live in old state
        // board[i][j] in {0, 5} means it's dead in previous state
        if(i > 0 && j > 0 && board[i-1][j-1] >= 1 && board[i-1][j-1] <= 4) count++;
        if(i > 0 && board[i-1][j] >= 1 && board[i-1][j] <= 4) count++;
        if(i > 0 && j < n-1 && board[i-1][j+1] >= 1 && board[i-1][j+1] <= 4) count++;
        if(j > 0 && board[i][j-1] >= 1 && board[i][j-1] <= 4) count++;
        if(j < n-1 && board[i][j+1] >= 1 && board[i][j+1] <= 4) count++;
        if(i < m-1 && j < n-1 && board[i+1][j+1] >= 1 && board[i+1][j+1] <= 4) count++;
        if(i < m-1 && board[i+1][j] >= 1 && board[i+1][j] <= 4) count++;
        if(i < m-1 && j > 0 && board[i+1][j-1] >= 1 && board[i+1][j-1] <=4) count++;
        return count;
    }

Log in to reply
 

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