加速加速，来看矩阵，也全是Medium，快速过
54. Spiral Matrix[Medium]
思路：矩阵螺旋输出，就是纯模拟，比较有意思的是，这题居然之前还特地写了一篇博客
LeetCode-54-Spiral Matrix-CSDN博客
/*
Author Owen_Q
*/
public class SpiralMatrix {
public static List<Integer> spiralOrder(int[][] matrix) {
int[] orderX = new int[] {0, 1, 0, -1};
int[] orderY = new int[] {1, 0, -1, 0};
int x0 = 0;
int y0 = 0;
int x1 = matrix.length - 1;
int y1 = matrix[0].length - 1;
int direction = 0;
List<Integer> result = new ArrayList<>();
int x = 0;
int y = 0;
while (x0 <= x1 && y0 <= y1) {
result.add(matrix[x][y]);
if (direction == 0 && y == y1) {
x0++;
} else if (direction == 1 && x == x1) {
y1--;
} else if (direction == 2 && y == y0) {
x1--;
} else if (direction == 3 && x == x0) {
y0++;
} else {
direction--;
}
direction = (direction + 1) % 4;
x += orderX[direction];
y += orderY[direction];
}
return result;
}
}
48. Rotate Image[Medium]
思路：矩阵旋转问题，首先需要研究一下，每个点在四个区域的对应位置，这样就可以得到旋转后的点位。
| 左上角 | 右上角 | 左下角 | 右下角 |
|---|---|---|---|
由于这题明确规定不允许用额外矩阵进行复制，只能在原矩阵上进行操作，那么用一个临时变量存储旋转过程中的点位即可。
还有要注意一点就是要旋转的区域。分为奇偶两种场景，根据下面的图不难发现，其实奇偶都可以统一为同一片局域，即
/*
Author Owen_Q
*/
public class ImageRotator {
public static void rotate(int[][] matrix) {
int n = matrix.length;
int xLen = n >> 1;
int yLen = n - xLen;
for (int i = 0; i < xLen; i++) {
for (int j = 0; j < yLen; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[n - 1 - j][i];
matrix[n - 1 - j][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;
}
}
}
}
多想一点：将旋转变为对称
众所周知，旋转要分四个区域，想起来就很头疼，而对称性就很简单了，只需要找到一个轴，矩阵的任何位置都可以直接得出其对称点。那么研究不难发现，顺时针旋转90度就等于基于 和
两条直线轴对称。
| 原位置 | 第一次对称 | 第二次对称 |
|---|---|---|
/*
Author Owen_Q
*/
public class ImageRotator {
public static void rotateWithSymmetry(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
int yLen = n >> 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < yLen; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[i][n - j - 1];
matrix[i][n - j - 1] = temp;
}
}
}
}
73. Set Matrix Zeroes[Medium]
思路：将矩阵中所有包含0的行和列都置为0。那么最简单的就是一遍预处理标记所有包含0的行与列，另一遍进行变更。首先想到预处理肯定需要行列两个数组，但后来想到其实可以直接用第一行和第一列记录该行和该列是否包含0，这时只需要额外两个空间记录第一行和第一列是否包含0即可。这时，不难发现其实第一行第一列这一格没用上，那就可以用这个格来表示第一行是否为0，由此又可以省出一个空间，只需要开辟一个空间记录第一列是否为0即可。
/*
Author Owen_Q
*/
public class MatrixZerosSetter {
public static void setZeroes(int[][] matrix) {
boolean y0 = false;
int xLen = matrix.length;
int yLen = matrix[0].length;
for (int i = 0; i < xLen; i++) {
if (matrix[i][0] == 0) {
y0 = true;
break;
}
}
for (int i = xLen - 1; i >= 0; i--) {
for (int j = yLen - 1; j >= 0; j--) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
break;
}
}
}
for (int j = yLen - 1; j > 0; j--) {
for (int i = xLen - 1; i >= 0; i--) {
if (matrix[i][j] == 0) {
matrix[0][j] = 0;
break;
}
}
}
for (int i = xLen - 1; i >= 0; i--) {
for (int j = yLen - 1; j >= 1; j--) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
if (y0) {
matrix[i][0] = 0;
}
}
}
}
240. Search a 2D Matrix II[Medium]
思路：这题的思路倒是十分巧妙，可以用Z型搜索法，因为右下一定大于左上，因此右上一定是中间的位置，从当前位置开始，变大则向下，变小则向左，即可在 的复杂度内完成搜索
/*
Author Owen_Q
*/
public class MatrixSearcher {
public static boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix[0].length;
int i = 0;
int j = n - 1;
while (i < m && j >= 0) {
if (matrix[i][j] == target) {
return true;
}
if (matrix[i][j] > target) {
j--;
} else {
i++;
}
}
return false;
}
}
完结撒花
