lc287 Game of Live

难点在于不能使用额外的空间。

观察到数组中每一个元素要么为1要么为0，32位int只用了一位，可以利用bit操作，将第二次state存储到int变量的倒数第二位中。例：board[i][j] = 3, 换成二进制就是一堆0最后两位是11，表达的含义就是当前状态cell为live，下一次状态还是live。

1）如何更新第一次state 直接把board[i][j]右移一位即可，这样就把第一次state更新为第二次state

2）如何更新第二次state 需要统计当前cell周围存活cell的数量，注意可能写code的时候边缘cell会导致数组越界，要添加判断条件Math.max(0, i-1), Math.max(0, j-1), Max.min(m, i+1), Math.max(n, j+1) 然后就可以按照规则更新第二次state，注意由于更新第一次state时使用的是右移操作，所以第二次state的默认值为0，就是说我们只需要处理第二次state为1的情况即可。

代码如下：

 class Solution {

     public void gameOfLife(int[][] board) {

         if(board == null || board.length == 0)

             return;

         int m = board.length;

         int n = board[0].length;

         for(int i = 0; i < m; ++i){

             for(int j = 0; j < n; ++j){

                 int lives = count(board, m, n, i, j);

                 if(board[i][j] == 1 && lives >= 2 && lives <= 3)

                     board[i][j] = 3;

                 else if(board[i][j] == 0 && lives == 3)

                     board[i][j] = 2;

             }

         }

         for(int i = 0; i < m; ++i){

             for(int j = 0; j < n; ++j){

                 board[i][j] >>= 1;

             }

         }

     }

     private int count(int[][] board, int m, int n, int i, int j){

         int count = 0;

         for(int a = Math.max(0, i-1); a <= Math.min(m - 1, i+1); a++){

             for(int b = Math.max(0, j-1); b <= Math.min(n-1, j+1); b++){

                 count += board[a][b] & 1;

             }

         }

         count -= board[i][j] & 1;

         return count;

     }

 }

巴特西

lc287 Game of Live

最新文章

热门文章