class Solution {
public:
int dr[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dc[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
void gameOfLife(vector<vector<int>>& board) {
// 2: life -> life
// 3: lefe -> dead
// 4: dead -> dead
// 5: dead -> life
int m = board.size(), n = board[0].size();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int life = 0, dead = 0;
for (int k = 0; k < 8; k++) {
int nx = i + dr[k];
int ny = j + dc[k];
if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
if (board[nx][ny] == 1 || board[nx][ny] == 2 || board[nx][ny] == 3) life += 1;
else dead += 1;
}
if (life < 2 || life > 3) {
// to dead
if (board[i][j] == 0) board[i][j] = 4;
else board[i][j] = 3;
} else if (life == 3) {
// to life
if (board[i][j] == 0) board[i][j] = 5;
else board[i][j] = 2;
}
}
}
for (auto &x: board)
for (auto &y: x) {
if (y == 2 || y == 5) y = 1;
else if (y == 3 || y == 4) y = 0;
}
return;
}
};Time Complexity: O(m * n)
Space: O(1)
使用標記的技巧達到 Space O(1) 的做法
