Topic describes

This is 59. Spiral matrix II on LeetCode, medium difficulty.

Tag: “Simulation”

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

Example 1:

Input: n = 3 output: [[1,2,3],[8,9,4],[7,6,5]]Copy the code

Example 2:

Input: n = 1 Output: [[1]]Copy the code

Tip:

  • 1 <= n <= 20

Follow the “shape” simulation

We can build in circles.

Use the “top left” (x1,y1)(x1,y1)(x1,y1) (x1,y1) & the “bottom right” (x2,y2)(x2,y2)(x2,y2) to determine a “circle” and build.

When finished, redraw the “upper left corner” and “lower right corner” to get (x1+1,y1+1)(x1 +1,y1+1)(x1 +1,y1+1) and (x2−1,y2−1)(X2-1, y2-1)(x2−1,y2−1), respectively, and execute the same build rules.

Code:

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] ans = new int[n][n];
        circle(0.0, n - 1, n - 1.1, ans);
        return ans;
    }
    void circle(int x1, int y1, int x2, int y2, int start, int[][] ans) {
        if (x2 < x1 || y2 < y1) return ;

        if (x1 == x2) {
            ans[x1][y1] = start;
            return;
        }

        int val = start;
        for (int i = y1; i < y2; i++) ans[x1][i] = val++;
        for (int i = x1; i < x2; i++) ans[i][y2] = val++;
        for (int i = y2; i > y1; i--) ans[x2][i] = val++;
        for (int i = x2; i > x1; i--) ans[i][y1] = val++;

        circle(x1 + 1, y1 + 1, x2 - 1, y2 - 1, val, ans); }}Copy the code
  • O(n2)O(n^2)O(n2)
  • Space complexity: O(n2)O(n^2)O(n2)

Follow the “direction” to simulate

In fact, we can also simulate according to “direction”.

Because each lap is built in a particular “four directions.”

This is a much simpler solution. And the timing of the trigger direction change:

  1. Location overflow occurs next
  2. Back to the beginning of the circle

Code:

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] ans = new int[n][n];
        // Define four directions
        int[][] dirs = new int[] [] {{0.1}, {1.0}, {0, -1}, {-1.0}};
        for (int x = 0, y = 0, d = 0, i = 1; i <= n * n; i++) {
            ans[x][y] = i;

            // The next position to reach
            int nx = x + dirs[d][0], ny = y + dirs[d][1];
            // If the next step is "overflow" or has been accessed (indicating that the four directions have been passed once)
            if (nx < 0 || nx >= n || ny < 0|| ny >= n || ans[nx][ny] ! =0) {
                d = (d + 1) % 4;
                nx = x + dirs[d][0];
                ny = y + dirs[d][1];
            }

            x = nx;
            y = ny;
        }
        returnans; }}Copy the code
  • O(n2)O(n^2)O(n2)
  • Space complexity: O(n2)O(n^2)O(n2)

The last

This is the No.59 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode by the start date, some of which have locks, we will first brush all the topics without locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.