螺旋矩阵 III 图解题解

这道题到底在问什么

输入

rows=1, cols=4, 起点 (0,0)

输出

[[0,0],[0,1],[0,2],[0,3]]

输入

rows=2, cols=2, 起点 (0,0)

输出

[[0,0],[0,1],[1,1],[1,0]]

最优解：一步一步想明白

1. 3记住两根尺子:方向东南西北转圈,步长每两段加一。下面用一张小网格把这两根尺子走一遍。
2. 4真实网格是上面两行 0、1;最下面灰带是「界外」第 2 行看这张图。真正的网格是上面绿框这两行,共 2 行 4 列。最下面一条灰带代表「网格外面」,等会儿螺旋会踩进去。绿色的 (1,1) 是起点,先把它记成答案里的第 1 个。
3. 5每两段方向用同一个步长,之后步长加一先把步长规律记牢。出发先向东走 1 步,再向南走 1 步;然后向西走 2 步,向北走 2 步;接着向东走 3 步,向南走 3 步。就是每两段用同一个步长,走完两段步长就加一。
4. 6向东 第 1/1 步　|　已记录 1 / 8出发了。第一段向东走 1 步,指针落到 (1,2)(橙色)。每走到一格,先问一句:这格在网格里吗?
5. 7(1,2) 在网格内,收进答案　|　已记录 2 / 8(1,2) 的行和列都没越界,在网格里。把它涂绿、记成答案的第 2 个,右边 ans 队伍多了一个坐标。
6. 8向南 第 1/1 步　|　已记录 2 / 8指针沿着南方向迈一步,落到 (2,2)。还是老规矩,先判断它在不在真实网格里。
7. 9(2,2) 越出网格,跳过不记　|　已记录 2 / 8(2,2) 掉到灰带里,也就是网格外面。这一步照样要走,但不能记进答案,所以打个红叉跳过。注意:虽然没记,人还是站在这里继续往前走。
8. 10向西 第 1/2 步　|　已记录 2 / 8指针沿着西方向迈一步,落到 (2,1)。还是老规矩,先判断它在不在真实网格里。
9. 11(2,1) 越出网格,跳过不记　|　已记录 2 / 8(2,1) 又是界外,继续打叉跳过,ans 不变,但脚步不停,接着按规律往下走。
10. 12向西 第 2/2 步　|　已记录 2 / 8指针沿着西方向迈一步,落到 (2,0)。还是老规矩,先判断它在不在真实网格里。
11. 13(2,0) 越出网格,跳过不记　|　已记录 2 / 8(2,0) 又是界外,继续打叉跳过,ans 不变,但脚步不停,接着按规律往下走。
12. 14向北 第 1/2 步　|　已记录 2 / 8指针沿着北方向迈一步,落到 (1,0)。还是老规矩,先判断它在不在真实网格里。
13. 15(1,0) 在网格内,收进答案　|　已记录 3 / 8(1,0) 的行和列都没越界,在网格里。把它涂绿、记成答案的第 3 个,右边 ans 队伍多了一个坐标。
14. 16向北 第 2/2 步　|　已记录 3 / 8指针沿着北方向迈一步,落到 (0,0)。还是老规矩,先判断它在不在真实网格里。
15. 17(0,0) 在网格内,收进答案　|　已记录 4 / 8(0,0) 同样在界内,收进答案,成为第 4 个。
16. 18向东 第 1/3 步　|　已记录 4 / 8指针沿着东方向迈一步,落到 (0,1)。还是老规矩,先判断它在不在真实网格里。
17. 19(0,1) 在网格内,收进答案　|　已记录 5 / 8(0,1) 同样在界内,收进答案,成为第 5 个。
18. 20向东 第 2/3 步　|　已记录 5 / 8指针沿着东方向迈一步,落到 (0,2)。还是老规矩,先判断它在不在真实网格里。
19. 21(0,2) 在网格内,收进答案　|　已记录 6 / 8(0,2) 同样在界内,收进答案,成为第 6 个。
20. 22向东 第 3/3 步　|　已记录 6 / 8指针沿着东方向迈一步,落到 (0,3)。还是老规矩,先判断它在不在真实网格里。
21. 23(0,3) 在网格内,收进答案　|　已记录 7 / 8(0,3) 同样在界内,收进答案,成为第 7 个。
22. 24向南 第 1/3 步　|　已记录 7 / 8指针沿着南方向迈一步,落到 (1,3)。还是老规矩,先判断它在不在真实网格里。
23. 25(1,3) 在网格内,收进答案　|　已记录 8 / 8(1,3) 同样在界内,收进答案,成为第 8 个。
24. 26全部 8 格按螺旋顺序记齐,任务结束当记录数等于网格总格数 8,就说明全走遍了,立刻收工。右边 ans 这一长串坐标,正是按螺旋访问顺序排好的最终答案。中间踩进灰带的那几步,一个都没混进来。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def spiralMatrixIII(
        self, rows: int, cols: int, rStart: int, cStart: int
    ) -> List[List[int]]:
        ans = [[rStart, cStart]]
        if rows * cols == 1:
            return ans
        k = 1
        while True:
            for dr, dc, dk in [[0, 1, k], [1, 0, k], [0, -1, k + 1], [-1, 0, k + 1]]:
                for _ in range(dk):
                    rStart += dr
                    cStart += dc
                    if 0 <= rStart < rows and 0 <= cStart < cols:
                        ans.append([rStart, cStart])
                        if len(ans) == rows * cols:
                            return ans
            k += 2

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    vector<vector<int>> spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
        int cnt = rows * cols;
        vector<vector<int>> ans;
        ans.push_back({rStart, cStart});
        if (cnt == 1) return ans;
        for (int k = 1;; k += 2) {
            vector<vector<int>> dirs = {{0, 1, k}, {1, 0, k}, {0, -1, k + 1}, {-1, 0, k + 1}};
            for (auto& dir : dirs) {
                int r = dir[0], c = dir[1], dk = dir[2];
                while (dk-- > 0) {
                    rStart += r;
                    cStart += c;
                    if (rStart >= 0 && rStart < rows && cStart >= 0 && cStart < cols) {
                        ans.push_back({rStart, cStart});
                        if (ans.size() == cnt) return ans;
                    }
                }
            }
        }
    }
};

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public int[][] spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
        int cnt = rows * cols;
        int[][] ans = new int[cnt][2];
        ans[0] = new int[] {rStart, cStart};
        if (cnt == 1) {
            return ans;
        }
        for (int k = 1, idx = 1;; k += 2) {
            int[][] dirs = new int[][] {{0, 1, k}, {1, 0, k}, {0, -1, k + 1}, {-1, 0, k + 1}};
            for (int[] dir : dirs) {
                int r = dir[0], c = dir[1], dk = dir[2];
                while (dk-- > 0) {
                    rStart += r;
                    cStart += c;
                    if (rStart >= 0 && rStart < rows && cStart >= 0 && cStart < cols) {
                        ans[idx++] = new int[] {rStart, cStart};
                        if (idx == cnt) {
                            return ans;
                        }
                    }
                }
            }
        }
    }
}

复杂度

面试官可能追问