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)
1
2
3
|
P A H N
A P L S I I G
Y 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:
1
|
string convert(string s, int numRows);
|
Example 1:
1
2
|
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
|
Example 2:
1
2
3
4
5
6
7
8
|
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P I N
A L S I G
Y A H R
P I
|
解：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
/*
* @lc app=leetcode id=6 lang=cpp
*
* [6] ZigZag Conversion
*/
class Solution {
public:
string convert(string s, int nRows) {
if(nRows <= 1) return s;
string result = "";
/*
P A H N
A P L S I I G
Y I R
P | A | H | N
A P | L S | I I | G
Y | I | R |
*/
// 假设一个竖线和一个斜线（不包括斜线和下一个线的交集）是个循环
// 那么循环的公式就是
// cycle = (2*nRows - 2), nRows > 1.
int cycle = 2 * nRows - 2;
for(int i = 0; i < nRows; ++i)
{
for(int firstJ = i; firstJ < s.length(); firstJ = firstJ + cycle){
// firstJ为该行该循环的第一个字母index
result = result + s[firstJ];
// secondJ 该行该循环的第二个字母index
// firstJ - i 当前循环开始的index
// cycle - i 循环内同一行的第二个字母
int secondJ = (firstJ - i) + cycle - i;
if(i != 0 && i != nRows-1 && secondJ < s.length())
result = result + s[secondJ];
}
}
return result;
}
};
|