LeetCode 289.生命游戏

289.生命游戏

思路：

从题目的设计来看，要求是根据当前的数组中每个值周边的值来更新当前值，但是前提是都是考虑的周边的原始值，而非更新后的值。

最开始想到的是先拷贝一个数组，但是题目中建议不使用额外空间解决，即在原数组上操作。

首先考虑的解决办法是位运算，因为原始值是int类型，有32位长度，而题中值只为0/1，那么仅仅占用了一个bit。

• 位运算
  • 原来的第一位不改变，用第二位保存更新后的值。
  • 获取周边原始值的时候，只获取第一位的值进行判断。
  • 在整体更新完后，每个值进行位右移运算。

class Solution {
    public void gameOfLife(int[][] board) {
        int m = board.length;
        int n = board[0].length;
        int[] dx = new int[]{-1, 0, 1, -1, 1, -1, 0, 1};
        int[] dy = new int[]{-1, -1, -1, 0, 0, 1, 1, 1};
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int countLive = 0;
                for (int k = 0; k < 8; k++) {
                    int newX = i + dx[k];
                    int newY = j + dy[k];
                    if (newX < 0 || newX >= m || newY < 0 || newY >= n) {
                        continue;
                    }
                    countLive += board[newX][newY] & 1;
                }
                if (board[i][j] == 1) {
                    if (countLive == 2 || countLive == 3) {
                        board[i][j] |= 2;
                    }
                } else {
                    if (countLive == 3) {
                        board[i][j] |= 2;
                    }
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] >>= 1;
            }
        }
    }
}

• 使用额外状态（参考解题思路的一种解法，类似位操作）
  • 与位运算不同的是，在原有的状态值0/1增加了两个新的细胞的状态值2/-1
  • -1代表细胞值由0变为1
  • 2代表细胞值由1变为0

class Solution {
    public void gameOfLife(int[][] board) {
        int m = board.length;
        int n = board[0].length;
        int[] dx = new int[]{-1, 0, 1, -1, 1, -1, 0, 1};
        int[] dy = new int[]{-1, -1, -1, 0, 0, 1, 1, 1};
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int countLive = 0;
                for (int k = 0; k < 8; k++) {
                    int newX = i + dx[k];
                    int newY = j + dy[k];
                    if (newX < 0 || newX >= m || newY < 0 || newY >= n) {
                        continue;
                    }
                    if (board[newX][newY] == 1 || board[newX][newY] == 2) {
                        countLive++;
                    }
                }
                if (board[i][j] == 1) {
                    if (countLive < 2 || countLive > 3) {
                        board[i][j] = 2;
                    }
                } else {
                    if (countLive == 3) {
                        board[i][j] = -1;
                    }
                }
            }
        }
        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] == -1) {
                    board[i][j] = 1;
                }
            }
        }
    }
}