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 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 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
题目说的是Z形变换，但是加上是 |/|这样的形状，按Z看了好久一点规律都没有，才发现不是Z形的
这里找到一个很坑的规律
对于任意整数序列K[0,1,2,3,4,...]和numRows有：
1.第0行，索引位置为k(2numRows-2),如0(23-2),1(23-2)等
2.最后一行，索引位置为k(2numRows-2)+numRows-1，如04+3-1,14+3-1等
3.其余第i行，索引位置为k(2numRows-2)+i以及(k+1)(2*numRows-2)-i处
很繁琐的一个规律，有了这个就很好写了
class Solution {
public String convert(String s, int numRows) {
if (numRows == 1) return s;
StringBuilder ret = new StringBuilder();
int n = s.length();
int cycleLen = 2 * numRows - 2;
for (int i = 0; i < numRows; i++) {
for (int j = 0; j + i < n; j += cycleLen) {
ret.append(s.charAt(j + i));
if (i != 0 && i != numRows - 1 && j + cycleLen - i < n)
ret.append(s.charAt(j + cycleLen - i));
}
}
return ret.toString();
}
}
