Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

📃

59. Spiral Matrix II – Force buckle (LeetCode) (leetcode-cn.com)

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]]Copy the code

Example 2:

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

🔔

In this case, there is no algorithm idea at all. The main idea is to assign values to the array in a spiral order. The difficulty lies in the processing of the boundary.

This idea of solving the problem step by step in accordance with the process, which seems to have no routine, is also called “simulation method”.

The four directions of the clockwise spiral:

  • From left to right
  • From top to bottom
  • From right to left
  • From the bottom up

The specific process we do not complete the text, directly look at the picture to understand:

class Solution { public int[][] generateMatrix(int n) { int[][] res = new int[n][n]; Int left = 0; Int right = n-1; Int up = 0; Int bottom = n - 1; Int curNum = 1; While (curNum <= n * n) {// for (int j = left; j <= right; j++) { res[up][j] = curNum++; } up++; For (int j = up; int j = up; j <= bottom; j++) { res[j][right] = curNum++; } right--; For (int j = right; int j = right; j >= left; j--) { res[bottom][j] = curNum++; } bottom--; For (int j = bottom; j >= up; j--) { res[j][left] = curNum++; } left++; } return res; }}Copy the code

This solution also applies directly to this problem, which is basically the same: 54. Spiral Matrix-force buckle (LeetCode) (leetcode-cn.com)

There’s another solution that’s easier to write:

class Solution { public int[][] generateMatrix(int n) { int[][] res = new int[n][n]; / / four directions: right upper left int [] [] directions = {{0, 1}, {1, 0}, {0, 1}, {1, 0}}; // specify which direction int directionIndex = 0; Int curNum = 1; Int maxNum = n * n; Int row = 0; Int column = 0; While (curNum <= maxNum) {// Fill a number res[row][column] = curNum; curNum ++; Int nextRow = row + Directions [directionIndex][0]; int nextColumn = column + directions[directionIndex][1]; if (nextRow < 0 || nextRow >= n || nextColumn < 0 || nextColumn >= n || res[nextRow][nextColumn] ! = 0) { directionIndex = (directionIndex + 1) % 4; } row = row + Directions [directionIndex][0]; column = column + directions[directionIndex][1]; } return res; }}Copy the code

💥 Complexity analysis

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

If you are like me, you always worry about the order and system of the test, and eventually give up halfway, you can see here: LeetCode + Jianfinger Offer = 💰, the blogger is currently studying for a master’s degree in Southeast University, and is also preparing for autumn recruitment. Everyone can come here to swipe questions and punch cards together every day

My public account “Flying Veal” focuses on sharing original technical articles related to computer foundation (data structure + algorithm + computer network + database + operating system + Linux) and Java technology stack. Attention to the public account for the first time to get the article update, the background reply 300 can be free to get the Geek University produced Java interview 300 questions, Echo to receive free star 1K + community project supporting tutorials