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 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 text, int nRows);
convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".
SOLUTION 1:
使用以下算法会比较简单。
两个规律:
1 两个zigzag之间间距为2*nRows-2
2 每个zigzag中间(在j和j+interval之间)位置为j+interval-2*i
注意:当Rows = 1时,此方法不适用,因为size = 0,会造成死循环。所以Rows = 1时,需要独立处理。
引自:http://blog.csdn.net/fightforyourdream/article/details/16881517
public class Solution {
public String convert(String s, int nRows) {
if (s == null) {
return null;
} // 第一个小部分的大小
int size = * nRows - ; // 当行数为1的时候,不需要折叠。
if (nRows <= ) {
return s;
} StringBuilder ret = new StringBuilder(); int len = s.length();
for (int i = ; i < nRows; i++) {
// j代表第几个BLOCK
for (int j = i; j < len; j += size) {
ret.append(s.charAt(j)); // 即不是第一行,也不是最后一行,还需要加上中间的节点
int mid = j + size - i * ;
if (i != && i != nRows - && mid < len) {
char c = s.charAt(mid);
ret.append(c);
}
}
} return ret.toString();
}
}
2015.1.4 redo:
public class Solution {
public String convert(String s, int nRows) {
if (s == null) {
return null;
} // corner case;
if (nRows == 1) {
return s;
} // The number of elements in a section.
int section = 2 * nRows - 2;
StringBuilder sb = new StringBuilder(); int len = s.length();
for (int i = 0; i < nRows; i++) {
for (int j = i; j < len; j += section) {
char c = s.charAt(j);
sb.append(c); // The middle rows.
int mid = j + section - 2 * i;
// bug 2: the mid is out of range.
if (i != 0 && i != nRows - 1 && mid < len) {
// bug 1: forget a ')'
sb.append(s.charAt(mid));
}
}
} return sb.toString();
}
}
请至主页君的GIT HUB:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/string/Convert.java