矩阵基础

• 使用哈希数组来标记当前行或者列是否出现0
• 按层模拟
• 旋转90度可以先水平翻，然后再对角线翻

73. 矩阵置零

题目讲解：LeetCode
重点：

1. 使用标记数组：用两个标记数组分别记录每一行和每一列是否有零出现。
2. 使用两个标记变量：用矩阵的第一行和第一列代替两个标记数组。再额外使用两个标记变量分别记录第一行和第一列是否原本包含 0。

思路：

• 使用标记数组
  1.首先遍历该数组一次，如果某个元素为 0，那么就将该元素所在的行和列所对应标记数组的位置置为 true。
  2.最后我们再次遍历该数组，用标记数组更新原数组即可。
• 使用两个标记变量
  1.首先预处理出两个标记变量，接着使用其他行与列去处理第一行与第一列。
  2.然后反过来使用第一行与第一列去更新其他行与列，最后使用两个标记变量更新第一行与第一列即可。

复杂度：

• m 是矩阵的行数，n 是矩阵的列数
• 使用标记数组
  时间复杂度：O(mn)
  空间复杂度：O(m+n)
• 使用两个标记变量
  时间复杂度：O(mn)
  空间复杂度：O(1)

// 使用标记数组
public void setZeroes(int[][] matrix) {// 重点: 用两个标记数组分别记录每一行和每一列是否有零出现boolean[] row = new boolean[matrix.length];boolean[] col = new boolean[matrix[0].length];for (int i = 0; i < matrix.length; i++) {for (int j = 0; j < matrix[0].length; j++) {if (matrix[i][j] == 0) {row[i] = true;col[j] = true;}}}for (int i = 0; i < matrix.length; i++) {for (int j = 0; j < matrix[0].length; j++) {if (row[i] || col[j]) matrix[i][j] = 0;}}
}

// 使用两个标记变量
public void setZeroes(int[][] matrix) {boolean row0Flag = false;boolean col0Flag = false;for (int j = 0; j < matrix[0].length; j++) {if (matrix[0][j] == 0) {row0Flag = true;break;}}for (int i = 0; i < matrix.length; i++) {if (matrix[i][0] == 0) {col0Flag = true;break;}}// 重点: 使用第一行和第一列标记for (int i = 1; i < matrix.length; i++) {for (int j = 1; j < matrix[0].length; j++) {if (matrix[i][j] == 0) {matrix[0][j] = 0;matrix[i][0] = 0;}}}for (int i = 1; i < matrix.length; i++) {for (int j = 1; j < matrix[0].length; j++) {if (matrix[0][j] == 0 || matrix[i][0] == 0) {matrix[i][j] = 0;}}}// 重点: 再用两个标记变量处理第一行和第一列if (row0Flag) {Arrays.fill(matrix[0], 0);}if (col0Flag) {for (int i = 0; i < matrix.length; i++) matrix[i][0] = 0;}
}

54. 螺旋矩阵

题目讲解：LeetCode
重点：

1. 按层模拟。四个标记。

思路：

• 按层模拟
  1.每一层遍历 顶 右 底 左。每遍历完一个对应的边界需要处理。

复杂度：

• m 和 n 分别是行数和列数
• 时间复杂度：O(mn)。每个元素都要被访问一次。
• 空间复杂度：O(1)。除了输出数组以外，空间复杂度是常数。

public List<Integer> spiralOrder(int[][] matrix) {List<Integer> result = new ArrayList<>();int curTop = 0;int curRight = matrix[0].length - 1;int curBottom = matrix.length - 1;int curLeft = 0;// 重点: 按层模拟, 每一层遍历 顶 右 底 左while (curLeft <= curRight && curTop <= curBottom) {// 当前层的最顶行for (int i = curLeft; i <= curRight; i++) {result.add(matrix[curTop][i]);}curTop++;// 当前层的最右列for (int i = curTop; i <= curBottom; i++) {result.add(matrix[i][curRight]);}curRight--;// 当前外层的最底行还存在if (curTop <= curBottom) {for (int i = curRight; i >= curLeft; i--) {result.add(matrix[curBottom][i]);}}curBottom--;// 当前外层的最左列还存在if (curLeft <= curRight) {for (int i = curBottom; i >= curTop; i--) {result.add(matrix[i][curLeft]);}}curLeft++;}return result;
}

48. 旋转图像

题目讲解：LeetCode
重点：

1. 原地旋转代码背下来。
2. 用翻转代替旋转。水平翻，然后对角线翻。

思路：

• 原地旋转

1. 逆时间的顺序来替换。背下来。

• 用翻转代替旋转

1. 先水平翻转
2. 再对角线翻转

复杂度：

• N 是 matrix 的边长
• 原地旋转
  时间复杂度：O(N^2)
  空间复杂度：O(1)
• 用翻转代替旋转
  时间复杂度：O(N^2)
  空间复杂度：O(1)

// 原地旋转
public void rotate(int[][] matrix) {int n = matrix.length;// 替换一半另一半就相当于自动替换过去了for (int i = 0; i < n / 2; i++) {// 内层要加一是因为n为奇数时需要多遍历一遍for (int j = 0; j < (n + 1) / 2; j++) {int temp = matrix[i][j];// 逆时针替换// 左上matrix[i][j] = matrix[n - j - 1][i];// 左下matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];// 右下matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];// 右上matrix[j][n - i - 1] = temp;}}
}

// 用翻转代替旋转
public void rotate(int[][] matrix) {int n = matrix.length;// 重点: 先水平翻转for (int i = 0; i < matrix.length / 2; i++) {for (int j = 0; j < matrix[0].length; j++) {int temp = matrix[i][j];matrix[i][j] = matrix[n - i - 1][j];matrix[n - i - 1][j] = temp;}}// 重点: 再对角线翻转, 循环条件看作楼梯, 外层循环i=0则为对角线左侧楼梯顶层for (int i = 0; i < matrix.length; i++) {for (int j = 0; j < i; j++) {int temp = matrix[i][j];matrix[i][j] = matrix[j][i];matrix[j][i] = temp;}}
}

题目讲解：LeetCode
重点：
1.

思路：
1.

复杂度：

• 时间复杂度：
• 空间复杂度：