One algorithm per day (I) - simulation algorithm

One algorithm per day (I) — simulation algorithm

What is a program? The essence of program is to solve problems, and the core of solving problems is algorithm. For programmers, algorithmic ability is a true reflection of your logical thinking and development potential. Of course, algorithm ability is not innate, it is a combination of genius and accumulation, the improvement of algorithm ability requires us to continue to practice, thinking and summary. Starting today, I’m going to take you through algorithms and understand the art of programming.

Z transformation

First, let’s look at an interesting algorithm problem:

Arrange a given string s in zigzagging from top to bottom and left to right, numRows, according to the given number of rows. For example, the input string is"PAYPALISHIRING"Number of lines for3P A H N A P L S I I G Y I R After that, your output needs to be read line by line from left to right, producing A new string, such as:"PAHNAPLSIIGYIR". String convert(string s, int numRows);Copy the code

So let’s think about this for a second, if we were to solve this problem ourselves, how would we do it?

With that thought, let’s analyze the problem.

This problem is a very typical simulation algorithm problem, the introduction to us: input, transition conditions, expected results, and even the idea of solving the problem have given us. Don’t believe it? Let’s take a look:

The input is a string and a line number, arranged from the top down.
When you get to the tail row, you flip it, diagonal up from left to right, and when you get to the top row, you flip it again, and then you go down again.
Repeat process 2, ending the flip at the end of the string.

The algorithm is as follows:

var convert = function(s, numRows) {
    // If there is only one column, print it directly
    if(numRows === 1) return s;
    // Calculate the rollover rule
    const roundNum = 2 * (numRows - 1);
    // nowRow indicates the current row and flag indicates whether to move up or down
    let nowRow = 0, flag = true;
    // Declare an array of lines of strings to store the characters on each line
    const fianlArr = new Array(numRows).fill(' ');
    for(let i = 0; i<s.length; i++) {
        // When you get to the front row, flip the flags from top to bottom
        if(i % roundNum === 0 ) {
            flag = true;
        }
        // When it comes to the tail, reverse the flags to align them from bottom to top
        if(i % roundNum === (numRows - 1)) {
            flag = false;
        }
        // Populate the row array with the contents of the corresponding row
        fianlArr[nowRow] += s[i];
        // The number of lines moves up or down according to the flag
        nowRow = flag ? (nowRow + 1) : (nowRow - 1);
    }
    // Concatenate the string in the row array
    return fianlArr.join(' ');
}
Copy the code

Const roundNum = 2 * (numrows-1); This line, let’s explain:

Excluding a row, let’s list the vertex positions of the remaining rows:

The number of rows	shadow	The first line	shadow	.
2	1	2	3	.
3	2	4	6	.
4	3	6	9	.
5	4	8	12	.

RoundNum = 2 * (numrows-1) const roundNum = 2 * (numrows-1) const roundNum = 2 * (numrows-1) When the remainder of the subscript position divided by roundNum is numrows-1, it indicates that the current row is in the tail row.

The echo prints a two-dimensional array

Let’s look at a similar problem:

Enter two numeric rows and columns, and the loop prints a two-dimensional array increasing in size in the direction of the loop. Input:5 、4Output:0   1   2   3 
13  14  15  4
12  19  16  5
11  18  17  6
10  9   8   7Input:3.2Output:0  1
5  2
4  3
Copy the code

In this problem, we use a similar solution to the z-transform:

Enter two numbers, m and n, corresponding to the number of rows and columns respectively

We can take the product of m and n to get the total number of processing, and generate a two-dimensional array of m x n to store the final result.
Fills a two-dimensional array from left to right starting at 0
When you reach the last column, change the fill direction to top down
When you reach the last line, change the fill direction to right to left
When you reach the first column, change the fill direction to bottom up
When we reach the second row, we find that the first row has already been filled (we pass arr[x][y]! == undefined to determine whether the data is filled), then we change the filling direction to from left to right
Repeat steps 3 to 6 until m x n times.

We will find that, after processing m x N, we perfectly simulate the loop-print two-dimensional array described in the problem.

conclusion

I leave this topic to you, I hope you can leave a message in the comments section and share your solutions or questions. We will also share the author’s solutions in the next article.

I am how to celebrate more than years, if the article has helped you, I hope you can point a thumbs-up, thank you!

If you have any questions, please discuss them in the comments section.

One algorithm per day (I) — simulation algorithm