LeetCode 885. Spiral Matrix III

2024-03-31 18:14:16

题目描述

在 R 行 C 列的矩阵上，我们从 (r0, c0) 面朝东面开始

这里，网格的西北角位于第一行第一列，网格的东南角位于最后一行最后一列。

现在，我们以顺时针按螺旋状行走，访问此网格中的每个位置。

每当我们移动到网格的边界之外时，我们会继续在网格之外行走（但稍后可能会返回到网格边界）。

最终，我们到过网格的所有 R * C 个空间。

按照访问顺序返回表示网格位置的坐标列表。

tag

矩阵遍历矩阵模拟

样例

1
2

输入：R = 5, C = 6, r0 = 1, c0 = 4
输出：[[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]

算法1

(模拟) O(max(M,N)^2)

思路

观察发现每个方向的步数依次为1,1,2,2,3,3,…,依次类推，按照步骤走即可，发现不在网格内就跳过。

复杂度分析：

虽然输入是矩形，但是走还是按照正方形走。

python 代码

class :
    def spiralMatrixIII(self, R: int, C: int, r0: int, c0: int) -> List[List[int]]:
        res = [[r0, c0]]
        count_turn = 0
        d = 0
        x = r0
        y = c0
        dx = [0, 1, 0, -1]
        dy = [1, 0, -1, 0]
        while len(res) < R * C:
            steps = count_turn // 2 + 1
            for step in range(steps):
                x += dx[d]
                y += dy[d]
                if 0 <= x <= R - 1 and 0 <= y <= C - 1:
                    res.append([x, y])
            count_turn += 1
            d = (d + 1) % 4
        return res

上一篇: LeetCode 498. Diagonal Traverse

下一篇: LeetCode 59. Spiral Matrix II

原文:大专栏 LeetCode 885. Spiral Matrix III

码农公寓