双缓冲技术

当数据量非常大时，画图可能须要几秒钟甚至更长的时间，并且有时还会出现闪屏现象，为了解决这些问题，采用双缓冲技术来画图。

双缓冲即在内存中创建一个与屏幕画图区域一致的对象，先将图形绘制到内存中的这个对象上，再一次性将这个对象上的图形复制到屏幕上，这样能大大加快画图的速度。双缓冲实现步骤例如以下：

  1. 在内存中创建与画布一致的缓冲区
  2. 创建位图并选入内存设备
  3. 在缓冲区绘图
  4. 将缓冲区位图复制到当前画布上
  5. 释放内存缓冲区

LeetCode例题

289. Game of Life
According to Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”

The board is made up of an m x n grid of cells, where each cell has an initial state: live (represented by a 1) or dead (represented by a 0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

  • Any live cell with fewer than two live neighbors dies as if caused by under-population.
  • Any live cell with two or three live neighbors lives on to the next generation.
  • Any live cell with more than three live neighbors dies, as if by over-population.
  • Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously. Given the current state of the m x n grid board, return the next state.

Example 1:

Input: board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]

Output: [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

原地更新技巧 - 图1

Example 2:

Input: board = [[1,1],[1,0]]
Output: [[1,1],[1,1]]

原地更新技巧 - 图2

Constraints:

  • 原地更新技巧 - 图3
  • 原地更新技巧 - 图4
  • 原地更新技巧 - 图5
  • 原地更新技巧 - 图6 is 0 or 1.

今天这道题是大学cs课程里大概率会说到的，实现起来也很简单。由于每个位置的细胞的状态是取决于当前四周其他状态的，而且每个细胞的状态是同时变化的，所以不能一个一个地更新，只能在一个新的数组里创建新的状态。

如果是额外开辟数组，有点像C++里的双缓冲技术。

当然上面所说的也不是绝对的，因为这道题目的输入是int[][]，而int是可以存储更多的比特位的。原有的最低位存储的是当前状态，那倒数第二低位存储下一个状态就行了。

方法一：位运算原地操作

一个 int 有 32 bit，输入数据只用了一个 bit，所以我们可以利用其他空闲的bit位进行“原地修改”。

  1. class Solution {
  2. public:
  3.     void gameOfLife(vector<vector<int>>& board) {
  4.         int dx[] = {-1,  0,  1, -1, 1, -1, 0, 1};
  5.         int dy[] = {-1, -1, -1,  0, 0,  1, 1, 1};
  7.         for(int i = 0; i < board.size(); i++) {
  8.             for(int j = 0 ; j < board[0].size(); j++) {
  9.                 int sum = 0;
  10.                 for(int k = 0; k < 8; k++) {
  11.                     int nx = i + dx[k];
  12.                     int ny = j + dy[k];
  13.                     if(nx >= 0 && nx < board.size() && ny >= 0 && ny < board[0].size()) {
  14.                         sum += (board[nx][ny]&1); // 只累加最低位
  15.                     }
  16.                 }
  17.                 if(board[i][j] == 1) {
  18.                     if(sum == 2 || sum == 3) {
  19.                         board[i][j] |= 2;  // 使用第二个bit标记是否存活
  20.                     }
  21.                 } else {
  22.                     if(sum == 3) {
  23.                         board[i][j] |= 2; // 使用第二个bit标记是否存活
  24.                     }
  25.                 }
  26.             }
  27.         }
  28.         for(int i = 0; i < board.size(); i++) {
  29.             for(int j = 0; j < board[i].size(); j++) {
  30.                 board[i][j] >>= 1; //右移一位，用第二bit覆盖第一个bit。
  31.             }
  32.         }
  33.     }
  34. };

方法二：使用额外的状态

题目中每个细胞只有两种状态 live(1) 或 dead(0)，但我们可以拓展一些复合状态使其包含之前的状态。举个例子，如果细胞之前的状态是 0，但是在更新之后变成了 1，我们就可以给它定义一个复合状态 2。这样我们看到 2，既能知道目前这个细胞是活的，还能知道它之前是死的。

针对本题，具体的计算规则如下所示：

  • 规则 1：如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡。这时候，将细胞值改为 -1，代表这个细胞过去是活的现在死了；
  • 规则 2：如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活。这时候不改变细胞的值，仍为 1；
  • 规则 3：如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡。这时候，将细胞的值改为 -1，代表这个细胞过去是活的现在死了。可以看到，因为规则 1 和规则 3 下细胞的起始终止状态是一致的，因此它们的复合状态也一致；
  • 规则 4：如果死细胞周围正好有三个活细胞，则该位置死细胞复活。这时候，将细胞的值改为 2，代表这个细胞过去是死的现在活了。

对于最终的输出，需要将 board 转成0，1 的形式。因此这时候需要再遍历一次数组，将复合状态为 2 的细胞的值改为 1，复合状态为 -1 的细胞的值改为 0。

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int neighbors[3] = {0, 1, -1};

        int rows = board.size();
        int cols = board[0].size();

        // 遍历面板每一个格子里的细胞
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {

                // 对于每一个细胞统计其八个相邻位置里的活细胞数量
                int liveNeighbors = 0;

                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {

                        if (!(neighbors[i] == 0 && neighbors[j] == 0)) {
                            // 相邻位置的坐标
                            int r = (row + neighbors[i]);
                            int c = (col + neighbors[j]);

                            // 查看相邻的细胞是否是活细胞
                            if ((r < rows && r >= 0) && (c < cols && c >= 0) && (abs(board[r][c]) == 1)) {
                                liveNeighbors += 1;
                            }
                        }
                    }
                }

                // 规则 1 或规则 3 
                if ((board[row][col] == 1) && (liveNeighbors < 2 || liveNeighbors > 3)) {
                    // -1 代表这个细胞过去是活的现在死了
                    board[row][col] = -1;
                }
                // 规则 4
                if (board[row][col] == 0 && liveNeighbors == 3) {
                    // 2 代表这个细胞过去是死的现在活了
                    board[row][col] = 2;
                }
            }
        }

        // 遍历 board 得到一次更新后的状态
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (board[row][col] > 0) {
                    board[row][col] = 1;
                } else {
                    board[row][col] = 0;
                }
            }
        }
    }
};