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 N
A P L S I I G
Y I RAnd 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 s, int numRows);Example 1:
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"Example 2:
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P I N
A L S I G
Y A H R
P I解：
/*
* @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;
}
};