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