2326. Spiral Matrix IV
Difficulty: Medium
Topics: Array, Linked List, Matrix, Simulation
You are given two integers m and n, which represent the dimensions of a matrix.
You are also given the head of a linked list of integers.
Generate an m x n matrix that contains the integers in the linked list presented in spiral order (clockwise), starting from the top-left of the matrix. If there are remaining empty spaces, fill them with -1.
Return the generated matrix.
Example 1:
Example 2:
Example 3:
Constraints:
Hint:
Solution:
We will simulate a spiral traversal of an m x n matrix, filling it with values from a linked list. The remaining positions that don't have corresponding linked list values will be filled with -1.
Here's how the solution is structured:
Let's implement this solution in PHP: 2326. Spiral Matrix IV
val = $val; $this->next = $next; } } /** * @param Integer $m * @param Integer $n * @param ListNode $head * @return Integer[][] */ function spiralMatrix($m, $n, $head) { ... ... ... /** * go to ./solution.php */ } // Helper function to print the matrix (for debugging) function printMatrix($matrix) { foreach ($matrix as $row) { echo implode(" ", $row) . "\n"; } } // Example usage: // Create the linked list: [3,0,2,6,8,1,7,9,4,2,5,5,0] $head = new ListNode(3); $head->next = new ListNode(0); $head->next->next = new ListNode(2); $head->next->next->next = new ListNode(6); $head->next->next->next->next = new ListNode(8); $head->next->next->next->next->next = new ListNode(1); $head->next->next->next->next->next->next = new ListNode(7); $head->next->next->next->next->next->next->next = new ListNode(9); $head->next->next->next->next->next->next->next->next = new ListNode(4); $head->next->next->next->next->next->next->next->next->next = new ListNode(2); $head->next->next->next->next->next->next->next->next->next->next = new ListNode(5); $head->next->next->next->next->next->next->next->next->next->next->next = new ListNode(5); $head->next->next->next->next->next->next->next->next->next->next->next->next = new ListNode(0); $m = 3; $n = 5; $matrix = spiralMatrix($m, $n, $head); printMatrix($matrix); ?>Explanation:
Matrix Initialization: The matrix is initialized with -1 so that any unfilled spaces will remain -1 by default.
Spiral Movement:
- The direction vector dirs manages movement in four directions: right, down, left, and up.
- The index dirIndex keeps track of the current direction. After moving in one direction, we calculate the next position and check if it's valid. If not, we change the direction.
Linked List Traversal:
- We traverse through the linked list nodes, placing values in the matrix one by one, following the spiral order.
Boundary and Direction Change:
- When we encounter an invalid position (out of bounds or already filled), we rotate the direction by 90 degrees (i.e., change the direction vector).
Time Complexity:
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
The above is the detailed content of Spiral Matrix IV. For more information, please follow other related articles on the PHP Chinese website!