写在前面
其实螺旋矩阵类的题目按理来说应该是简单的，因为是纯粹的模拟，只不大家定义方向的方式各有不同，以及方向的转换以及判断不够灵活，所以我们就简单试试！
螺旋矩阵
LeetCode原题链接
题目描述
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例1
示例 2：
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.lengthn == matrix[i].length1 <= m, n <= 10-100 <= matrix[i][j] <= 100
解读
其实这是很经典的顺时针螺旋矩阵了，只需要定义好方向，判断好数组边界以及已访问边界，就可以很顺利解决了。所以接下来我们简单看看实现。
最重要的事情其实是定义好方向，然后根据方向进行走步。
学会优雅的第一步，就是勇敢的派出一个探子，让它去尝试，如果它失败了我们就换方向走一步，否则就原方向走一步
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
| class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<>();
int n = matrix.length;
int m= matrix[0].length;
int[][] direction = {{0,1},{1,0},{0,-1},{-1,0}};
int dir_key=0;
int i=0,j=0;
for(int c = 0; c < n * m; c++){
res.add(matrix[i][j]);
matrix[i][j]=101;
int i_try = i + direction[dir_key][0];
int j_try = j + direction[dir_key][1];
if(i_try<0 || i_try>=n || j_try<0 || j_try>=m || matrix[i_try][j_try]>100){
dir_key = (dir_key+1)%4;
}
i = i+direction[dir_key][0];
j = j+direction[dir_key][1];
}
return res;
}
}
|
螺旋矩阵II
LeetCode原题链接
题目描述
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
示例 1：
1
2
| 输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]
|
示例 2：
提示：
解读
其实本质上和上题是同样的思路，只不过一个是写入，一个是读取，不多赘述
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int[][] generateMatrix(int n) {
int[][] res = new int[n][n];
int[][] way = {{0,1},{1,0},{0,-1},{-1,0}};
int c=0,l=0;
int way_key = 0;
for(int i=1;i<=n*n;i++){
res[c][l]=i;
int nextc = c + way[way_key][0];
int nextl = l + way[way_key][1];
if (nextc < 0 || nextc >= n || nextl < 0 || nextl >= n || res[nextc][nextl] != 0) {
way_key = (way_key + 1) % 4;
}
c = c+way[way_key][0];
l = l+way[way_key][1];
}
return res;
}
}
|
螺旋矩阵III
这题还有有一点令人难受的，因为需要剪枝才能让效率稍微好一些，但是我剪的也不是非常好
LeetCode原题链接
题目描述
在 rows x cols 的网格上，你从单元格 (rStart, cStart) 面朝东面开始。网格的西北角位于第一行第一列，网格的东南角位于最后一行最后一列。
你需要以顺时针按螺旋状行走，访问此网格中的每个位置。每当移动到网格的边界之外时，需要继续在网格之外行走（但稍后可能会返回到网格边界）。
最终，我们到过网格的所有 rows x cols 个空间。
按照访问顺序返回表示网格位置的坐标列表。
示例 1：
1
2
| 输入：rows = 1, cols = 4, rStart = 0, cStart = 0
输出：
|
示例 2：
1
2
| 输入：rows = 5, cols = 6, rStart = 1, cStart = 4
输出：
|
提示：
1 <= rows, cols <= 1000 <= rStart < rows0 <= cStart < cols
解读
其实还是老模板，只不过这次不会碰壁，是由内而外，所以需要自己判断螺旋什么时候需要走多少步。
其实我们可以发现，只要方向由上下变为左右的时候，就需要把螺旋的边长增加1，这点需要自己品味，为什么我设置的初始方向是向上，初始step是0，其实都是有一点意思的。
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
| class Solution {
public int[][] spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
int r_n=rStart;
int c_n=cStart;
int step =0;
int[][] direction = {{0,1},{1,0},{0,-1},{-1,0}};
int dir_key = 3;
int count=1;
int[][] res=new int[rows*cols][2];
res[0][0]=r_n;
res[0][1]=c_n;
while(count<rows*cols){
if(dir_key%2==1){
step+=1;
}
dir_key = (dir_key+1)%4;
if((r_n<0&&direction[dir_key][0]<=0)||
(c_n<0&&direction[dir_key][1]<=0)||
(r_n>=rows&&direction[dir_key][0]>=0)||
(c_n>=cols&&direction[dir_key][1]>=0)){
r_n=r_n+direction[dir_key][0]*step;
c_n=c_n+direction[dir_key][1]*step;
continue;
}
for(int i=0;i<step;i++){
r_n=r_n+direction[dir_key][0];
c_n=c_n+direction[dir_key][1];
if(r_n>=0&&r_n<rows&&c_n>=0&&c_n<cols){
res[count][0]=r_n;
res[count][1]=c_n;
count++;
}
}
}
return res;
}
}
|
螺旋矩阵IV
LeetCode原题链接
题目描述
给你两个整数：m 和 n ，表示矩阵的维数。
另给你一个整数链表的头节点 head 。
请你生成一个大小为 m x n 的螺旋矩阵，矩阵包含链表中的所有整数。链表中的整数从矩阵 左上角 开始、顺时针 按 螺旋 顺序填充。如果还存在剩余的空格，则用 -1 填充。
返回生成的矩阵。
示例 1：
1
2
3
4
| 输入：m = 3, n = 5, head = [3,0,2,6,8,1,7,9,4,2,5,5,0]
输出：[[3,0,2,6,8],[5,0,-1,-1,1],[5,2,4,9,7]]
解释：上图展示了链表中的整数在矩阵中是如何排布的。
注意，矩阵中剩下的空格用 -1 填充。
|
示例 2：
1
2
3
4
| 输入：m = 1, n = 4, head = [0,1,2]
输出：[[0,1,2,-1]]
解释：上图展示了链表中的整数在矩阵中是如何从左到右排布的。
注意，矩阵中剩下的空格用 -1 填充。
|
提示：
1 <= m, n <= 1051 <= m * n <= 105- 链表中节点数目在范围
[1, m * n] 内
0 <= Node.val <= 1000
解读
这题不多说啊，直接照搬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
|
class Solution {
public int[][] spiralMatrix(int m, int n, ListNode head) {
int[][] res = new int[m][n];
for(int i=0;i<m;i++){
Arrays.fill(res[i],-1);
}
int[][] direction = {{0,1},{1,0},{0,-1},{-1,0}};
int dir_key=0;
int i=0,j=0;
ListNode pre=head;
while(pre!=null){
res[i][j] = pre.val;
pre=pre.next;
int i_try = i + direction[dir_key][0];
int j_try = j + direction[dir_key][1];
if(i_try<0 || i_try>=m || j_try<0 || j_try>=n || res[i_try][j_try]!=-1){
dir_key = (dir_key+1)%4;
}
i = i+direction[dir_key][0];
j = j+direction[dir_key][1];
}
return res;
}
}
|
关于边界处理
其实I和IV都取巧了，就是在判断有没有达到边界的时候，用了数值的范围。
所以其实墙壁也需要交给我们管理的，所以对于IV的代码，我们也可以这么写。
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
|
class Solution {
public int[][] spiralMatrix(int m, int n, ListNode head) {
int[][] res = new int[m][n];
for(int i=0;i<m;i++){
Arrays.fill(res[i],-1);
}
int[][] direction = {{0,1},{1,0},{0,-1},{-1,0}};
int dir_key=0;
int i=0,j=0;
ListNode pre=head;
int top=0,left=0,bottom=m-1,right=n-1;
while(pre!=null){
res[i][j] = pre.val;
pre=pre.next;
int i_try = i + direction[dir_key][0];
int j_try = j + direction[dir_key][1];
if(i_try<top || i_try>bottom || j_try<left || j_try>right){
dir_key = (dir_key+1)%4;
if(dir_key==0) left+=1;
if(dir_key==1) top+=1;
if(dir_key==2) right-=1;
if(dir_key==3) bottom-=1;
}
i = i+direction[dir_key][0];
j = j+direction[dir_key][1];
}
return res;
}
}
|
