螺旋矩阵 IV 图解题解

这道题到底在问什么

输入

m=3, n=4, head=[3,7,1,9,4,8,2,6]

输出

[[3,7,1,9],[-1,-1,-1,4],[-1,6,2,8]]

输入

m=1, n=4, head=[0,1,2]

输出

[[0,1,2,-1]]

最优解：一步一步想明白

1. 3记牢这一句:走不走得动,只看下一格是不是「界内且还是 -1」。是就走,不是就顺时针转向。这一条判断,既管住了拐弯,也顺手把剩余格子留成了 -1。下面从左上角开始一步步走。
2. 4整张矩阵先铺成 -1开工前先把整张 3 乘 4 的矩阵在心里铺成 -1,舞台上没写过的格子先用一个点占位。指针停在左上角 (0,0),初始方向是向右。侧栏那一列 3、7、1、9、4、8、2、6,就是链表从头到尾要写进来的 8 个值。准备好了,开始沿螺旋往里填。
3. 5第 1 个值落格第一步最简单:直接在起点 (0,0) 写下链表头的值 3,这一格变成紫色表示刚写。链表指针往后挪一位,侧栏顶上的 3 划走了。接着要决定下一格往哪儿走。
4. 6下一格畅通,继续直行站在刚写完的这一格,判断下一步。朝向右探一格,下一格 (0,1) 在界内、而且还是 -1,没填过,直接迈过去。
5. 7第 2 个值落格把链表当前值 7 写进 (0,1),这一格点亮成紫色,之前写过的格子退成蓝色。链表再往后一位,侧栏又少一个值。现在已经写满 2 个格子。
6. 8下一格畅通,继续直行站在刚写完的这一格,判断下一步。朝向右探一格,下一格 (0,2) 在界内、而且还是 -1,没填过,直接迈过去。
7. 9第 3 个值落格把链表当前值 1 写进 (0,2),这一格点亮成紫色,之前写过的格子退成蓝色。链表再往后一位,侧栏又少一个值。现在已经写满 3 个格子。
8. 10下一格畅通,继续直行站在刚写完的这一格,判断下一步。朝向右探一格,下一格 (0,3) 在界内、而且还是 -1,没填过,直接迈过去。
9. 11第 4 个值落格把链表当前值 9 写进 (0,3),这一格点亮成紫色,之前写过的格子退成蓝色。链表再往后一位,侧栏又少一个值。现在已经写满 4 个格子。
10. 12下一格越界或已填,顺时针转向站在刚写完的这一格,判断下一步。朝向右探一格会走出矩阵,于是顺时针转到向下,探到 (1,3) 在界内又还是 -1,迈过去。 注意转向不是数着走了几步才拐,而是探到走不动的那一刻才拐,这样非方形矩阵也不会算错。
11. 13第 5 个值落格把链表当前值 4 写进 (1,3),这一格点亮成紫色,之前写过的格子退成蓝色。链表再往后一位,侧栏又少一个值。现在已经写满 5 个格子。
12. 14下一格畅通,继续直行站在刚写完的这一格,判断下一步。朝向下探一格,下一格 (2,3) 在界内、而且还是 -1,没填过,直接迈过去。
13. 15第 6 个值落格把链表当前值 8 写进 (2,3),这一格点亮成紫色,之前写过的格子退成蓝色。链表再往后一位,侧栏又少一个值。现在已经写满 6 个格子。
14. 16下一格越界或已填,顺时针转向站在刚写完的这一格,判断下一步。朝向下探一格会走出矩阵,于是顺时针转到向左,探到 (2,2) 在界内又还是 -1,迈过去。 注意转向不是数着走了几步才拐,而是探到走不动的那一刻才拐,这样非方形矩阵也不会算错。
15. 17第 7 个值落格把链表当前值 2 写进 (2,2),这一格点亮成紫色,之前写过的格子退成蓝色。链表再往后一位,侧栏又少一个值。现在已经写满 7 个格子。
16. 18下一格畅通,继续直行站在刚写完的这一格,判断下一步。朝向左探一格,下一格 (2,1) 在界内、而且还是 -1,没填过,直接迈过去。
17. 19第 8 个值落格把链表当前值 6 写进 (2,1),这一格点亮成紫色,之前写过的格子退成蓝色。链表再往后一位,侧栏又少一个值。现在已经写满 8 个格子。
18. 208 个值全部落格链表的 8 个值全部写完,侧栏空了。螺旋才走到 (2,1) 就停在了半路,根本没绕回中间。矩阵一共 12 格,只写了 8 格,还剩下 4 格从头到尾没人碰过。这 4 个空格该怎么办,下一步见分晓。
19. 21未被螺旋覆盖的格子把还显示点的空格挑出来看:(1,0)、(1,1)、(1,2)、(2,0),这 4 个格子链表没走到。它们正好卡在螺旋还没绕进去的中间地带。因为一开始整张矩阵就是 -1,这些格子其实一直安安静静地保持着 -1,我们什么都不用额外做。
20. 224 个空格写上 -1现在把那 4 个空格的真面目亮出来:它们都是 -1,刷成浅蓝。这一步其实没做任何新动作,只是把「一开始就铺好的 -1」显示出来而已。这正是先整张铺 -1 的妙处:剩余格子天然就是 -1,省得最后再回头补。到此,12 个格子全部有值。
21. 23答案 [[3,7,1,9],[-1,-1,-1,4],[-1,6,2,8]]回放一遍全程。绿色是链表螺旋填出来的 8 个值:先沿第一行 3、7、1、9 向右,撞墙转下走 4、8,再转左走 2、6,链表就空了。浅蓝的 4 个 -1 是没被螺旋绕到的空位。合起来就是最终答案:第一行 3、7、1、9,第二行 -1、-1、-1、4,第三行 -1、6、2、8。

⚠️ 容易写错的地方

完整代码（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 *
from string import *
from operator 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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:
        ans = [[-1] * n for _ in range(m)]
        i = j = k = 0
        dirs = (0, 1, 0, -1, 0)
        while 1:
            ans[i][j] = head.val
            head = head.next
            if head is None:
                break
            while 1:
                x, y = i + dirs[k], j + dirs[k + 1]
                if 0 <= x < m and 0 <= y < n and ans[x][y] == -1:
                    i, j = x, y
                    break
                k = (k + 1) % 4
        return ans

#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) {}
};
/**
 * Definition for singly-linked list.
 * 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>> spiralMatrix(int m, int n, ListNode* head) {
        vector<vector<int>> ans(m, vector<int>(n, -1));
        int i = 0, j = 0, k = 0;
        const int dirs[5] = {0, 1, 0, -1, 0};
        while (1) {
            ans[i][j] = head->val;
            head = head->next;
            if (!head) {
                break;
            }
            while (1) {
                int x = i + dirs[k], y = j + dirs[k + 1];
                if (x >= 0 && x < m && y >= 0 && y < n && ans[x][y] == -1) {
                    i = x;
                    j = y;
                    break;
                }
                k = (k + 1) % 4;
            }
        }
        return ans;
    }
};

import java.util.*;
/**
 * Definition for singly-linked list.
 * public 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 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[][] spiralMatrix(int m, int n, ListNode head) {
        int[][] ans = new int[m][n];
        for (int[] row : ans) {
            Arrays.fill(row, -1);
        }
        int i = 0, j = 0, k = 0;
        final int[] dirs = {0, 1, 0, -1, 0};
        while (true) {
            ans[i][j] = head.val;
            head = head.next;
            if (head == null) {
                break;
            }
            while (true) {
                int x = i + dirs[k], y = j + dirs[k + 1];
                if (x >= 0 && x < m && y >= 0 && y < n && ans[x][y] == -1) {
                    i = x;
                    j = y;
                    break;
                }
                k = (k + 1) % 4;
            }
        }
        return ans;
    }
}

复杂度

面试官可能追问