【python】54. 螺旋矩阵

2021/6/17 1:23:43

本文主要是介绍【python】54. 螺旋矩阵,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目

54. 螺旋矩阵

力扣上已经有很多题解了,但是总觉得很多题解有点复杂不太符合直觉,下面两种解法是我认为比较简洁易懂的。(虽然这两种方法的用时与内存都不算特别优化。

解法一:根据螺旋规律输出

这种方法有C++版本,这个思路很符合问题的常规思考方向,又可以比较简洁地遍历四个方向。

观察螺旋规律

  • 从 matrix[0][-1] 为起点,开始(这里的起点不是指实际上的第一排第一列的元素,而只是一个位置控制。如果是从matrix[0][0]开始,则在顺时针的方案中第一个操作的元素会是matrix[0][1],最后会溢出)
  • 向右出发,那么第一次会走 n 步,n为列数
  • 向下转,会走 m - 1 步,m为行数
  • 向左转,n - 1 步
  • 向上转,m - 2 步

从上可以看出,n-->m-1-->n-1-->m-2-->n-2-->m-3-->...-->1,步数在行与列依次减少一。因此,利用数组sz的值控制好步数和步数的变化,便可将所有元素依次填入ans数组。

其中dd为方向数组,分别为向右(纵坐标+1),向下(横坐标+1),向左(纵坐标-1)与向上(横坐标-1)。通过d = (d + 1) % len(dd)遍历方向数组即可顺序切换方向。
如果是逆时针,则方向数组顺序为:向下(横坐标+1),向右(纵坐标+1),向上(横坐标-1)与向左(纵坐标-1)

个人编写的python版本:

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        sz = [len(matrix[0]), len(matrix)]
        ans = [0] * sz[0] * sz[1]
        sz[1] = sz[1] - 1

        dd = [[0, 1], [1, 0], [0, -1], [-1, 0]]
        idx = 0
        d = 0
        x = 0
        y = -1
        while idx != len(ans):
            for i in range(sz[d % 2]):
                x = x + dd[d][0] 
                y = y + dd[d][1]
                ans[idx] = matrix[x][y]
                idx = idx + 1
            sz[d % 2] = sz[d % 2] - 1
            d = (d + 1) % len(dd)
        return ans

如果是逆时针螺旋,则需要对应修改数组sz、方向数组dd与起始位置xy:

        sz[0] = sz[0] - 1

        dd = [[1, 0], [0, 1], [-1, 0], [0, -1]]
        idx = 0
        d = 0
        x = -1
        y = 0

解法二:削苹果

这个解法相当简洁,思路跟削苹果一样,旋转一下矩阵,然后削去最上方的头,直到整颗苹果削完。

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        res = []
        while matrix:
            # 削头(第一层)
            res += matrix.pop(0)
            # 将剩下的逆时针转九十度,等待下次被削
            matrix = list(zip(*matrix))[::-1]
        return res

其中:

  •  List pop() 默认是pop最后一个元素,默认为 index=-1,这里pop的是第一行(list matrix的第一个元素)。(这操作很符合直觉,一看到这个问题,首先就很容易想到用栈这个数据结构来解决。
  • zip() 是python的内置函数,在python3中返回的是一个对象,需要手动list()转换。


这篇关于【python】54. 螺旋矩阵的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程