73. 矩阵置零 Java
方法一：使用额外布尔数组，空间复杂度：O(m+n)
用一个长为 m 的布尔数组 row0记录每一行是否包含 0。
遍历 matrix[i]，如果包含 0，那么置 row0[i]=true。
用一个长为 n 的布尔数组 col0 记录每一列是否包含 0。
遍历 matrix 的 j 列，如果包含 0，那么置 col0[j]=true。
然后，再次遍历 matrix。对于 matrix[i][j]，如果 row0[i]=true 或者 col0[j]=true，说明 i 行有 0，或者 j 列有 0，把 matrix[i][j] 变成 0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
boolean[] row0 = new boolean[m];
boolean[] col0 = new boolean[n];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (matrix[i][j] == 0) row0[i] = col0[j] = true;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (row0[i] || col0[j]) matrix[i][j] = 0;
}
}
|
方法二：不使用额外数组
把 matrix[i][j] 置 0 的循环，可以倒着遍历 i 行，这样可以直接修改第一列。
对比一下，如果正着遍历 i 行，如果提前把 matrix[i][0] 改成 0，会误认为这一行要全部变成 0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
boolean row1has0 = false;
for (int j = 0; j < n; j++)
if (matrix[0][j] == 0) {
row1has0 = true;
break;
}
for (int i = 1; i < m; i++)
for (int j = 0; j < n; j++)
if (matrix[i][j] == 0) matrix[i][0] = matrix[0][j] = 0;
for (int i = 1; i < m; i++)
for (int j = n - 1; j >= 0; j--)
if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
if (row1has0) Arrays.fill(matrix[0],0);
}
}
|
54. 螺旋矩阵 Java
二维数组DIRS存储右下左上四个方向变化坐标变化量，走过的用Integer.MAX_VALUE标记，当下一步要出界或遇到走过的，就按优先级递减变换方向。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public List<Integer> spiralOrder(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
List<Integer> ans = new ArrayList<>(m * n);
int i = 0, j = 0, di = 0;
for (int k = 0; k < m * n; k++) {
ans.add(matrix[i][j]);
matrix[i][j] = Integer.MAX_VALUE;
int x = i + DIRS[di][0];
int y = j + DIRS[di][1];
if (x < 0 || x > m || y < 0 || y > n || matrix[x][y] == Integer.MAX_VALUE){
di = (di + 1) % 4;
}
i += DIRS[di][0];
j += DIRS[di][1];
}
return ans;
}
}
|
48. 旋转图像 Java
一般地，把一个点绕 O 旋转任意θ角度，可以通过两个翻转操作实现。要求这两条翻转的对称轴，交点为 O 且夹角为 θ/2。
对于本题，每个元素需要绕矩阵中心顺时针旋转 90°，这可以通过关于主对角线翻转，关于垂直中轴翻转实现。这两条对称轴的交点为矩阵中心，且夹角为 45°。
顺转90° ：转置 + 行左右转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n; i++){
for (int j = 0; j < i; j++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = tmp;
}
}
for (int[] row : matrix) {
for (int j = 0; j < n / 2; j++) {
int tmp = row[j];
row[j] = row[n - 1 - j];
row[n - 1 - j] =tmp;
}
}
}
}
|
逆转90° ：转置 + 列上下转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n; i++){
for (int j = 0; j < i; j++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = tmp;
}
}
for (int i = 0; i < n / 2; i++) {
int[] tmp = matrix[i];
matrix[i] = matrix[n - 1 - i];
matrix[n - 1 - i] =tmp;
}
}
}
|
180° ：行左右转 + 列上下转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int[] row : matrix) {
for (int j = 0; j < n / 2; j++) {
int tmp = row[j];
row[j] = row[n - 1 - j];
row[n - 1 - j] =tmp;
}
}
for (int i = 0; i < n / 2; i++) {
int[] tmp = matrix[i];
matrix[i] = matrix[n - 1 - i];
matrix[n - 1 - i] =tmp;
}
}
}
|
240. 搜索二维矩阵 II Java
使用二叉搜索树思想，从右上角开始，小了向下，大了向左。
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int i = 0;
int j = matrix[0].length - 1;
while (i < matrix.length && j >= 0) {
if (matrix[i][j] == target) return true;
if (matrix[i][j] < target) i++;
else j--;
}
return false;
}
}
|