位操作解决数组的花样遍历

文章目录

---

题目

leetcodeT289 https://leetcode.cn/problems/game-of-life/description/

---

一、思路：

这题思路很简单，对每个位置按照题目所给规则进行遍历，判断周围网格的活细胞数即可。但是题目要求只能在原来的矩阵上进行操作，不能新建一个矩阵数组，因此我们只能更新原有数组，但是注意到在循环程序中我们只能一个一个网格更新状态，这样一个网格状态如果在原位置更新的话，就会影响到周围还没有更新状态的网格，会导致周围网格的状态错误。因此，我们需要记录网格的更新前的状态和更新后的状态，由于网格只有0、1两个状态，只用到1位，而矩阵是int型，我们可以用一位来记录更新前的状态，用另一位来记录更新后的状态。

二、代码

class Solution {public void gameOfLife(int[][] board) {int n = board.length;int m = board[0].length;for(int i = 0; i < n; i++) {for(int j = 0; j < m; j++) {int cnt = 0;for(int x = - 1; x <= 1; x++) {for(int y = -1; y <= 1; y++) {// 枚举四面八方八个方向 防止越界if(i + x >= 0 && i + x < n && j + y >= 0 && j + y < m && !(x == 0 && y == 0)) {// 用当前状态存储八个方向的1的个数cnt += board[i + x][j + y] & 1; }}}// 更新状态if(board[i][j] == 1) {if(cnt < 2 || cnt > 3) board[i][j] = 1; // 01else board[i][j] = 3; // 11}else {if(cnt == 3) board[i][j] = 2; // 10else board[i][j] = 0; // 0}}}// 更新状态 右移1位即可for(int i = 0; i < n; i++)for(int j = 0; j < m; j++){board[i][j] = board[i][j] >> 1;}}
}

---

总结

通过二进制位运算的思想可以存储两个状态，用来避免更新对下面操作的影响。