LeetCode 热题 100 | 矩阵
矩阵基础
- 使用哈希数组来标记当前行或者列是否出现0
- 按层模拟
73. 矩阵置零
题目讲解：LeetCode
重点：
- 使用标记数组：用两个标记数组分别记录每一行和每一列是否有零出现。
- 使用两个标记变量：用矩阵的第一行和第一列代替两个标记数组。再额外使用两个标记变量分别记录第一行和第一列是否原本包含 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.每一层遍历 顶 右 底 左。每遍历完一个对应的边界需要处理。复杂度：
- 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.思路：
1.复杂度：
- 时间复杂度：
- 空间复杂度：
题目讲解：LeetCode
重点：
1.思路：
1.复杂度：
- 时间复杂度：
- 空间复杂度：