LeetCode 生命游戏,不用新数组的方式

Stella981
• 阅读 678

原文链接: LeetCode 生命游戏,不用新数组的方式

https://leetcode-cn.com/problems/game-of-life/

主要思想是将下一次的状态存储在高位, 因为只需要一个位就能表示生死两种状态

/**
如果活细胞周围八个位置的活细胞数少于两个,则该位置活细胞死亡;
如果活细胞周围八个位置有两个或三个活细胞,则该位置活细胞仍然存活;
如果活细胞周围八个位置有超过三个活细胞,则该位置活细胞死亡;
如果死细胞周围正好有三个活细胞,则该位置死细胞复活;
 * @param {number[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var gameOfLife = function (board) {
  const path = [
    [-1, -1],
    [-1, 0],
    [-1, 1],
    [1, -1],
    [1, 0],
    [1, 1],
    [0, -1],
    [0, 1],
  ];
  const pathLength = path.length;
  const h = board.length;
  if (!h) return;
  const w = board[0].length;
  let i, j, k, n, v, nx, ny, dx, dy;
  for (let i = 0; i < h; i++) {
    for (let j = 0; j < w; j++) {
      n = 0;
      v = board[i][j] & 1;
      for (k = 0; k < pathLength; k++) {
        dx = path[k][0];
        dy = path[k][1];
        nx = dx + i;
        ny = dy + j;
        if (nx < 0 || ny < 0 || nx >= h || ny >= w) {
          continue;
        }
        if (board[nx][ny] & 1) n++;
      }
      if (v & 1) {
        // 活细胞
        if (n < 2 || n > 3) {
          // 死亡
          // board[i][j] = v | 2;
        } else if (n <= 3) {
          // 存活
          board[i][j] = v | 2;
        }
      } else if ((v & 1) === 0 && n === 3) {
        // 死细胞
        board[i][j] = v | 2;
      }
      //   console.log("n", { v, i, j, n });
    }
  }
  for (i = 0; i < h; i++) {
    for (j = 0; j < w; j++) {
      board[i][j] = board[i][j] >> 1;
    }
  }
  //   return board;
};

// 输入:board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
// 输出:[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

// 输入:board = [[1,1],[1,0]]
// 输出:[[1,1],[1,1]]

// console.log(
//   gameOfLife([
//     [0, 1, 0],
//     [0, 0, 1],
//     [1, 1, 1],
//     [0, 0, 0],
//   ])
// );
// console.log(
//   gameOfLife([
//     [1, 1],
//     [1, 0],
//   ])
// );
点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Wesley13 Wesley13
3年前
java将前端的json数组字符串转换为列表
记录下在前端通过ajax提交了一个json数组的字符串,在后端如何转换为列表。前端数据转化与请求varcontracts{id:'1',name:'yanggb合同1'},{id:'2',name:'yanggb合同2'},{id:'3',name:'yang
待兔 待兔
4个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Stella981 Stella981
3年前
LeetCode 1009. 十进制整数的反码
原文链接: LeetCode1009.十进制整数的反码(https://my.oschina.net/ahaoboy/blog/3118044)https://leetcodecn.com/problems/complementofbase10integer/(https://www.oschina.net/action/GoToL
Stella981 Stella981
3年前
LeetCode 169. 求众数
原文链接: LeetCode169.求众数(https://my.oschina.net/ahaoboy/blog/3118038)https://leetcodecn.com/problems/majorityelement/(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F
Stella981 Stella981
3年前
LeetCode 72. 编辑距离
原文链接: LeetCode72.编辑距离(https://my.oschina.net/ahaoboy/blog/3113850)https://leetcodecn.com/problems/editdistance/(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2F
Stella981 Stella981
3年前
Android So动态加载 优雅实现与原理分析
背景:漫品Android客户端集成适配转换功能(基于目标识别(So库35M)和人脸识别库(5M)),导致apk体积50M左右,为优化客户端体验,决定实现So文件动态加载.!(https://oscimg.oschina.net/oscnet/00d1ff90e4b34869664fef59e3ec3fdd20b.png)点击上方“蓝字”关注我
Stella981 Stella981
3年前
LeetCode 338. 比特位计数
原文链接: LeetCode338.比特位计数(https://my.oschina.net/ahaoboy/blog/3117631)https://leetcodecn.com/problems/countingbits/(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%
Wesley13 Wesley13
3年前
2D小游戏开发学习笔记(5)
一、围住神经猫游戏游戏玩法:玩法很简单,蓝色圆圈代表神经猫,通过点击周围圆圈把猫困住,就算游戏成功游戏效果!(https://oscimg.oschina.net/oscnet/up968a35abafe07c092eacca8126719e14a50.png)逻辑梳理:1、
达里尔 达里尔
11个月前
给数组添加新数据,判断数据是否重复
多选要进行数组拼接,希望判断往原数组里添的新数据是否重复,封装个简易方法languageconstdataArrayname:'aaa',id:1,name:'bbb',id:2;constnewDataname:'ccc',id:2;//要添加的新数