我也曾经对那种力量一无所知!论算法的重要性

用户头像
Jazzy
关注
发布于: 2020 年 05 月 06 日
我也曾经对那种力量一无所知!论算法的重要性

Leetcode54题:螺旋矩阵54. 螺旋矩阵

题目描述:

给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。

示例1:

输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]



示例2:

输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]



解题过程,3个思路,时间和空间都相同的情况下,最后一个的写法让我对那种力量一无所知:

# solution 1
class Solution:
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
if matrix == [] : return []
res = []
maxUp = maxLeft = 0
maxDown = len(matrix) - 1
maxRight = len(matrix[0]) - 1
direction = 0 # go right, 1 go down, 2 go left, 3 up
while True:
if direction == 0:
for i in range(maxLeft, maxRight+1):
res.append(matrix[maxUp][i])
maxUp += 1
elif direction == 1: # go down
for i in range(maxUp, maxDown+1):
res.append(matrix[i][maxRight])
maxRight -= 1
elif direction == 2: # go left
for i in reversed(range(maxLeft, maxRight+1)):
res.append(matrix[maxDown][i])
maxDown -= 1
else: # go up
for i in reversed(range(maxUp, maxDown+1)):
res.append(matrix[i][maxLeft])
maxLeft += 1
if maxUp > maxDown or maxLeft > maxRight:
return res
direction = (direction + 1) % 4



# solution 2
class Solution:
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
if len(matrix) == 0: return []
left = 0
up = 0
down = len(matrix) - 1
right = len(matrix[0]) - 1
# 0 -> right, 1 -> down, 2 -> left, 3 -> up
direction = 0
# start location
x, y = 0, 0
res = []
while True:
if left > right or up > down:
return res
if direction == 0:
while y <= right:
res.append(matrix[up][y])
y += 1
up += 1
x = up
direction = 1
continue
if direction == 1:
while x <= down:
res.append(matrix[x][right])
x += 1
right -= 1
y = right
direction = 2
continue
if direction == 2:
while y >= left:
res.append(matrix[down][y])
y -= 1
down -= 1
x =down
direction = 3
continue
if direction == 3:
while x >= up:
res.append(matrix[x][left])
x -= 1
left += 1
y = left
direction = 0
continue



# solution 3
# 一行代码搞定
lass Solution:
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
return matrix and list(matrix.pop(0)) + self.spiralOrder(list(zip(*matrix))[::-1])



最后执行结果



时间消耗和内存占用



发布于: 2020 年 05 月 06 日 阅读数: 35
用户头像

Jazzy

关注

We slove problem by thinking。 2017.11.11 加入

生活中养成很多良好的习惯有助于改善我们的生活,让我们的生活过得更好,反之亦然。如果想要过上悲惨的生活就不去培养良好的习惯。

评论

发布
暂无评论
我也曾经对那种力量一无所知!论算法的重要性