Skip to content

Latest commit

 

History

History

058. Spiral Matrix II

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 

这道题我戏称为“迷宫题”。回忆一下小时候在公园里,是否遇到过这样一种简陋迷宫,迷宫里不断的转圈,最终你进入了一个圆圈的中心,可能有个小广场,小雕塑,或是小房子在那里等着你。

这道题只不过把圈圈变成了正方形罢了。处于中心位置的数,恰好是 n*n.


不知道上述的描述会不会给你什么启发,而我就是完全依照这个思路去解的,所以效率也许并不高,也说不出这属于那种算法的范畴。以三维矩阵为例,设行为i, 列为j,如果把最外圈转一遍,记录步骤如下表:

i j 条件 动作
0 0 i==0 && j!=n-1 ++j
0 1 i==0 && j!=n-1 ++j
0 2 i==0 && j!=n-1 ++j
1 2 j==n-1 && i!=n-1 ++i
2 2 j==n-1 && i!=n-1 ++i
2 1 i==n-1 && j!=0 --j
2 0 i==n-1 && j!=0 --j
1 0 j==0 && i!=0 --i
0 0 j==0 && i!=0 --i

可以发现,最后我们又回到了原点,却没有像我们想象的那样,停在[1][0]的地方,在迷宫里,这个地方意味着你面对着一堵墙,你不能去撞墙,而是要右转进入下一个圈圈。

程序里,我们就要为墙所在的地方设置标记位。换句话说,我们也可以给不为墙的地方设置标记位,如给二维数组初始化时,将值设为 -1.那么走过的地方自然不可能为 -1,就成了墙。

所以转圈停止的条件为: Matrix[i][j] != -1;

ok,如果将每一步产生的值记录下来(设为value, 每走一步就自加), 那么当 value == nn 的时候就算走到了中心。如果不等于 nn,就要向里面再转一圈。

思路很清楚了,我觉得这个解法很直接,代码也并不繁复,非常好理解。请大家拍砖。