Leetcode【54、59、885】
问题描述：【Array】54. Spiral Matrix
解题思路：
这道题是给一个矩阵，按顺时针螺旋输出所有数字。
这道题做法很直接，就是从最外层到最内层一层一层按照顺时针螺旋输出各个数字即可。如下图所示：
用 (i, j) 表示矩阵坐标，k 表示层数。对于每一层，我们从左到右（橙色）、从上到底（红色）、从底到左（绿色）、从左到上（蓝色）依次输出。然后，层数加 1，进入下一层继续循环输出。直到输出所有数字。
编程时，注意找到 i、j 下标及层数 k 的对应关系。例如从左到右（橙色）的判断条件是 if i == k and j != n - 1- k:（初始化 i = j = k = 0）。
Python3 实现：
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix:
return []
m, n = len(matrix), len(matrix[0])
i = j = k = 0 # (i,j)表示坐标, k表示层数
ans = []
while True:
if i == k and j != n - 1 - k: # 从左到右
ans.append(matrix[i][j])
j += 1
elif i != m - 1 - k and j == n - 1 - k: # 从右到底
ans.append(matrix[i][j])
i += 1
elif i == m - 1 - k and j != k: # 从底到左
ans.append(matrix[i][j])
j -= 1
elif i != k and j == k: # 从左到上
ans.append(matrix[i][j])
i -= 1
if i == k: # 遍历完一层，进入下一层
i += 1
j += 1
k += 1
else: # 方阵情况(m=n)，最后输出最中心的数字
ans.append(matrix[i][j])
if len(ans) == m * n: # 达到长度，返回结果
return ans问题描述：【Array】59. Spiral Matrix II
解题思路：
这道题是给一个数字 n，按顺时针螺旋顺序将 1~n^2 保存到 n*n 矩阵中。
思路同上面的 Leetcode 54。
Python3 实现：
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
matrix = [[0] * n for _ in range(n)]
cnt = 1
i = j = k = 0 # (i,j)表示坐标, k表示层数
while cnt <= n * n:
if i == k and j != n - 1 - k: # 从左到右
matrix[i][j] = cnt; cnt += 1
j += 1
elif i != n - 1 - k and j == n - 1 - k: # 从右到底
matrix[i][j] = cnt; cnt += 1
i += 1
elif i == n - 1 - k and j != k: # 从底到左
matrix[i][j] = cnt; cnt += 1
j -= 1
elif i != k and j == k: # 从左到上
matrix[i][j] = cnt; cnt += 1
i -= 1
if i == k: # 遍历完一层，进入下一层
i += 1; j += 1; k += 1
else: # 最后填充最中心的数字
matrix[i][j] = cnt; cnt += 1
return matrix题目描述：【Array】885. Spiral Matrix III
解题思路：
这道题是在 R 行 C 列的矩阵上，从 (r0, c0) 面朝东面开始按顺时针按螺旋状行走，访问此网格中的每个位置。每当移动到网格的边界之外时，会继续在网格之外行走（但稍后可能会返回到网格边界）。最终，到过网格的所有 R * C 个空间，按照访问顺序返回表示网格位置的坐标列表。
这道题的关键是要知道每次要朝一个方向走几步或者什么时候转向。以示例 2 为例：
可以观察到，由 1 到 2、2 到 3 各走一步；由 3 到 5、5 到 7 各走两步；.... 因此可以发现，每两次转向，步数加 1。
编程时，我们用一个变量 tour 控制四个方向 (使用 tour % 4 实现)，每次转向 tour += 1；用 step 表示一个方向走 step 步才转向；用 cnt 表示转向的次数，每转两次向让 step += 1。因此，我们很容易写出代码。注意，可能走出网格，网格之外的坐标不加入到最后的结果中就行。
Python3 实现：
class Solution:
def spiralMatrixIII(self, R: int, C: int, r0: int, c0: int) -> List[List[int]]:
ans = []
i, j = r0, c0 # (i,j)表示坐标位置
ans.append([i, j])
step = cnt = tour = 0 # step表示朝一个方向走step步, cnt表示转向次数, tour表示走完step步改变一次方向
while len(ans) < R * C:
if cnt % 2 == 0: # 两次转向后对step值加1
step += 1
tmp = step
while tmp != 0 and tour % 4 == 0: # 向东
tmp -= 1
j += 1
if 0 <= i < R and 0 <= j < C: # 坐标不能越界
ans.append([i, j])
while tmp != 0 and tour % 4 == 1: # 向南
tmp -= 1
i += 1
if 0 <= i < R and 0 <= j < C:
ans.append([i, j])
while tmp != 0 and tour % 4 == 2: # 向西
tmp -= 1
j -= 1
if 0 <= i < R and 0 <= j < C:
ans.append([i, j])
while tmp != 0 and tour % 4 == 3: # 向北
tmp -= 1
i -= 1
if 0 <= i < R and 0 <= j < C:
ans.append([i, j])
tour += 1 # 走完step步改变一次方向
cnt += 1 # 转向次数加1
return ans本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019.07.02 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
