每天一道算法:螺旋矩阵

52、螺旋矩阵

题目

给定一个矩阵 m*n,返回所有元素的螺旋排列顺序(从左上角开始,顺时针旋转,由外向内)。

示例:

思路

1、递归法

先输出最外圈的顺时针顺序,然后用同样方法处理剩下的元素。

最外圈的顺时针顺序为:

1、最上面一行,从左到右

2、最右面一列,从上到下

3、最下面一行,从右到左

4、最左面一列,从下到上

然后,使用递归法,处理第二圈、第三圈等,直到矩阵最中间的一圈被处理完毕(这也是递归结束条件)。

2、递归法(一行代码)

另外一种递归法:

1、读取最上面一行,从左到右

2、将最上面一行从矩阵中删除

3、将矩阵逆时针旋转90度。

4、递归,继续处理最上面一行。

递归结束条件:矩阵为空。

实际上,这种方法只需要用一行python代码便可以实现:

其中,

1、当 matrix = [] 时,matrix and [*matrix.pop(0)] 这个表达式返回 [],这是因为 and 符号连接时,先计算左边的正负,时,matrix 为空,为FALSE,因此不必再计算 and 右边的表达式。直接返回 matrix,即 []。

2、[*zip(*matrix)] 表示将 matrix 的第一列作为第一行,第二列作为第二行... 即将矩阵进行对角线对称。

python语法:

后面加上可迭代对象,相当于将可迭代对象依次列出

可以用在两个场合:

(1)[*a] 表示将a变为list,相当于 list(a)

(2)fun(*a) 表示将a变为list,并且每个元素分别作为fun()的一个参数,即这时 fun 被传入了多个参数,而不是一个。

比如:

相当于执行了 type(1,2,3),因此会报错。

3、[*zip(*matrix)][::-1] 表示先将 matrix 进行对角线对称,然后将所有行逆序排列。

比如原矩阵为:

先对角线对称:

再逆序排列:

可见, matrix3 是 matrix 逆时针旋转 90 度的结果。

代码

python实现

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181210G0M4OA00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券