This is the fourth day of my participation in the August More text Challenge. For details, see: August More Text Challenge

preface

About the LeetCode array type problem related solutions, it can be seen that LeetCode array type problem before doing must see, classification solution summarized the problem, can be used to improve a single. If you think it is helpful, remember to give more likes and attention, thank you!

Topic describes

I give you a positive integer n, and I generate an n x N square matrix consisting of all the elements from 1 to N2, with the elements spiraling clockwise.

Example 1:



Enter n = 3

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

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

Link: leetcode-cn.com/problems/sp…

Answer key

This question is similar to Leetcode 54, except that while 54 asks you to walk the matrix clockwise, this question asks you to fill the array clockwise. In fact, there is no difference in approach. The main points are as follows:

  1. Define an array of directions. Since it is traversed clockwise, there are four directions, left to right, top to bottom, right to left, and bottom to top. The corresponding direction array is [[0, 1], [1, 0], [0, -1], [-1, 0], [-1, 0]], We also use a variable dirIndex to indicate where we are going.

  2. Define four boundaries, top, bottom, left, and right. These four boundaries are used to prevent the boundary from being crossed when traversing clockwise. When the boundary is approached in one direction, the direction of progress should be changed, that is, the value of dirIndex should be changed and the value of dirIndex should be increased by 1. So I’m going to shorten the top boundary down.

  3. Use the variable now to represent the filled number, traversing clockwise if now <= n * n

Specific code implementation see the following code, according to the code to compare the above three important points, realize the significance of these variables.

O(n ^ 2) in time, O(1) in space.

/ * * *@param {number} n
 * @return {number[][]}* /
var generateMatrix = function(n) {
    let dir = [[0.1], [1.0], [0, -1], [...1.0]]
    let dirIndex = 0
    let res = Array.from({length: n}, () = > (new Array(n)))
    let now = 1
    let top = left = 0
    let bottom = right = n - 1
    let x = y = 0
    while(now <= n * n) {
      res[x][y] = now
      if (y === right && dirIndex === 0) {
        ++top
        ++dirIndex
      } else if (x === bottom && dirIndex === 1) {
        --right
        ++dirIndex
      } else if (y === left && dirIndex === 2) {
        --bottom
        ++dirIndex
      } else if (x === top && dirIndex === 3) {
        ++left
        ++dirIndex
      }
      dirIndex %= 4
      x += dir[dirIndex][0]
      y += dir[dirIndex][1]
      ++now
    }
 return res
};
Copy the code