©2020-2024 ioDraw All rights reserved
该题首先题目较长，我们一定遇到这种题目要好好审题再下手！！！
值得注意的是该题任何细胞所发生的变化都是同时的（即我们不能一边遍历一边改变细胞状态，不然会影响后面细胞）
该题有两种思路
1.建立新数组
class Solution { public: int nextt[8][2]={
{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}}; int tx,ty,n,m; void
check(int x,int y,vector<vector<int>>& other_board,vector<vector<int>>& board)
{ int count=0; for(int i=0;i<8;i++) { tx=x+nextt[i][0]; ty=y+nextt[i][1];
if(tx<0||ty<0||tx>=n||ty>=m)// 小心越界 { continue; } if(board[tx][ty]==1) {
count++; } } if(count<2&&count>=0)//周围少于2个活细胞 { other_board[x][y]=0; } else
if(count<=3&&board[x][y]==1)//周围有2~3个活细胞且原细胞活着 { other_board[x][y]=1; } else
if(count==3&&board[x][y]==0)//周围有3个活细胞且原细胞死亡 { other_board[x][y]=1; } else
if(count>3)//周围有>3个活细胞 { other_board[x][y]=0; } } void
gameOfLife(vector<vector<int>>& board) { n=board.size(); m=board[0].size();
vector<vector<int> > other_board(n,vector<int>(m)); for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) { other_board[i][j]=board[i][j];// copy原数组 } } for(int
i=0;i<n;i++) { for(int j=0;j<m;j++) { check(i,j,other_board,board);//
每个元素都检查周围8个元素 } } for(int i=0;i<n;i++) { for(int j=0;j<m;j++) {
board[i][j]=other_board[i][j];// 粘贴到原数组 } } } };
2.建立新规则
class Solution { public: int nextt[8][2] = {
{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1} }; int tx, ty, n, m; void
check(int x, int y, vector<vector<int>>& board) { int count = 0; for (int i =
0; i < 8; i++) { tx = x + nextt[i][0]; ty = y + nextt[i][1]; if (tx < 0 || ty <
0 || tx >= n || ty >= m) { continue; } if (board[tx][ty] ==
1||board[tx][ty]==-1)//注意这里比原来多一个条件 { //如果原来是活细胞也要加上 count++; } } if
((board[x][y] == 1) && (count < 2 || count > 3)) { // -1 代表这个细胞过去是活的现在死了
board[x][y] = -1; } if (board[x][y] == 0 && count == 3) { // 2 代表这个细胞过去是死的现在活了
board[x][y] = 2; } } void gameOfLife(vector<vector<int>>& board) { n =
board.size(); m = board[0].size(); for (int i = 0; i < n; i++) { for (int j =
0; j < m; j++) { check(i, j, board); } } for (int i = 0; i < n;
i++)//最后记得将所有细胞的状态更新 { for (int j = 0; j < m; j++) { if (board[i][j] > 0) {
board[i][j] = 1; } else { board[i][j] = 0; } } } } };
两种方法的时间复杂度都是O(nm)
但是第二种方法的空间复杂度会更小