Shulou(Shulou.com)06/03 Report--

This article will explain in detail the written test questions about bytes and the example analysis of algorithm questions. The content of the article is of high quality, so the editor will share it with you for reference. I hope you will have a certain understanding of the relevant knowledge after reading this article.

Given a matrix of m x n elements (m rows, n columns), please return all the elements in the matrix in clockwise spiral order.

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

Basically, the idea is to deal with layers inward, traversing clockwise: top, right, bottom, and left.

In fact, it is very similar to the way of the maze, after walking to the grid, to judge whether the next grid can still walk, that is, the boundary conditions. When you encounter the boundary conditions, follow the above order: top, right, bottom, left.

So we can have several constraints:

Whether it is within this range or not, it cannot exceed these ranges.

Does this grid walk through and save the previous state?

It is right to record the current direction and hold the next direction.

Depth first traversal

Following the depth-first traversal approach, we can construct common dfs templates:

Const spiralOrder = function (matrix) {if (matrix.length = 0) return []; const result = [], dx = [0,1,0,-1], dy = [1,0,-1,0], col = matrix.length, row = matrix [0] .length / / isCheckMatrix record whether to go through const isCheckMatrix = Array.from (new Array (col), () = > (new Array (row) .fill (false)) const dfs = (x, y, directionIndex) = > {/ / logic code / / usually logic processing, boundary processing}}; dfs (0,0,0); return result}

This should be the basic template, the only difference is that we look at the three parameters of dfs, XMagneyDirectionIndex.

The x and y parameters are easy to understand, and the meaning of this directionIndex parameter is to tell us the current way forward.

The next step is to write our logic. First determine which grid to go to next:

Dx = [0,1,0,-1] dy = [1,0,1,0] const nextX = x + dx [directionIndex] const nextY = y + dy [directionIndex]

According to the location of the current grid, we know where to go next, and through the subscript index of directionIndex, we know the coordinates of our next grid.

Then it is to judge the situation of the boundary:

Can't go out of bounds.

Judge whether you can go or not.

According to the above information, in fact, our main logical part is completed.

Code: const spiralOrder = function (matrix) {if (matrix.length = 0) return []; const result = [], dx = [0,1,0,-1], dy = [1,0,-1,0], col = matrix.length, row = matrix [0] .length Const isCheckMatrix = Array.from (new Array (col), () = > (new Array (row) .fill (false)) const dfs = (x, y, directionIndex) = > {result.push (Matrix [x] [y]) / save the answer isCheckMatrix [x] [y] = true / / Mark through for (let I = 0; I

< 3; i++) { const nextX = x + dx[directionIndex] const nextY = y + dy[directionIndex] // 判断边界 if (nextX < col && nextX >

= 0 & & nextY

< row && nextY >

= 0 & &! isCheckMatrix [nextX] [nextY]) {dfs (nextX, nextY, directionIndex)} / / take the remainder directionIndex = (directionIndex + 1)% 4;}}; dfs (0,0,0); return result}

Here we need each other to do the remainder. When there are only four directions, and if you can't go in that direction, try the next direction.

DirectionIndex = (directionIndex + 1)% 4; optimize

When I finished writing, I was wondering if I could optimize it and do a branch reduction treatment. Later, I found that if the current position could be taken, it would not be possible to judge other directions.

Or we can get out of this cycle ahead of time, and the optimization here is the current processing of return.

Code: const spiralOrder = function (matrix) {if (matrix.length = 0) return []; const result = [], dx = [0,1,0,-1], dy = [1,0,-1,0], col = matrix.length, row = matrix [0] .length Const isCheckMatrix = Array.from (new Array (col), () = > (new Array (row) .fill (false)) const dfs = (x, y, directionIndex) = > {result.push (Matrix [x] [y]); isCheckMatrix [x] [y] = true for (let I = 0; I

< 3; i++) { const nextX = x + dx[directionIndex] const nextY = y + dy[directionIndex] if (nextX < col && nextX >

= 0 & & nextY

< row && nextY >

= 0 & &! isCheckMatrix [nextX] [nextY]) {return dfs (nextX, nextY, directionIndex)} directionIndex = (directionIndex + 1)% 4;}; dfs (0,0,0); return result} This is the end of the sample analysis of the written test questions and algorithm questions about bytes. I hope the above content can be helpful to everyone and learn more knowledge. If you think the article is good, you can share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.