| comments | difficulty | edit_url | rating | source | tags | ||||
|---|---|---|---|---|---|---|---|---|---|
true |
中等 |
1421 |
第 300 场周赛 Q2 |
|
给你两个整数：m 和 n ，表示矩阵的维数。
另给你一个整数链表的头节点 head 。
请你生成一个大小为 m x n 的螺旋矩阵，矩阵包含链表中的所有整数。链表中的整数从矩阵 左上角 开始、顺时针 按 螺旋 顺序填充。如果还存在剩余的空格，则用 -1 填充。
返回生成的矩阵。
示例 1：
输入：m = 3, n = 5, head = [3,0,2,6,8,1,7,9,4,2,5,5,0] 输出：[[3,0,2,6,8],[5,0,-1,-1,1],[5,2,4,9,7]] 解释：上图展示了链表中的整数在矩阵中是如何排布的。 注意，矩阵中剩下的空格用 -1 填充。
示例 2：
输入：m = 1, n = 4, head = [0,1,2] 输出：[[0,1,2,-1]] 解释：上图展示了链表中的整数在矩阵中是如何从左到右排布的。 注意，矩阵中剩下的空格用 -1 填充。
提示：
1 <= m, n <= 1051 <= m * n <= 105- 链表中节点数目在范围
[1, m * n]内 0 <= Node.val <= 1000
我们定义一个二维数组
然后我们开始遍历链表，每次遍历一个节点，就将当前节点的值填充到
否则，我们需要找到下一个元素的位置，我们可以通过当前位置
遍历完链表之后，我们就得到了一个螺旋矩阵，返回即可。
时间复杂度
# 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/**
* 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 Solution {
public int[][] spiralMatrix(int m, int n, ListNode head) {
int[][] ans = new int[m][n];
for (var 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;
}
}/**
* 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;
}
};/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func spiralMatrix(m int, n int, head *ListNode) [][]int {
ans := make([][]int, m)
for i := range ans {
ans[i] = make([]int, n)
for j := range ans[i] {
ans[i][j] = -1
}
}
i, j, k := 0, 0, 0
dirs := [5]int{0, 1, 0, -1, 0}
for {
ans[i][j] = head.Val
if head = head.Next; head == nil {
break
}
for {
x, y := i+dirs[k], j+dirs[k+1]
if x >= 0 && x < m && y >= 0 && y < n && ans[x][y] == -1 {
i, j = x, y
break
}
k = (k + 1) % 4
}
}
return ans
}/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function spiralMatrix(m: number, n: number, head: ListNode | null): number[][] {
const ans: number[][] = Array.from({ length: m }, () => Array(n).fill(-1));
const dirs: number[] = [0, 1, 0, -1, 0];
let [i, j, k] = [0, 0, 0];
while (1) {
ans[i][j] = head.val;
head = head.next;
if (!head) {
break;
}
while (1) {
const [x, y] = [i + dirs[k], 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;
}