[随缘一题]螺旋矩阵

数据结构和算法►数组 , , 评论

PS

本题代码来源于九章算法.

来源

lintcode-螺旋矩阵

描述

给出整数 n, 返回一个大小为 n * n 的螺旋矩阵

样例

1
2
3
4
5
6
7
8
给出 n = 3
则螺旋矩阵为:

[
[1,2,3]
[8,9,4]
[7,6,5]
]
1
2
3
4
5
6
7
8
9
10
给出 n = 5
则螺旋矩阵为:

[
 [1,2,3,4,5]
 [16,17,18,19,6]
 [15,24,25,20,7]
 [14,23,22,21,8]
 [13,12,11,10,9]
]

解题思路

这道题标的是简单题,但是我没做出来…

因此借鉴了九章算法的实现方法,链接在文首给出,这里分析一下实现.

  1. 不要想着向右走几步,之后向下转.而是每一步走完,判断是否转向,计算下一步所在位置的x,y下标.

  2. 不要想着在向右的过程中,x左边不变,y坐标加1,而是每一步的x,y坐标都会变化,变化的量不同

都是血泪教训啊.

剩下的思路较为简单,写了详细的注释在代码里.

实现代码

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
public int[][] spiralArray(int n) {
  int[][] res = new int[n][n];
  //定义每一步的x,y轴增量,顺序为右下左上,比如:当向右走的时候,x坐标不变,y坐标每次加1.
  int[] dx = new int[]{0, 1, 0, -1};
  int[] dy = new int[]{1, 0, -1, 0};

  //x,y作为当前的下标
  //d为方向

  //i,y遍历用
  //nx,ny,下一个的x,y坐标

  int x, y, d;
  int i, j, nx, ny;
  // 将二维数组全部初始化为-1,-1用来判断当前位置是否已经走过
  for (i = 0; i < n; ++i) {
    for (j = 0; j < n; ++j) {
      res[i][j] = -1;
    }
  }

  x = 0;
  y = 0;
  d = 0;
  //i在这个时候相当于每个位置应该放的数字
  for (i = 1; i <= n * n; ++i) {
    //当前位置放置i
    res[x][y] = i;
    //计算下一个的x,y坐标.  计算方法为:x+增量,增量由当前的方向决定
    nx = x + dx[d];
    ny = y + dy[d];

    //判断下一步的x,y坐标是否有问题,包括:四种越界和该位置已经走过了
    if (nx < 0 || nx >= n || ny < 0 || ny >= n || res[nx][ny] != -1) {
      //如果下一步有问题,转向,转向方法为:(d+1)%4,这样可以按照右下左上的顺序来旋转
      d = (d + 1) % 4;
      //方向改变,增量改变,重新计算新的下一步坐标
      nx = x + dx[d];
      ny = y + dy[d];
    }
    //走下一步
    x = nx;
    y = ny;
  }
  //返回.
  return res;
}

完。




ChangeLog

2018-12-27 完成

以上皆为个人所思所得，如有错误欢迎评论区指正。

欢迎转载，烦请署名并保留原文链接。

联系邮箱：huyanshi2580@gmail.com

更多学习笔记见个人博客——>呼延十

呼延十Developer

个人简介。