Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

The title

Spiral matrix II:

Given a positive integer n, generate an n x n square matrix matrix containing all elements from 1 to n^2 in a clockwise spiral order.

Example 1: input: n = 3 output: [[1,2,3],[8,9,4],[7,6,5]]

Example 2: Input: n = 1 Output: [[1]]

Tip: 1 <= n <= 20

Copyright belongs to LeetCode. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Answer key

Analysis of the problem solving

Antithesis thought

1. Simulation matrix generation. As required, the initial position is set to the upper left corner of the matrix and the initial orientation is set to the right. If the next position is outside the boundary of the matrix, or a previously visited position, it is rotated clockwise to enter the next direction. Do this until you have n^2 elements.

2. Let matrix be the generated matrix, whose initial elements are set to 0. Since the filled elements are all positive, we can determine the element value of the current location. If it is not 0, it indicates that the location has been accessed.

Complexity analysis

• Time complexity: O(N^2)
• Space complexity: O(1)

The problem solving code

The solution code is as follows (there are detailed notes in the code) :

class Solution {
    public int[][] generateMatrix(int n) {
        int maxNum = n * n;
        int curNum = 1;

        // Helical matrix definition
        int[][] matrix = new int[n][n];
        / / rows and columns
        int row = 0, column = 0;
        int[][] directions = {{0.1}, {1.0}, {0, -1}, {-1.0}};
        int directionIndex = 0;

        // Generate the matrix
        while (curNum <= maxNum) {
            // The upper right corner starts at 1
            matrix[row][column] = curNum;
            // The current value is accumulated
            curNum++;

            // Calculates the position of the next cell
            int nextRow = row + directions[directionIndex][0];
            int nextColumn = column + directions[directionIndex][1];

            // Range judgment
            if (nextRow < 0 || nextRow >= n 
              || nextColumn < 0|| nextColumn >=n || matrix[nextRow][nextColumn] ! =0) {
                
                // Rotate clockwise to the next direction
                directionIndex = (directionIndex + 1) % 4;
            }

            // Go to the next grid
            row = row + directions[directionIndex][0];
            column = column + directions[directionIndex][1];
        }

        / / return
        returnmatrix; }}Copy the code

Feedback results after submission:

The reference information

• Problem 59: Spiral matrix II