LeetCode 289. 生命游戏（位运算）
LeetCode 289. 生命游戏（位运算）
Michael阿明
发布于 2020-07-13 15:37:39
发布于 2020-07-13 15:37:39
1. 题目
链接：289. 生命游戏
2. 解题
2.1 复制数组解法
很简单，按照题意模拟即可
class Solution {
public:
void gameOfLife(vector<vector<int>>& board) {
if(board.empty())
return;
vector<vector<int>> cp(board);//复制数组法
int nearby[8][2] = {{-1, 0}, {-1, -1}, {0, -1}, {1, -1},
{1, 0}, {1, 1}, {0, 1}, {-1, 1}};
int m = board.size(), n = board[0].size(), i, j, k, x, y, live;
for(i = 0; i < m; ++i)
{
for(j = 0; j < n; ++j)
{
live = 0;
for(k = 0; k < 8; ++k)
{
x = i+nearby[k][0];
y = j+nearby[k][1];
if(x>=0 && x<m && y>=0 && y<n && cp[x][y])
live++;
}
if(cp[i][j])
{
if(live < 2 || live > 3)
board[i][j] = 0;
}
else
{
if(live == 3)
board[i][j] = 1;
}
}
}
}
};
2.2 原地解法
- 原来是1，标记成0，用2表示（等于1或者2，原状态都是1）
- 原来是0，标记成1，用3表示（等于0或者3，原状态都是0）
- 处理完后，改写数组
- 等于2的，赋值为0
- 等于3的，赋值为1
class Solution {
public:
void gameOfLife(vector<vector<int>>& board) {
if(board.empty())
return;
int nearby[8][2] = {{-1, 0}, {-1, -1}, {0, -1}, {1, -1},
{1, 0}, {1, 1}, {0, 1}, {-1, 1}};
int m = board.size(), n = board[0].size(), i, j, k, x, y, live;
for(i = 0; i < m; ++i)
{
for(j = 0; j < n; ++j)
{
live = 0;
for(k = 0; k < 8; ++k)
{
x = i+nearby[k][0];
y = j+nearby[k][1];
if(x>=0 && x<m && y>=0 && y<n && (board[x][y]==1 || board[x][y]==2))
live++;
}
if(board[i][j])
{
if(live < 2 || live > 3)
board[i][j] = 2;
}
else
{
if(live == 3)
board[i][j] = 3;
}
}
}
for(i = 0; i < m; ++i)
{
for(j = 0; j < n; ++j)
{
if(board[i][j] == 2)
board[i][j] = 0;
else if(board[i][j] == 3)
board[i][j] = 1;
}
}
}
};2.3 位运算
- 利用数值的低位作为原数据
- 高位保存周围存活的数量
class Solution {
public:
void gameOfLife(vector<vector<int>>& board) {
if (board.empty())
return;
int m = board.size(), n = board[0].size(), i, j, k, x, y, live;
int nearby[8][2] = {{-1, 0}, {-1, -1}, {0, -1}, {1, -1},
{1, 0}, {1, 1}, {0, 1}, {-1, 1}};
for (i = 0; i < m; ++i)
{
for (j = 0; j < n; ++j)
{
for (k = 0; k < 8; ++k)
{
x = i + nearby[k][0];
y = j + nearby[k][1];
if (x >= 0 && x < m && y >= 0 && y < n)
board[i][j] += (board[x][y] & 1) << 1;
}
}
}
for (i = 0; i < m; ++i)
{
for (j = 0; j < n; ++j)
{
live = board[i][j] >> 1;
if (live < 2 || live > 3)
board[i][j] = 0;
else if (live == 3)
board[i][j] = 1;
else
board[i][j] &= 1;
}
}
}
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019/10/28 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号