How to solve the ZigZag Conversion problem in leetcode

This article will explain in detail how to solve the ZigZag Conversion problem in leetcode. The editor thinks it is very practical, so I share it with you for reference. I hope you can get something after reading this article.

ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P A H NA P L S I I GY I R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

String convert (string text, int nRows)

Convert ("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR"

Meaning of the title:

The transformation of zigzag (zigzag). The transformation is as follows:

A) two rows: 0 2413 6B) three rows: 0 481 3 5 7 92 6 10C) four rows: 0 6 121 5 7 11 132 4 8 10 143 9 15D) the number of rows is seven: the first line: 0 12 24 the second line: 1 11 13 23 25 Line 3: 2 10 14 22 26 Line 4: 3 9 15 21 27 Line 5: 4 8 16 20 28 Line 6: 5 7 17 19 29 Line 7: 6 18 30

If you look at the above situation, you can see:

1) the distance between the first and last lines is: (number of rows-1) * 2

2) the sum of the distance between the first element and the second element and between the second element and the third element in the middle lines is: (number of lines-1) * 2.

3) the relationship between the distance between the first element and the second element in the middle lines and the number of lines: (number of rows-number of lines) * 2.

4) the relationship between the distance between the second and third elements in the middle lines and the number of lines: (line-1) * 2.

So there is the getIndex () function:

1) if it is the first element of each row, return the number of rows directly.

2) if it is the subscript of the first or last line except the first element: the subscript of the previous element + (number of lines-1) * 2

3) get the subscript of the even series in the middle several rows: the subscript of the previous element + (number of rows-number of rows) * 2

4) get the subscript of the odd column in the middle rows (except the first element): previous element subscript + (lines-1) * 2

Note:

Because the number of lines in the program starts from zero, there will be a difference of one in the program.

IntgetIndex (int index, int cnt, int numRows, int flag) {if (flag = = 0) {return cnt;} else if (cnt = = 0 | | cnt = = numRows-1) {index = index + (numRows-1) * 2;} else if (flag% 2! = 0) {index = index + (numRows-1-cnt) * 2 } else if (flag% 2 = = 0) {index = index + cnt * 2;} return index;} char* convert (char* s, int numRows) {if (* s = ='\ 0' | | numRows = = 1) {return s;} int len = strlen (s); if (len)