Algorithm ZigZag-Conversion
Description
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)
if it should be convert to 4 rows
P I N
A L S I G
Y A H R
P I
then we hope output is "PINALSIGYAHRPI"
Submission
class Solution {
public String convert(String s, int numRows) {
if (numRows == 1) {
return s;
}
int mod = numRows + numRows - 2;
// row : 0~numRows-1, <0: %mod == 0> <1: %mod == 1> <2: %mod = 2> <...
StringBuffer[] stringBuffers = new StringBuffer[numRows];
// Arrays.fill(stringBuffers, new StringBuffer());
for (int i = 0; i < numRows; ++i) {
stringBuffers[i] = new StringBuffer();
}
for (int i = 0; i < s.length(); ++i) {
int offset = i % mod;
offset = offset > numRows - 1 ? mod - offset : offset;
stringBuffers[offset].append(s.charAt(i));
}
StringBuffer res = new StringBuffer();
for (int i = 0; i < numRows; ++i) {
res.append(stringBuffers[i]);
}
return res.toString();
}
}
Solution
将字符串转换成 zigzag的转换形式，实际上我们只需要发现，这个锯齿实际上是一个循环的逻辑即可，是指数量的循环
以行数4为例，实际上每六个字符构成一个锯齿的基本形状，之后便是不断地重复，我们的实现便是基于这样的规律性，也就是说，字符串中每个位置
模6的值始终对应固定的行，基于这样的发现，我们便首先定义 mod 的值是多少，实际上 mod=2*numRows - 2之后我们只需创建numRows个StringBuffer对象，分别append到该行的所有字符，最终连接起来即可。
那么问题便是如何根据mod的值获知所在的对应的行，观察分析便可得到 offset的生成逻辑
Review
最终submit的耗时较短，但是空间占用较多，可以在对象创建上进行控制
