Description:
https://leetcode.com/problems/game-of-life/#/description
Algorithm:
Use state machine to finish in-place.
Code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
class Solution { public: void gameOfLife(vector<vector>& board) { int m = board.size(); if (m == 0) return; int n = board[0].size(); if (n == 0) return; for (int i = 0; i < m;i++) { for (int j = 0; j < n;j++) { if (changeState(board, i, j, m, n)) { if (board[i][j] % 2 == 1) board[i][j] = 1; else board[i][j] = 3; } else { if (board[i][j] % 2 == 1) board[i][j] = 2; else board[i][j] = 0; } } } for (int i = 0; i < m;i++) { for (int j = 0; j < n;j++) { board[i][j] = board[i][j] % 2; } } } private: bool changeState(vector<vector>board, int i, int j, int m, int n) { int count = 0; if (i - 1 >= 0 && j - 1 >= 0 && (board[i - 1][j - 1] == 1 || board[i - 1][j - 1] == 2)) count++; if (i - 1 >= 0 && (board[i - 1][j] == 1 || board[i - 1][j] == 2)) count++; if (i - 1 >= 0 && j + 1 < n && (board[i - 1][j + 1] == 1 || board[i - 1][j + 1] == 2)) count++; if (j + 1 < n && (board[i][j + 1] == 1 || board[i][j + 1] == 2)) count++; if (j - 1 >= 0 && (board[i][j - 1] == 1 || board[i][j - 1] == 2)) count++; if (i + 1 < m && j - 1 >= 0 && (board[i + 1][j - 1] == 1 || board[i + 1][j - 1] == 2)) count++; if (i + 1 < m && (board[i + 1][j] == 1 || board[i + 1][j] == 2)) count++; if (i + 1 < m && j + 1 < n && (board[i + 1][j + 1] == 1 || board[i + 1][j + 1] == 2)) count++; if (board[i][j] == 1 && (count == 3 || count == 2)) return true; if (board[i][j] == 0 && count == 3) return true; return false; } }; |
Time & Space:
O(n) & O(1)