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]
思路：
其实这一题和迷宫问题有些类似，你可以理解为：都是从一个固定的起始点找一条合适的路线最终到达终点。相同的地方就是已遍历过的点不能再遍历了，这个点很关键。而为了解决这个重复遍历问题，此处也是借鉴了迷宫问题的思路，设置一个标记矩阵专门用来记录已遍历过的点，比如：某位置记为0，说明该位置还没有遍历；记为1，说明该位置已经遍历过了，之后就再也不能遍历了。还有一个点很关键，就是遍历的方向选择问题。本题所给的要求就是顺时针方向，迷宫问题也是给出了4个方向供每个点去选择，而这4个方向也是有优先级的，所以借鉴这个思路，此处也是给出了按照顺时针方向的4个方向供选择。具体可见下图，方便理解。
具体代码如下：
class Solution:
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
if len(matrix) == 0:
return []
matrix_row, matrix_col = len(matrix), len(matrix[0])
# 定义一个维度和matrix相同的全0矩阵，用于找到点移动的路线；0代表可以通过，1代表不能通过
detect_matrix = []
for _ in range(matrix_row):
detect_matrix.append([0]*matrix_col)
# 定义点移动的方向集合，先后顺序代表优先级，题目要求顺时针旋转
move_direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]
# 定义移动点的初始位置
start_pos = [0, 0]
detect_matrix[0][0] = 1
# 定义保存最终结果的集合，初始元素就是起始值
final_matrix = [matrix[0][0]]
print(detect_matrix)
while True:
# 遍历检测矩阵，如果当前矩阵中没有0元素，说明原matrix矩阵已经遍历完成
for each_row in detect_matrix:
if 0 not in each_row:
break
# 获取当前位置start_pos的可移动方向
next_direction = self.get_direction(start_pos, move_direction, detect_matrix)
print("next_direction", next_direction)
# 如果当前位置不能移动了，说明原matrix矩阵已经遍历完成；反之则可按给定方向移动
if next_direction is not None:
# 获取当前位置start_pos按求得next_direction方向移动的下一个坐标位置
next_pos = start_pos.copy()
next_pos[0] += next_direction[0]
next_pos[1] += next_direction[1]
# 按照求得next_direction方向一直移动start_pos点，直到超出矩阵matrix的范围或者当前位置为1不可通过了
while True:
print("next_pos", next_pos)
if next_pos[0] in range(matrix_row) and next_pos[1] in range(matrix_col) and detect_matrix[next_pos[0]][next_pos[1]] != 1:
next_pos_copy = next_pos.copy()
# 将符合要求遍历得到的点保存到final_matrix集合中
final_matrix.append(matrix[next_pos_copy[0]][next_pos_copy[1]])
# 当前点遍历了，将其设为1，表示其已经不能再遍历了
detect_matrix[next_pos[0]][next_pos[1]] = 1
# 继续按照给定方向遍历下一个坐标点
next_pos[0] += next_direction[0]
next_pos[1] += next_direction[1]
# 如果当前位置不符合要求，则要回到上一步位置，准备切换方向继续遍历
else:
start_pos = next_pos.copy()
start_pos[0] -= next_direction[0]
start_pos[1] -= next_direction[1]
break
else:
break
return final_matrix
def get_direction(self, start_pos, move_direction, detect_matrix):
# 按照给定的4个方向遍历，按照方向的先后顺序如果有哪个方向可通过，则立即返回该方向；反之，则返回None，说明没有方向可通过了
for direction in move_direction:
next_pos = start_pos.copy()
next_pos[0] += direction[0]
next_pos[1] += direction[1]
row, col = len(detect_matrix), len(detect_matrix[0])
if next_pos[0] in range(row) and next_pos[1] in range(col) and detect_matrix[next_pos[0]][next_pos[1]] != 1:
return direction
return None
if __name__ == "__main__":
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
final_matrix = Solution().spiralOrder(matrix)
print(final_matrix)
执行效率算是中等偏上吧，在70%左右。