网站开发php制作,如何在工商局网站做企业年报,贸易公司怎么做网站比较好,网页模版289. 生命游戏
题目#xff1a; 给定一个包含 m n 个格子的面板#xff0c;每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态#xff1a; 1 即为 活细胞 #xff08;live#xff09;#xff0c;或 0 即为 死细胞 #xff08;dead#xff09;。每个细胞与… 289. 生命游戏
题目 给定一个包含 m × n 个格子的面板每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态 1 即为 活细胞 live或 0 即为 死细胞 dead。每个细胞与其八个相邻位置水平垂直对角线的细胞都遵循以下四条生存定律 如果活细胞周围八个位置的活细胞数少于两个则该位置活细胞死亡如果活细胞周围八个位置有两个或三个活细胞则该位置活细胞仍然存活如果活细胞周围八个位置有超过三个活细胞则该位置活细胞死亡如果死细胞周围正好有三个活细胞则该位置死细胞复活 下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态返回下一个状态。 思考
方法一暴力破解
这个问题看起来很简单但有一个陷阱如果你直接根据规则更新原始数组那么就做不到题目中说的 同步 更新。假设你直接将更新后的细胞状态填入原始数组那么当前轮次其他细胞状态的更新就会引用到当前轮已更新细胞的状态但实际上每一轮更新需要依赖上一轮细胞的状态是不能用这一轮的细胞状态来更新的。
所以我们需要创建一个同样大小的数组用来存储变化后的值。
创建数组代码如下
vectorvectorint nextBoard(m, vectorint(n, 0)); // 创建一个新的矩阵来存储下一步的状态
接下来我们需要计算周围8个格加起来的活细胞数量。但这里要注意边界情况。
8个格子普通版边界需要处理if语句写起来又臭又长。
ans matirex[i-1][j]matirex[i1][j]matirex[i][j-1]matirex[i][j1]matirex[i-1][j-1]matirex[i1][j1]matirex[i1][j-1]matirex[i-1][j1]; 所以不妨设置移动变量 dx,dy.先将xy进行变化然后判断越界情况。 for (int dx -1; dx 1; dx) {for (int dy -1; dy 1; dy) {if (dx 0 dy 0) continue; // 跳过当前位置int x i dx;int y j dy;if (x 0 x m y 0 y n) {//在区域内count matrix[x][y];}}}再根据生存规律判断细胞实际存活情况 。
最后将结果复制回数组中。
class Solution {
public:int num(vectorvectorint matrix, int i, int j) {int count 0;int m matrix.size();int n matrix[0].size();for (int dx -1; dx 1; dx) {for (int dy -1; dy 1; dy) {if (dx 0 dy 0) continue; // 跳过当前位置int x i dx;int y j dy;if (x 0 x m y 0 y n) {count matrix[x][y];}}}return count;}void gameOfLife(vectorvectorint board) {int m board.size();int n board[0].size();vectorvectorint nextBoard(m, vectorint(n, 0)); for (int i 0; i m; i) {for (int j 0; j n; j) {int liveNeighbors num(board, i, j);// 根据规则更新下一步的状态if (board[i][j] 1 (liveNeighbors 2 || liveNeighbors 3)) {nextBoard[i][j] 1; // 存活状态} else if (board[i][j] 0 liveNeighbors 3) {nextBoard[i][j] 1; // 重生} else {nextBoard[i][j] 0; // 死亡}}}// 将下一步状态复制回原矩阵for (int i 0; i m; i) {for (int j 0; j n; j) {board[i][j] nextBoard[i][j];}}}
};复杂度时间复杂度0(mn),空间复杂度0(mn)。
方法二使用额外的状态
方法一中O(mn) 的空间复杂度在数组很大的时候内存消耗是非常昂贵的。题目中每个细胞只有两种状态 live(1) 或 dead(0)但我们可以拓展一些复合状态使其包含之前的状态。举个例子如果细胞之前的状态是 0但是在更新之后变成了 1我们就可以给它定义一个复合状态 2。这样我们看到 2既能知道目前这个细胞是活的还能知道它之前是死的。
根据生存规律判断细胞实际存活情况规则修正如下 规则 1如果活细胞周围八个位置的活细胞数少于两个则该位置活细胞死亡。这时候将细胞值改为 -1代表这个细胞过去是活的现在死了 规则 2如果活细胞周围八个位置有两个或三个活细胞则该位置活细胞仍然存活。这时候不改变细胞的值仍为 1 规则 3如果活细胞周围八个位置有超过三个活细胞则该位置活细胞死亡。这时候将细胞的值改为 -1代表这个细胞过去是活的现在死了。可以看到因为规则 1 和规则 3 下细胞的起始终止状态是一致的因此它们的复合状态也一致 规则 4如果死细胞周围正好有三个活细胞则该位置死细胞复活。这时候将细胞的值改为 2代表这个细胞过去是死的现在活了。 另外计数方式也需要改一下只有当abs(board[x][y]) 1时原先才是活的进行计数 // 根据规则更新下一步的状态if (board[i][j] 1 (liveNeighbors 2 || liveNeighbors 3)) {board[i][j] -1; // 存活状态} else if (board[i][j] 0 liveNeighbors 3) {board[i][j] 2; // 重生} //其他位置保持不变即可//计数方式if (x 0 x m y 0 y n(abs(board[x][y]) 1)) {count 1;}
最后再讲2更改为 13更改为0 即可。
代码如下
class Solution {
public:int num(vectorvectorint matrix, int i, int j) {int count 0;int m matrix.size();int n matrix[0].size();for (int dx -1; dx 1; dx) {for (int dy -1; dy 1; dy) {if (dx 0 dy 0) continue; // 跳过当前位置int x i dx;int y j dy;if (x 0 x m y 0 y n(abs(matrix[x][y]) 1)) {count 1;}}}return count;}void gameOfLife(vectorvectorint board) {int m board.size();int n board[0].size();//vectorvectorint nextBoard(m, vectorint(n, 0)); // 创建一个新的矩阵来存储下一步的状态for (int i 0; i m; i) {for (int j 0; j n; j) {int liveNeighbors num(board, i, j);// 根据规则更新下一步的状态if (board[i][j] 1 (liveNeighbors 2 || liveNeighbors 3)) {board[i][j] -1; // 存活状态} else if (board[i][j] 0 liveNeighbors 3) {board[i][j] 2; // 重生} //其他位置保持不变即可}}// 将下一步状态复制回原矩阵for (int i 0; i m; i) {for (int j 0; j n; j) {if(board[i][j]0) board[i][j] 1;else board[i][j] 0;}}}
};48. 旋转图像
题目 给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。 你必须在 原地 旋转图像这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。 思路要求原地修改数组说明空间复杂度需要为0(1)考虑使用swap调换数组位置。
常用调换位置方法 1.中心反转 swap(matrix[i][j],matrix[j][i]); swap(matrix[i][j],matrix[n-j-1][n-i-]); 2.水平翻转 swap(matrix[i][j],matrix[n-i-1][j]); 3.数列翻转 swap(matrix[i][j],matrix[i][n-j-1]); 翻转问题一定注意下标的范围反转只需要换一半 例如水平和数列 n/2,中心就是ji 本题研究一下发现只需要中心翻转数列翻转一下即可
matrix [[1,2,3],[4,5,6],[7,8,9]]
中心翻转后[[1,4,7],[2,5,8],[3,6,9]] swap(matrix[i][j],matrix[j][i]);
数列翻转[[7,4,1],[8,5,2],[9,6,3]] 代码
class Solution {
public:void rotate(vectorvectorint matrix) {int nmatrix.size();for(int i0;in;i){for(int j0;ji;j){swap(matrix[i][j],matrix[j][i]);}}for(int i0;in;i){for(int j0;jn/2;j){swap(matrix[i][j],matrix[i][n-j-1]);}}}
};
73. 矩阵置零
题目
给定一个 m x n 的矩阵如果一个元素为 0 则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
方法一开一个二维数组
1.一个直观的解决方案是使用 O(mn) 的额外空间但这并不是一个好的解决方案。
class Solution {
public:void setZeroes(vectorvectorint matrix) {int m matrix.size();int n matrix[0].size();vectorvectorint res(m, vectorint(n, 1));for (int i 0; i m; i) {for (int j 0; j n; j) {if (matrix[i][j] 0) {for (int k 0; k n; k)res[i][k] 0;for (int k 0; k m; k)res[k][j] 0;}}}for (int i 0; i m; i) {for (int j 0; j n; j) {matrix[i][j] matrix[i][j] * res[i][j];}}}
};
方法二创建两个额外的数组来记录哪些行和列需要被置零
一个简单的改进方案是使用 O(m n) 的额外空间但这仍然不是最好的解决方案
class Solution {
public:void setZeroes(vectorvectorint matrix) {int m matrix.size();int n matrix[0].size();vectorint res_row(m, 1);vectorint res_col(n, 1);for (int i 0; i m; i) {for (int j 0; j n; j) {if (matrix[i][j] 0) {res_row[i]0;res_col[j]0;}}}for (int i 0; i m; i) {for (int j 0; j n; j) {matrix[i][j] matrix[i][j] * res_row[i]*res_col[j];}}}
};
方法三使用两个标记变量
我们可以用矩阵的第一行和第一列代替方法一中的两个标记数组以达到 O(1) 的额外空间。但这样会导致原数组的第一行和第一列被修改无法记录它们是否原本包含 0。因此我们需要额外使用两个标记变量分别记录第一行和第一列是否原本包含 0。
在实际代码中我们首先预处理出两个标记变量接着使用其他行与列去处理第一行与第一列然后反过来使用第一行与第一列去更新其他行与列最后使用两个标记变量更新第一行与第一列即可。
class Solution {
public:void setZeroes(vectorvectorint matrix) {int m matrix.size();int n matrix[0].size();int flag_col0 false, flag_row0 false;for (int i 0; i m; i) {if (!matrix[i][0]) {flag_col0 true;}}for (int j 0; j n; j) {if (!matrix[0][j]) {flag_row0 true;}}for (int i 1; i m; i) {for (int j 1; j n; j) {if (!matrix[i][j]) {matrix[i][0] matrix[0][j] 0;}}}for (int i 1; i m; i) {for (int j 1; j n; j) {if (!matrix[i][0] || !matrix[0][j]) {matrix[i][j] 0;}}}if (flag_col0) {for (int i 0; i m; i) {matrix[i][0] 0;}}if (flag_row0) {for (int j 0; j n; j) {matrix[0][j] 0;}}}
};
