Item 59. Spiral matrix II Given a positive integer n, generate a square matrix containing all elements from 1 to n2 in a clockwise spiral order.

Example:

Input: 3 output: [[1, 2, 3], [8, 9, 4], [7, 6, 5]]

The topic of thinking can be said to be a topic with high frequency in the interview. “This topic does not involve any algorithm, but it is a simulation process, but it is very concerned with the ability to control the code.”

How do you draw this spiral square matrix?

I believe that many students just started to do this kind of problem, is a wave of judgment fierce as a tiger.

You end up having all sorts of problems with it, and then you start tinkering with it, and then you figure out what’s wrong with it, what’s wrong with it, and it doesn’t work.

You’ll remember that we talked about dichotomy in this article array: Every Time you see a dichotomy, you have to stick to the “circular invariant principle” if you want to write a dichotomy correctly.

And again, we have to stick to the circular invariants.

Simulate the process of drawing a matrix clockwise:

Fill up, left to right, right column, top to bottom, down column, right to left, bottom to top

I’m going to go around and around from the outside in.

It can be found that there are a lot of boundary conditions here. In a cycle, there are so many boundary conditions that if they are not traversed according to fixed rules, it is “once entering the cycle, offer is as deep as the sea”.

In this circle, we should draw four sides, how to draw the four sides, each side should adhere to the same principle of left closed and right open, or left open and closed again, so that the circle can be drawn in accordance with a uniform rule.

So let me draw a circle according to the principle of left closed and right open. Let’s see:

So each of these colors represents an edge, and the length that we’re going to traverse, and you can see the rule for each corner, and then you give the corner to a new edge.

This is also to adhere to the principle of each edge closed left open right.

Some students have been doing this problem is not good, the code is more and more messy.

The reason is that when you draw each edge, you can open and close it on the left, close it on the right, and open it on the left.

The code is as follows, and the purpose of each step has been annotated in detail. It can be seen that there are many cases to judge in the while loop, and the principle of processing in the code is the same: close left and open right.

public class Solution { public int[][] generateMatrix(int n) { int[][] res = new int[n][n]; Int count = 1; // int offset = 1 for each space in the matrix; Int loopCount = n / 2; int loopCount = n / 2; Int mid = n / 2; int mid = n / 2; int mid = n / 2; Int startX = 0; int startX = 0; int startX = 0; // define the starting position of each circle int startY = 0; int i = 0; int j = 0;while (loopCount > 0) {
            for (j = startY; j < startY + n - offset; j++) {
                res[startX][j] = count;
                count++;
            }

            for (i = startX; i < startX + n - offset; i++) {
                res[i][j] = count;
                count++;
            }

            for (; j > startY; j--) {
                res[i][j] = count;
                count++;
            }

            for(; i > startX; i--) { res[i][j] = count; count++; } // at the beginning of the second lap, the starting position of the first lap is (0, 0), the starting position of the second lap is (1, 1) startX++; startY++; offset = offset + 2; // offset controls the length of each edge in each circle loopCount--; } // If n is odd, the middle-most position of the matrix should be assigned separatelyif (n % 2 == 1) {
            res[mid][mid] = count;
        }
        returnres; }}Copy the code

You can also set int count=0, just count++, and then set the res array, and then set the odd column

public class Solution { public int[][] generateMatrix(int n) { int[][] res = new int[n][n]; Int count = 0; // int offset = 1 for each space in the matrix; Int loopCount = n / 2; int loopCount = n / 2; Int mid = n / 2; int mid = n / 2; int mid = n / 2; Int startX = 0; int startX = 0; int startX = 0; // define the starting position of each circle int startY = 0; int i = 0; int j = 0;while (loopCount > 0) {
            
            for(j = startY; j < startY + n - offset; j++) { count++; res[startX][j] = count; // use startX, I}for (i = startX; i < startX + n - offset; i++) {
                count++;
                res[i][j] = count;
            }

            for (; j > startY; j--) {
                count++;
                res[i][j] = count;
            }

            for(; i > startX; i--) { count++; res[i][j] = count; } // at the beginning of the second lap, the starting position of the first lap is (0, 0), the starting position of the second lap is (1, 1) startX++; startY++; offset = offset + 2; // offset controls the length of each edge in each circle loopCount--; } // If n is odd, the middle-most position of the matrix should be assigned separatelyif (n % 2 == 1) {
            count++;
            res[mid][mid] = count;
        }
        returnres; }}Copy the code

Note: the offset variable must be present. Do not remove it, because the j < startY + n-offset in the first for loop cannot be changed to j < n-starty.