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

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)

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.