题目
力扣上已经有很多题解了,但是总觉得很多题解有点复杂不太符合直觉,下面两种解法是我认为比较简洁易懂的。(虽然这两种方法的用时与内存都不算特别优化。
解法一:根据螺旋规律输出
这种方法有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()转换。