文章目录
- 写在前面
- Tag
- 题目来源
- 题目解读
- 解题思路
- 写在最后
写在前面
本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更……
专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删:
- Tag:介绍本题牵涉到的知识点、数据结构;
- 题目来源:贴上题目的链接,方便大家查找题目并完成练习;
- 题目解读:复述题目(确保自己真的理解题目意思),并强调一些题目重点信息;
- 解题思路:介绍一些解题思路,每种解题思路包括思路讲解、实现代码以及复杂度分析;
- 知识回忆:针对今天介绍的题目中的重点内容、数据结构进行回顾总结。
Tag
【矩阵】【数组】
题目来源
面试经典150 | 289. 生命游戏
![](https://img-blog.csdnimg.cn/img_convert/7a57fc7b7c66d93995a9cee77b7cddde.gif)
题目解读
根据一些四条生存规则来完成对网格面板的更新,并且更新是同时发生的。
解题思路
方法一: O ( m n ) O(mn) O(mn) 额外空间
八个方向
首先明确网格点的八个更新方向:左边、左上、正上、右上、右边、右下、正下、左下。我们可以嵌套枚举 dirs = [0, -1, 0]
来实现以上的八个方向。
四条生存准则
每个网格点代表一个细胞,每个细胞有一个状态,1
表示活细胞,0
表示死细胞,细胞的更新规则如下:
- (1)活细胞周围八个方向位置上活细胞数小于两个,该位置细胞死亡;
- (2)活细胞周围八个方向位置上的活细胞数等于两个或三个,该位置细胞仍然存活;
- (3)活细胞周围八个方向位置上活细胞数超过三个,该位置细胞死亡;
- (4)死细胞周围八个方向位置上活细胞数等于三个,该位置细胞复活;
枚举每一个网格上的细胞,如果是活细胞,那么按照规则(1)(2)(3)更新 board
;如果是死细胞,按照规则(4)更新 board
。
但是,需要复制 board
得到 copyBoard
,利用 copyBoard
来判断当前细胞的状态(死亡还是存活),更新最后的结果到 board
上。
实现代码
class Solution {
public:void gameOfLife(vector<vector<int>>& board) {int dirs[] = {0, -1, 1};int rows = board.size();int cols = board[0].size();vector<vector<int>> copyBoard = board;for (int row = 0; row < rows; ++row) {for (int col = 0; col < cols; ++col) {int cnts = 0; // 表示周围相邻的八个方向上活细胞的数量for (int i = 0; i < 3; ++i) {for (int j = 0; j < 3; ++j) {if (!(dirs[i] == 0 && dirs[j] == 0)) {int nRow = row + dirs[i];int nCol = col + dirs[j];// 更新 cntsif (nRow >= 0 && nRow < rows && nCol >= 0 && nCol < cols && copyBoard[nRow][nCol] == 1) cnts += 1;}}}// 规则(1)(3)if (copyBoard[row][col] == 1 && (cnts < 2 || cnts > 3)) board[row][col] = 0;// 规则(4)if (copyBoard[row][col] == 0 && cnts == 3)board[row][col] = 1;}}}
};
复杂度分析
时间复杂度: O ( m n ) O(mn) O(mn), m m m 为数组 board
的行数, n n n 为数组 board
的列数。
空间复杂度: O ( m n ) O(mn) O(mn),额外空间是辅助数组 copyBoard
使用的空间。
方法二: O ( 1 ) O(1) O(1) 额外空间
在本题中,如果细胞的状态发生了变化,一共只有两种:
- 细胞从存活的状态转变成死亡的状态;
- 细胞从死亡的状态转变成存活的状态。
于是,我们可以在按照规则进行判断时,如果 “细胞从存活的状态转变成死亡的状态”,我们将 board
中该位置的转态置为 -1
;如果 “细胞从死亡的状态转变成存活的状态”,我们将 board
中该位置的状态置为 2
。这里的 -1
和 2
可以是任意的数字,只要不和 0
、1
重复即可。
需要注意的是,判断当前网格细胞是否是存活状态还要考虑 board[row][col] = -1
的情况。
最后,遍历 board
,根据表示 “细胞从存活的状态转变成死亡的状态” 的 -1
,将 board
中该位置置为 0
,根据表示 “细胞从死亡的状态转变成存活的状态” 的 2
,将 board
中该位置置为 1
。
实现代码
class Solution {
public:void gameOfLife(vector<vector<int>>& board) {int dirs[] = {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 cnts = 0; // 表示周围相邻的八个方向上活细胞的数量for (int i = 0; i < 3; ++i) {for (int j = 0; j < 3; ++j) {if (!(dirs[i] == 0 && dirs[j] == 0)) {int nRow = row + dirs[i];int nCol = col + dirs[j];// 更新 cntsif (nRow >= 0 && nRow < rows && nCol >= 0 && nCol < cols && (abs(board[nRow][nCol]) == 1)) cnts += 1;}}}// 规则(1)(3)if (board[row][col] == 1 && (cnts < 2 || cnts > 3)) board[row][col] = -1;// 规则(4)if (board[row][col] == 0 && cnts == 3)board[row][col] = 2;}}for (int row = 0; row < rows; ++row) {for (int col = 0; col < cols; ++col) {if (board[row][col] == -1) board[row][col] = 0;if (board[row][col] == 2) board[row][col] = 1;}}}
};
复杂度分析
时间复杂度: O ( m n ) O(mn) O(mn), m m m 为数组 board
的行数, n n n 为数组 board
的列数。
空间复杂度: O ( 1 ) O(1) O(1)。
写在最后
如果文章内容有任何错误或者您对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度方法,欢迎评论区交流。
最后,感谢您的阅读,如果感到有所收获的话可以给博主点一个 👍 哦。