This article originated from personal public account: TechFlow, original is not easy, for attention
Today is the 32nd article of LeetCode, and we are going to look at LeetCode’s number 54 — Spiral Matrix.
First of all, Spiral means Spiral. It is said that Naruto’s Spiral pill is translated into Spiral Sphere in the English version of the manga.
Gone, back to business. We all know what a spiral means by the spiral pill, so the so-called spiral matrix, is to traverse an array, or matrix, in the order of the spiral. We can take a look at the following image:
The order of the arrows is the order of the helices, and what they want to figure out is the result of traversing the helices.
background
The meaning of this problem is very simple, I think we can certainly understand, but really start to do it will find it is quite difficult. The main difficulty is that the order of our traversal is constantly changing, and the speed of change is also changing. To some extent, these changes are documented, but even so, abstracting these patterns into easy-to-understand bug-free code is not an easy task.
If I remember correctly, when I was a sophomore, there was a question in the ACM competition, exactly the same original question. Although it is very simple and everyone knows how to do it, the final pass rate is not high.
This is not entirely the subject of malicious, in fact, this kind of problem in the ACM competition or very common. There are often questions that are so clear that you just have to follow them. Although the question is not difficult, it is still very difficult to quickly write a program containing hundreds of lines of complex logic without bugs in the high-pressure scene of the competition. Because the key to this kind of question is to let us simulate the meaning of the question, so it is also called the simulation question.
To write this problem smoothly, you need a very common technique or convention, which is the key to this article.
The direction of the array
Among many problems, we often encounter such a problem, for example, we need to go through a maze, we need to move in the real world direction of up, down, left, right or east, west, west. There are all sorts of directions involved in movement, so we need code to represent directions.
For example, if we draw a little person, its coordinate is (x, y), and it can choose from four directions: north, south, east, west. Let’s say he moves one unit at a time, and we can easily figure out what his new coordinates are as he moves in all directions.
According to the mathematical definition of vector, we can write the unit vector of these four directions: [0, 1], [0, -1], [1, 0], [-1, 0].
We store these vectors in an array of constants, and we get the array of directions. When we need to iterate in all directions, we just iterate through this array.
Not only that, but if we have a request for the order of direction traversal, it can be done. In this case, for example, we can see that each time the spiral changes order, it turns 90 degrees to the left.
The rotation that was east turned south, the rotation that was south turned west, the rotation that was west turned north, and the rotation that was north turned east. So all we need to do is put the directions in the order of east, south, west, north, and south, and we increment the index of the directions array one bit at a time and modulo 4, and we get the next direction.
This technique is not hard to understand, but it can greatly simplify our code.
answer
Now that we understand the directions array, it’s a lot easier, and we look at the spiral traversal, and each time we change the direction, the length of the traversal is different, but each time we change the direction for the same reason, which is that we’re done traversing in this direction, so we need to change the direction. This is easy to understand, we just need to maintain the end points in each direction and change direction each time we get to the end point. And since the number of elements in the matrix is fixed, we know how many times we’re going to iterate, so we just have to handle the change of direction, and we’re done.
Let’s look at the code:
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
Define the orientation array
fx = [[0.1], [1.0], [0.- 1], [- 1.0]]
n = len(matrix)
if n == 0:
return []
m = len(matrix[0])
ret = []
# define boundary array
The order of the boundary array and rotation is also corresponding
# The top boundary is +1 after the first rotation, so the 0th bit is the top boundary
# After the second rotation, the right boundary is -1
# and so on
condition = [0, m- 1, n- 1.0]
x, y, dt = 0.0.0
for i in range(n * m):
ret.append(matrix[x][y])
x_, y_ = x + fx[dt][0], y + fx[dt][1]
# If you have crossed the boundary, you need to turn around
if x_ < condition[0] or x_ > condition[2] or y_ < condition[3] or y_ > condition[1] :
# update boundaries
if dt in (1.2) :
condition[dt] -= 1
else:
condition[dt] += 1
# Turn and move again
dt = (dt + 1) % 4
x_, y_ = x+fx[dt][0], y+fx[dt][1]
# print(x_, y_)
x, y = x_, y_
return ret
Copy the codeLet’s look at the code, and there’s one more detail we didn’t mention. When we move, we do not make changes directly on the original variable, because if we move out of bounds or trigger other illegal conditions, then we cannot roll back. So we will create new x and y variables to represent the position after the move, even if the move to an illegal position, will not affect the previous result. This is also a common technique. In Python, we underline the end of a variable to indicate that it is a shadow (clone) variable.
conclusion
Personally, I think today’s problem is good. It is necessary for beginners to do it by themselves. Because in the process of doing problems, we can learn the direction array very specifically this very useful problem-solving skills, it is widely used in the search problem, can be said to do algorithm problems must be one of the skills.
You might think that the logic that we use to determine whether or not we need to turn is a little complicated, but it’s not necessary. We can also use some other methods instead, such as we can create an array to record the location of the visited a substitute for the determination of boundary, and using the boundary determination methods, do the consumption of space to be bigger, and some more test by using the method of boundary decision thinking, personally, so I recommend it. Of course, there are some other methods for this problem, such as finding rules, which are not particularly clever, so I won’t take up your time.
Today’s article is all of these, if you feel that there is a harvest, please feel free to point attention or forward, your help is very important to me.
