Array - 59. Spiral matrix II

1 Title Description

59. Spiral matrix II

Give you a positive integer n , Generate a include 1 To n2 All the elements , And the elements are arranged in a clockwise spiral order n x n square matrix matrix .

2 Title Example

Input ：n = 3
Output ：[[1,2,3],[8,9,4],[7,6,5]]

Example 2：

Input ：n = 1
Output ：[[1]]

3 Topic tips

• 1 <= n <= 20

4 Ideas

This question does not involve any algorithm , Is the simulation process , But they are very concerned about the ability to control the code .
Simulate the process of drawing a matrix clockwise :

Fill up from left to right
Fill in the right column from top to bottom
Fill down from right to left
Fill in the left column from bottom to top
From outside to inside, circle by circle .
Each side should be consistently closed to the left and opened to the right , Or the principle of opening left and closing right , In this way, the circle can be drawn according to the unified rules .

5 My answer

class Solution {
    
    public int[][] generateMatrix(int n) {
    
        int loop = 0;  //  Control the number of cycles 
        int[][] res = new int[n][n];
        int start = 0;  //  Starting point of each cycle (start, start)
        int count = 1;  //  Define padding numbers 
        int i, j;

        while (loop++ < n / 2) {
     //  After judging the boundary ,loop from 1 Start 
            //  Simulate the upper side from left to right 
            for (j = start; j < n - loop; j++) {
    
                res[start][j] = count++;
            }

            //  Simulate the right side from top to bottom 
            for (i = start; i < n - loop; i++) {
    
                res[i][j] = count++;
            }

            //  Simulate the lower side from right to left 
            for (; j >= loop; j--) {
    
                res[i][j] = count++;
            }

            //  Simulate the left side from bottom to top 
            for (; i >= loop; i--) {
    
                res[i][j] = count++;
            }
            start++;
        }

        if (n % 2 == 1) {
    
            res[start][start] = count;
        }

        return res;
    }
}

C++ Code ：
This paragraph is quoted from the code Capriccio
Spiral matrix II

class Solution {
    
public:
    vector<vector<int>> generateMatrix(int n) {
    
        vector<vector<int>> res(n, vector<int>(n, 0)); //  Use vector Define a two-dimensional array 
        int startx = 0, starty = 0; //  Define the starting position of each cycle 
        int loop = n / 2; //  How many times per cycle , for example n It's odd 3, that loop = 1  Just a cycle , The values in the middle of the matrix need to be treated separately 
        int mid = n / 2; //  In the middle of the matrix , for example ：n by 3,  The middle position is (1,1),n by 5, The middle position is (2, 2)
        int count = 1; //  Used to assign a value to each space in the matrix 
        int offset = 1; //  You need to control the length of each edge traversal , The right boundary of each cycle shrinks by one digit 
        int i,j;
        while (loop --) {
    
            i = startx;
            j = starty;

            //  The following four for It's a simulation turn 
            //  Analog fill uplink from left to right ( Left closed right away )
            for (j = starty; j < n - offset; j++) {
    
                res[startx][j] = count++;
            }
            //  The simulation fills the right column from top to bottom ( Left closed right away )
            for (i = startx; i < n - offset; i++) {
    
                res[i][j] = count++;
            }
            //  The simulation fills down from right to left ( Left closed right away )
            for (; j > starty; j--) {
    
                res[i][j] = count++;
            }
            //  Simulate filling the left column from bottom to top ( Left closed right away )
            for (; i > startx; i--) {
    
                res[i][j] = count++;
            }

            //  At the beginning of the second lap , The starting position shall be added with 1,  for example ： The starting position of the first circle is (0, 0), The starting position of the second circle is (1, 1)
            startx++;
            starty++;

            // offset  Control the length of each edge traversal in each circle 
            offset += 1;
        }

        //  If n For an odd number , You need to assign a separate value to the middle of the matrix 
        if (n % 2) {
    
            res[mid][mid] = count;
        }
        return res;
    }
};

Similar topics ：

54. Spiral matrix
    To give you one m That's ok n Columns of the matrix matrix , Please follow Clockwise spiral sequence , Returns all elements in the matrix .
    

Tips ：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100

For this spiral traversal method , The important thing is to determine the position of the upper, lower, left and right sides , So when initializing , above up Namely 0, Underside down Namely m-1, On the left left yes 0, On the right right yes n-1. And then we do while loop , Traverse the upper edge first , Add all elements to the result res, Then move one position up and down , If the upper side is larger than the lower side , It indicates that the traversal has been completed at this time , direct break.

class Solution {
    
    public List<Integer> spiralOrder(int[][] matrix) {
    
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return new LinkedList<>();
        int l = 0;
        int r = matrix[0].length - 1;
        int u = 0;
        int d = matrix.length - 1;
        List<Integer> list = new LinkedList<>();
        while (l <= r && u <= d){
    
            for (int i = l; i <= r; i++) {
    
                list.add(matrix[u][i]);
            }
            u++;
            for (int i = u; i <= d; i++) {
    
                list.add(matrix[i][r]);
            }
            r--;
            for (int i = r; i >= l && u <= d; i--) {
    
                list.add(matrix[d][i]);
            }
            d--;
            for (int i = d; i >= u && l <= r; i--) {
    
                list.add(matrix[i][l]);
            }
            l++;
        }
        return list;                      
    }
}