春招冲刺百题计划--矩阵篇

289. 生命游戏

题目：

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为 活细胞 （live），或 0 即为 死细胞 （dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

1. 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
2. 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
3. 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
4. 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；

下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。

思考：

方法一：暴力破解

这个问题看起来很简单，但有一个陷阱，如果你直接根据规则更新原始数组，那么就做不到题目中说的 同步 更新。假设你直接将更新后的细胞状态填入原始数组，那么当前轮次其他细胞状态的更新就会引用到当前轮已更新细胞的状态，但实际上每一轮更新需要依赖上一轮细胞的状态，是不能用这一轮的细胞状态来更新的。

所以我们需要创建一个同样大小的数组，用来存储变化后的值。

创建数组代码如下：

vector<vector<int>> nextBoard(m, vector<int>(n, 0)); // 创建一个新的矩阵来存储下一步的状态

接下来，我们需要计算周围8个格加起来的活细胞数量。但这里要注意边界情况。

8个格子（普通版），边界需要处理，if语句，写起来又臭又长。

ans+= matirex[i-1][j]+matirex[i+1][j]+matirex[i][j-1]+matirex[i][j+1]+matirex[i-1][j-1]+matirex[i+1][j+1]+matirex[i+1][j-1]+matirex[i-1][j+1];

  所以不妨设置移动变量 dx,dy.先将x，y进行变化，然后判断越界情况。

    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(vector<vector<int>>& 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(vector<vector<int>>& board) {int m = board.size();int n = board[0].size();vector<vector<int>> nextBoard(m, vector<int>(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更改为 1；3更改为0 即可。 

代码如下：

class Solution {
public:int num(vector<vector<int>>& 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(vector<vector<int>>& board) {int m = board.size();int n = board[0].size();//vector<vector<int>> nextBoard(m, vector<int>(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,中心就是j<i

本题研究一下发现只需要中心翻转＋数列翻转一下即可

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(vector<vector<int>>& matrix) {int n=matrix.size();for(int i=0;i<n;i++){for(int j=0;j<i;j++){swap(matrix[i][j],matrix[j][i]);}}for(int i=0;i<n;i++){for(int j=0;j<n/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(vector<vector<int>>& matrix) {int m = matrix.size();int n = matrix[0].size();vector<vector<int>> res(m, vector<int>(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(vector<vector<int>>& matrix) {int m = matrix.size();int n = matrix[0].size();vector<int> res_row(m, 1);vector<int> 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(vector<vector<int>>& 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;}}}
};

---