螺旋矩阵

题目链接:leetcode 54leetcode 59

题目描述

leetcode 54:螺旋矩阵

给你一个 mn 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。

示例 1:

img

1
2
输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,3,6,9,8,7,4,5]

示例 2:

img

1
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]

提示:

  • $m == matrix.length$
  • $n == matrix[i].length$
  • $1 <= m, n <= 10$
  • $-100 <= matrix[i][j] <= 100$

leetcode 59:螺旋矩阵 II

给你一个正整数 n ,生成一个包含 1n2 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix

示例 1:

img

1
2
输入:n = 3
输出:[[1,2,3],[8,9,4],[7,6,5]]

示例 2:

1
2
输入:n = 1
输出:[[1]]

提示:

  • 1 <= n <= 20

题解

leetcode 54:螺旋矩阵

简单模拟:

为了避免判断边界,需要在矩阵的最外侧围上一圈 1

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> list = new ArrayList<>();
if (matrix == null || matrix.length == 0)
return list;
int row = matrix.length, col = matrix[0].length;
boolean[][] visit = new boolean[row + 2][col + 2]; //记录该位置是否被遍历过

//下面两个 for 循环在 visit矩阵外侧围一圈 1,表示已被访问过,不可再次访问
for (int i = 0; i < row + 2; i++) {
visit[i][0] = true;
visit[i][col + 1] = true;
}
for (int j = 0; j < col + 2; j++) {
visit[0][j] = true;
visit[row + 1][j] = true;
}

int i = 1, j = 1; //由于外圈多围了一圈,所以初始位置从(0,0)变为了(1,1)
int direction = 3; //定义一个变量,记录当前的方向,上下左右分别为:0,1,2,3
while (true) {
if (visit[i][j]) //如果四个方向都无路可走了,程序就结束了
break;
list.add(matrix[i - 1][j - 1]); //由于外圈加了一层,所以对应的matrix矩阵中的下标需要减一
visit[i][j] = true; //标记当前的格子已被访问过
switch (direction) {
case 0: //上
if (visit[i - 1][j]) { // 如果沿着当前方向走会碰到墙,那么就换个方向
direction = 3; //上面走不通,向右
j++;
} else { //否则,继续沿着当前方向走
i--;
}
break;
case 1: //下
if (visit[i + 1][j]) {
direction = 2; //下面走不通,向左
j--;
} else {
i++;
}
break;
case 2: //左
if (visit[i][j - 1]) {
direction = 0; //左面走不通,向上
i--;
} else {
j--;
}
break;
case 3: //右
if (visit[i][j + 1]) {
direction = 1; //右面走不通,向下
i++;
} else {
j++;
}
break;
}
}
return list;
}
}

leetcode 59:螺旋矩阵 II

代码把上面的代码热热还能用:

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
public int[][] generateMatrix(int n) {
int[][] matrix = new int[n][n];
boolean[][] visit = new boolean[n + 2][n + 2]; //记录该位置是否被遍历过

//下面两个 for 循环在 visit矩阵外侧围一圈 1,表示已被访问过,不可再次访问
for (int i = 0; i < n + 2; i++) {
visit[i][0] = true;
visit[i][n + 1] = true;
}
for (int j = 0; j < n + 2; j++) {
visit[0][j] = true;
visit[n + 1][j] = true;
}

int i = 1, j = 1; //由于外圈多围了一圈,所以初始位置从(0,0)变为了(1,1)
int direction = 3; //定义一个变量,记录当前的方向,上下左右分别为:0,1,2,3
int num = 1; //将要填的数字
while (true) {
if (visit[i][j]) //如果四个方向都无路可走了,程序就结束了
break;
matrix[i - 1][j - 1] = num++; //由于外圈加了一层,所以对应的matrix矩阵中的下标需要减一
visit[i][j] = true; //标记当前的格子已被访问过
switch (direction) {
case 0: //上
if (visit[i - 1][j]) { // 如果沿着当前方向走会碰到墙,那么就换个方向
direction = 3; //上面走不通,向右
j++;
} else { //否则,继续沿着当前方向走
i--;
}
break;
case 1: //下
if (visit[i + 1][j]) {
direction = 2; //下面走不通,向左
j--;
} else {
i++;
}
break;
case 2: //左
if (visit[i][j - 1]) {
direction = 0; //左面走不通,向上
i--;
} else {
j--;
}
break;
case 3: //右
if (visit[i][j + 1]) {
direction = 1; //右面走不通,向下
i++;
} else {
j++;
}
break;
}
}
return matrix;
}
}
坚持原创技术分享,感谢您的支持和鼓励!