旋转生成矩阵(Spiral Matrix)

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,

Given n = 3,

You should return the following matrix:

[[ 1, 2, 3 ],]

与之前蛇形遍历一个思路,给定几个状态x,y,state(说明当前生成的方向)

在这个问题中,只有以下几种情况:向上生成到顶时,向右生成;向右生成到顶时,向下生成;向下生成到顶时,向左生成;向左生成到顶时,向上生成。最终的结束条件是生成了n^2个数字。

首先生成一个n*n的矩阵:

1
2
3
4
5
rs = []
for i in range(n):
rs.append([])
for j in range(n):
rs[i].append(None)

这样就得到了一个n*n的空矩阵。

开始时尝试过

1
[[None]*n]*n

1
[[None for i in range(n)]]*n

的方式,发现均会出现问题。原因是以这种方式生成的二维数组的子项指向的是同一个对象。其后果是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
>>> a = [[None]*5]*5
>>> a
[[None, None, None, None, None],
[None, None, None, None, None],
[None, None, None, None, None],
[None, None, None, None, None],
[None, None, None, None, None]]
>>> a[2][2] = 1
>>> a
[[None, None, 1, None, None],
[None, None, 1, None, None],
[None, None, 1, None, None],
[None, None, 1, None, None],
[None, None, 1, None, None]]

使用built-in查看它们的id发现:

1
2
>>> id(a[2]),id(a[3])
(4337281432, 4337281432)

因此放弃看上去简洁的写法。

更新:发现一个简洁有效的写法:

1
x = [[None for i in range(n)] for j in range(n)]

之后找出每个方向的条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
while step <= n**2:
# print x,y,state,step,layer,tmp
rs[x][y] = step
if state == 'up':
if x == layer:
y += 1
state = 'right'
else:x -= 1
elif state == 'right':
if y+1 == n-layer:
x += 1
state = 'down'
else:y+=1
elif state == 'down':
if x+1 == n-layer:
y -= 1
state = 'left'
else:x+=1
elif state == 'left':
if y == layer:
x-=1
state= 'up'
else:y-=1
step += 1

大意如此。其中layer为当前从外向内已生成完的层数,由

1
if step == n**2-(n-layer*2-2)**2:layer+=1

可以得到。