Ac solution code


  • 0

    The basic idea is updating one grid(board[i][j]) with the number of its liveNeighbors, according to the rules in the question.

    The only trick is using two bits to store the grid's states in-place: 00, 01, 10, 11

    1) low  bit: currState    
    2) high bit: nextState
    

    JAVA Code: O(nm) runtime; O(1) space*

    public void gameOfLife(int[][] board) {
    	if (board == null || board.length == 0) return;
    	int n = board.length, m = board[0].length;
        for(int i = 0; i < n; i++) { 
        	for (int j = 0; j < m; j++) {
        		updateGrid(board, i, j);// Update one grid(board[i][j]) with the number of its liveNeighbors
        	}
        }        
        for(int i = 0; i < n; i++) {
        	for (int j = 0; j < m; j++) {
        		board[i][j] >>= 1;// Update the current state with nextState (in high bit)
        	}
        }
    }	
    private void updateGrid(int[][]board, int i, int j) {// Update one grid(board[i][j]) with the number of its liveNeighbors
    	Point directions[] = {new Point(0, 1), new Point(0, -1), new Point(1, 0), new Point(-1, 0), new Point(1, 1), new Point(1, -1), new Point(-1, 1), new Point(-1, -1)};
    	int liveNeighbors = 0;
    	for (Point d : directions) { 
    		if (i+d.x>=0 && i+d.x < board.length && j+d.y >=0 && j+d.y < board[0].length && (board[i+d.x][j+d.y] & 1) == 1) {// Check low bit
    			liveNeighbors++;
    		}
    	}    	
    	int nextState = board[i][j];
    	if (liveNeighbors < 2) nextState = 0; 		 // Any live cell with fewer than two live neighbors dies, as if caused by under-population.    		
    	else if (liveNeighbors == 3) nextState = 1;  // Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.        	      	
    	else if (liveNeighbors > 3) nextState = 0;   // Any live cell with more than three live neighbors dies, as if by over-population..    		 	 		
    	board[i][j] |= nextState << 1;  		   	 // Set nextState to high bit
    }

Log in to reply
 

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