dedecms两网站共享用户名,网络营销型网站策划,wordpress 布局调整,自动注册wordpress账号软件目录 题目解法代码说明#xff1a; 每一个各自去搜寻他周围的信息#xff0c;肯定存在冗余#xff0c;如何优化这个过程#xff1f;如何遍历每一个元素的邻域#xff1f;方向数组如何表示方向#xff1f; auto dir : directions这是什么用法board[i][j]一共有几种状态 每一个各自去搜寻他周围的信息肯定存在冗余如何优化这个过程如何遍历每一个元素的邻域方向数组如何表示方向 auto dir : directions这是什么用法board[i][j]一共有几种状态为什么要设置这么多种不是0和1代表生存和死亡就行 题目
根据 百度百科 生命游戏 简称为 生命 是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。
给定一个包含 m × n 个格子的面板每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态 1 即为 活细胞 live或 0 即为 死细胞 dead。每个细胞与其八个相邻位置水平垂直对角线的细胞都遵循以下四条生存定律
如果活细胞周围八个位置的活细胞数少于两个则该位置活细胞死亡 如果活细胞周围八个位置有两个或三个活细胞则该位置活细胞仍然存活 如果活细胞周围八个位置有超过三个活细胞则该位置活细胞死亡 如果死细胞周围正好有三个活细胞则该位置死细胞复活 下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态返回下一个状态。 示例 1 输入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]] 示例 2
输入board [[1,1],[1,0]] 输出[[1,1],[1,1]]
解法
下面是使用C实现“生命游戏”的代码它根据给定的网格状态计算下一个状态
#include vector
using namespace std;class Solution {
public:void gameOfLife(vectorvectorint board) {int m board.size();int n board[0].size();// 创建一个方向数组来表示相邻的八个方向vectorvectorint directions {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};// 遍历每个细胞计算其下一个状态for (int i 0; i m; i) {for (int j 0; j n; j) {int liveNeighbors 0;// 统计当前细胞周围的活细胞数for (auto dir : directions) {int ni i dir[0];int nj j dir[1];if (ni 0 ni m nj 0 nj n abs(board[ni][nj]) 1) {liveNeighbors;}}// 根据规则判断细胞的下一个状态if (board[i][j] 1 (liveNeighbors 2 || liveNeighbors 3)) {// 如果活细胞的邻居少于2个或多于3个变成死细胞board[i][j] -1; // -1表示活细胞变成死细胞}if (board[i][j] 0 liveNeighbors 3) {// 如果死细胞有正好3个邻居活细胞复活board[i][j] 2; // 2表示死细胞变成活细胞}}}// 更新细胞的状态for (int i 0; i m; i) {for (int j 0; j n; j) {if (board[i][j] -1) {board[i][j] 0; // -1变为0死} else if (board[i][j] 2) {board[i][j] 1; // 2变为1活}}}}
};代码说明
方向数组 directions: 用来表示每个细胞相邻的八个位置。邻居活细胞统计: 遍历每个细胞的八个相邻位置统计活细胞的个数。规则判断: 如果是活细胞且邻居活细胞少于2个或多于3个则标记为死亡暂时用-1表示。如果是死细胞且正好有3个活细胞则标记为复活暂时用2表示。 状态更新: 将标记的状态-1和2更新回最终的状态0或1。
这个实现可以处理 m x n 大小的任意网格时间复杂度为 O(m * n)适用于一般规模的输入。
每一个各自去搜寻他周围的信息肯定存在冗余如何优化这个过程
这是进一步的探索目前实现方法就是遍历每一个。而如何遍历一个元素邻域也是个问题
如何遍历每一个元素的邻域 // 创建一个方向数组来表示相邻的八个方向vectorvectorint directions {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};使用一个方向数组
方向数组如何表示方向
在生命游戏的实现中方向数组用来表示一个细胞的周围八个邻居的位置。方向数组中的 0 和 1 是通过表示相对的行和列偏移来确定方向的。
方向数组中的 0 和 1 解释
假设当前的细胞在网格中的位置是 (i, j)我们可以通过对行 i 和列 j 进行加减操作来确定相邻的八个位置
{0, 1} 表示行不变0列加11即向右移动。{1, 0} 表示行加11列不变0即向下移动。{0, -1} 表示行不变0列减1-1即向左移动。{-1, 0} 表示行减1-1列不变0即向上移动。
这些偏移可以扩展到斜方向
{1, 1} 表示行加11列加11即向右下角移动。{1, -1} 表示行加11列减1-1即向左下角移动。{-1, 1} 表示行减1-1列加11即向右上角移动。{-1, -1} 表示行减1-1列减1-1即向左上角移动。
在遍历每个细胞时我们可以根据这些方向数组中的偏移量来检查该细胞周围的邻居。例如若当前细胞在位置 (i, j)我们可以这样遍历其邻居
int ni i dir[0];
int nj j dir[1];使用行或列的平移操作
auto dir : directions这是什么用法
在 C 中auto 是一种用于自动类型推导的关键字。它可以让编译器根据变量的初始值自动推导出该变量的类型而不需要显式地声明类型。
在你的例子里for (auto dir : directions) 使用了范围-based for 循环auto 让编译器自动推导出 dir 的类型。directions 是一个二维的 vectorvectorint其中每个元素是一个 vectorint表示一个方向。因此auto dir 实际上被推导为 vectorint 类型。
详细说明
for (auto dir : directions)这个代码的意思是依次遍历 directions 中的每一个元素auto 让编译器自动推导出 dir 的类型。由于 directions 是 vectorvectorint所以每一个 dir 实际上是一个 vectorint表示某一个方向比如 {0, 1}表示向右。
使用 auto 的优点 减少代码冗长不需要手动写出每个变量的确切类型编译器可以自动推导。 如果不用 auto代码可能需要写成for (vectorint dir : directions)使用 auto 则更简洁for (auto dir : directions)防止类型错误在某些情况下复杂类型的声明可能容易出错使用 auto 可以让编译器直接根据上下文推导出正确的类型。
总结 auto 是 C11 引入的一种方便的特性它让编译器根据上下文推导出变量的类型减少了手动声明类型的繁琐同时可以提高代码的可读性和可维护性。在你的代码中auto 推导出的类型是 vectorint。
board[i][j]一共有几种状态为什么要设置这么多种不是0和1代表生存和死亡就行
多种状态的设置就不需要再创建一个辅助矩阵来存储每个细胞的下一时刻过程。 且对于一个细胞当前为1正存活使用-1来表示它的未来状态但是通过绝对值仍然可以获取当前状态这是很精妙的地方 四种状态的含义 在这种实现中board[i][j] 可以有四种状态
0当前是死细胞下一状态也保持为死细胞。 1当前是活细胞下一状态也保持为活细胞。 -1当前是活细胞但下一状态变为死细胞。 2当前是死细胞但下一状态变为活细胞。
abs(board[ni][nj]) 1这个绝对值用的太妙了直接减少了空间复杂度
