中级编程通关练习题 #1 – 螺旋矩阵

给定一个整数N(N>=5),创建一个NxN的螺旋矩阵。下图分别是5×5,6×6,7×7的三个螺旋矩阵,螺旋位置用数值1表示,空位用数值0表示。

spiral matrix

输入样例:

N= 10

输出样例:

[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1] ,
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1] ,
[1, 1, 1, 1, 1, 1, 1, 1, 0, 1] ,
[1, 0, 0, 0, 0, 0, 0, 1, 0, 1] ,
[1, 0, 1, 1, 1, 1, 0, 1, 0, 1] ,
[1, 0, 1, 0, 0, 1, 0, 1, 0, 1] ,
[1, 0, 1, 0, 0, 0, 0, 1, 0, 1] ,
[1, 0, 1, 1, 1, 1, 1, 1, 0, 1] ,
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1] ,
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]

算法思路:

  • 要点:NxN的螺旋矩阵总共有N条直线上的位置需要设置为1。譬如,5×5螺旋矩阵的5条螺旋直线包含的位置数量分别是5、4、4、2、2,6×6螺旋矩阵则是 6、5、5、3、3、1,7×7螺旋矩阵是 7、6、6、4、4、2、2,……,10×10螺旋矩阵是 10、9、9、7、7、5、5、3、3、1,……依此类推。
  • 方法一:从初始位置(0,0)开始设置矩阵的数值为1,然后沿当前方向(0,1)顺沿位置直到当前螺旋直线终点。然后沿着四个方向 (0, 1), (1, 0), (0, -1), (-1, 0)轮流调整方向,并继续设置当前螺旋直线方向上的位置数值为1,直到N条螺旋直线都设置完毕。
  • 方法二:使用递归算法从矩阵的最小子矩阵0x0、1×1、2×2开始,[], [[1]], [[1, 1], [0, 1]],每次180度反转矩阵后分别扩展增加两位(0,1)和(1,1)子矩阵,然后逐步扩展到NxN矩阵。
  • 方法三:采用Numpy模块中的索引区间修改功能,对矩阵进行递归修改。
  • 方法四:先使用列表推导式创建NxN的回型矩阵,即由内往外的若干个数值1组成的正方形,每个数值1的正方形和其他数值1正方形分隔一个空位数值0的正方形,然后循环调整相关位置的数值变为螺旋矩阵。