算法刷题记录-螺旋矩阵
螺旋矩阵
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
示例 1：
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]
示例 2：
输入：n = 1
输出：[[1]]
思路，这题有点绕，我用了一个比res大2的布尔矩阵来存储被赋值的情况，赋值的逻辑是这样，可以往右赋值就往右赋值，否则就往下赋值，否则就往上赋值，否则就往上赋值，需要注意的是右的优先级其实是小于上的，比如多4*4的矩阵
| 1 | 2 | 3 | 4 |
|---|---|---|---|
| 5 | |||
| 11 | 6 | ||
| 10 | 9 | 8 | 7 |
在赋值完11后，此时既可以往右也可以往上，但正确来说应该是往上的，因此往右的逻辑是不能往上，代码如下：
public int[][] generateMatrix(int n) {
int[][] res=new int[n][n];
boolean[][] flag=new boolean[n+2][n+2];
int row=0,col=0;
int i=0;
for (int j = 0; j < n+2; j++) {
flag[j][0]=true;
flag[0][j]=true;
flag[j][n+1]=true;
flag[n+1][j]=true;
}
while (i<n*n) {
res[row][col] = i + 1;
flag[row + 1][col + 1] = true;
i++;
if (!flag[row + 1][col + 2] & flag[row][col + 1]) {
col++;
} else if (!flag[row + 2][col + 1]) {
row++;
} else if (!flag[row + 1][col]) {
col--;
} else if (!flag[row][col + 1]) {
row--;
}
}
return res;
}
螺旋矩阵二
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
思路：与上一题一模一样的做法，只不过矩阵的大小不一定是n*n的。
public List<Integer> spiralOrder(int[][] matrix) {
ArrayList<Integer> res=new ArrayList<Integer>();
int m=matrix.length;
int n=matrix[0].length;
boolean[][] flag=new boolean[m+2][n+2];
for (int i = 0; i < n+2; i++) {
flag[0][i]=true;
flag[m+1][i]=true;
}
for (int i = 0; i < m+2; i++) {
flag[i][0]=true;
flag[i][n+1]=true;
}
int row=0,col=0;
int i=0;
while (i<m*n) {
res.add(matrix[row][col]);
flag[row + 1][col + 1] = true;
i++;
if (!flag[row + 1][col + 2] & flag[row][col + 1]) {
col++;
} else if (!flag[row + 2][col + 1]) {
row++;
} else if (!flag[row + 1][col]) {
col--;
} else if (!flag[row][col + 1]) {
row--;
}
}
return res;
}