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 text, int nRows);
convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".https://discuss.leetcode.com/topic/3162/easy-to-understand-java-solution
https://leetcode.com/discuss/55208/if-you-are-confused-with-zigzag-pattern-come-and-see
/*n=numRows
Δ=2n-2 1 2n-1 4n-3
Δ= 2 2n-2 2n 4n-4 4n-2
Δ= 3 2n-3 2n+1 4n-5 .
Δ= . . . . .
Δ= . n+2 . 3n .
Δ= n-1 n+1 3n-3 3n-1 5n-5
Δ=2n-2 n 3n-2 5n-4
*/
that's the zigzag pattern the question asked! Be careful with nR=1 && nR=2
The size of every period is defined as "cycle"
cycle = (2*nRows - 2), except nRows == 1.
In this example, (2*nRows - 2) = 4.
In every period, every row has 2 elements, except the first row and the last row.
Suppose the current row is i, the index of the first element is j:
j = i + cycle*k, k = 0, 1, 2, ...
The index of the second element is secondJ:
secondJ = (j - i) + cycle - i
(j-i) is the start of current period, (j-i) + cycle is the start of next period.
http://n00tc0d3r.blogspot.com/2013/06/zigzag-conversion.html
- For any full columns, the odd ones have nRows characters, even ones have(nRows - 2) characters.
- For the first and last rows, we read one single character from each expended column;
- For the rest of rows, we read two characters, one from top part and one from bottom part, from each expended column.
One edge case is that nRows = 1, where (nRows*2 - 2) becomes 0. In this case, we should simply return the original string.
public String convert(String s, int nRows) {
if (nRows == 1) return s;
StringBuilder ss = new StringBuilder();
int n = nRows + nRows - 2;
// rest rows
for (int i = 0; i < nRows; ++i) {
int cur = i;
while (cur < s.length()) {
ss.append(s.charAt(cur));
cur += n;
if (i > 0 && i < nRows - 1 && (cur - i - i) < s.length()) {
ss.append(s.charAt(cur - i - i));
}
}
}
return ss.toString();
}只要看出来他其实每个zigzag是2*m-2个字符就可以，这里m是结果的行的数量。接下来就是对于每一行先把往下走的那一列的字符加进去，然后有往上走的字符再加进去即可。时间复杂度是O(n),空间复杂度是O(1),代码如下：
public String convert(String s, int nRows) {
if(s == null || s.length()==0 || nRows <=0)
return "";
if(nRows == 1)
return s;
StringBuilder res = new StringBuilder();
int size = 2*nRows-2;
for(int i=0;i<nRows;i++)
{
for(int j=i;j<s.length();j+=size)
{
res.append(s.charAt(j));
if(i!=0 && i!=nRows-1 && j+size-2*i<s.length())
res.append(s.charAt(j+size-2*i));
}
}
return res.toString();
}
http://www.lifeincode.net/programming/leetcode-zigzag-conversion-java/
The number of rows is variable. So we need to find the rule of each row. For example, when nRows = 4, we know the ZigZag should be like the following.
It’s easy to find that the step of 4-number column is 6. In fact, the step is just two times of nRows minus 2, in which 2 indicating there are no numbers between the 4-number column in the first line and last line.
And there is only one number between 4-number column in other lines. Take the second line as an example. The second line is “1 5 7 11 13 17 19”. We can take a look at “1 5 7”. The step between “1” and “5” is (nRows – 1 – 1) * 2, which is 4. And the step of “5” and “7” is 6 – 4 = 2. In fact, assuming we are at line i (starting at 0), the first step is (nRows – 1 – i) * 2.
We should be careful about the situation when nRows = 1. Because our formula is not suitable when nRows = 1. And the inner loop should start from i, not 0.
public String convert(String s, int nRows) {
if (nRows == 1)
return s;
StringBuilder builder = new StringBuilder();
int step = 2 * nRows - 2;
for (int i = 0; i < nRows; i++) {
if (i == 0 || i == nRows - 1) {
for (int j = i; j < s.length(); j = j + step) {
builder.append(s.charAt(j));
}
} else {
int j = i;
boolean flag = true;
int step1 = 2 * (nRows - 1 - i);
int step2 = step - step1;
while (j < s.length()) {
builder.append(s.charAt(j));
if (flag)
j = j + step1;
else
j = j + step2;
flag = !flag;
}
}
}
return builder.toString();
}
http://www.cnblogs.com/springfor/p/3889414.html
这道题就是看坐标的变化。并且需要分块处理。
n=2时，字符串坐标变成zigzag的走法就是：
0 2 4 6
1 3 5 7
n=3时的走法是：
0 4 8
1 3 5 7 9
2 6 10
n=4时的走法是：
0 6 12
1 5 7 11 13
2 4 8 10 14
3 9 15
可以发现规律，画红色的长度永远是 2n-2 （想法是你试想把所有这些行压缩成两列，两边手挤一下，第二列永远的第一行和最后一行少字）。
利用这个规律，可以按行填字，第一行和最后一行，就是按照2n-2的顺序一点点加的。
其他行除了上面那个填字规则，就是还要处理斜着那条线的字，可以发现那条线的字的位置永远是当前列j+(2n-2)-2i(i是行的index）。 //????
public String convert(String s, int nRows) {
2 if(s == null || s.length()==0 || nRows <=0)
3 return "";
4 if(nRows == 1)
5 return s;
6
7 StringBuilder res = new StringBuilder();
8 int size = 2*nRows-2;
9 for(int i=0;i<nRows;i++){
10 for(int j=i;j<s.length();j+=size){
11 res.append(s.charAt(j));
12 if(i != 0 && i != nRows - 1){//except the first row and the last row
13 int temp = j+size-2*i;
14 if(temp<s.length())
15 res.append(s.charAt(temp));
16 }
17 }
18 }
19 return res.toString();
20 }
先计算一下每一个zig包含的字符个数，实际上是zigSize = nRows + nRows – 23 return "";
4 if(nRows == 1)
5 return s;
6
7 StringBuilder res = new StringBuilder();
8 int size = 2*nRows-2;
9 for(int i=0;i<nRows;i++){
10 for(int j=i;j<s.length();j+=size){
11 res.append(s.charAt(j));
12 if(i != 0 && i != nRows - 1){//except the first row and the last row
13 int temp = j+size-2*i;
14 if(temp<s.length())
15 res.append(s.charAt(temp));
16 }
17 }
18 }
19 return res.toString();
20 }
然后一行一行的加s中的特定元素就行。
第一行和最后一行都只需要加一个字符，每一个zig，而且在s中的index间隔是zigSize。
中间每一行需要添加两个字符到结果中去。第一个字符同上；第二个字符和前面添加这个字符在s上的inde相差正好是zigSize – 2*ir。ir是行index。
string convert(string s, int nRows) {
if(nRows <= 1) return s;
string ret;
int zigsize = 2 * nRows - 2;
for(int i = 0; i < nRows; ++i) {
for(int base = i; ;base += zigsize) {
if(base >= s.size())
break;
ret.append(1,s[base]);
if(i > 0 && i < nRows - 1) {
//middle need add ziggggging char
int ti = base + zigsize - 2 * i;
if(ti < s.size())
ret.append(1,s[ti]);
}
}
}
return ret;
}
https://leetcode.com/discuss/10990/solutions-follows-order-string-follows-order-output-string
In the above sample case the number of rows is 4, when the first iteration is completed the locations 0,1,2,3 of the string builder gets filled with the locations 0,6,12,18 of the input string it goes on further for other three rows.
0 6 12 18
1 5 7 11 13 17 19
2 4 8 10 14 16 20
3 9 15 21 public String convert(String s, int nRows) { if (nRows == 1) return s; StringBuilder strBuilder = new StringBuilder(); int borderRowStep = 2 * nRows - 2; for (int i = 0; i < nRows; i++) { if (i == 0 || i == nRows - 1) { for (int j = i; j < s.length(); j = j + borderRowStep) { strBuilder.append(s.charAt(j)); } } else { int j = i; boolean flag = true; int insideRowLargeStep = 2 * (nRows - 1 - i); int insideRowSmallStep = borderRowStep - insideRowLargeStep; while (j < s.length()) { strBuilder.append(s.charAt(j)); if (flag) j = j + insideRowLargeStep; else j = j + insideRowSmallStep; flag = !flag; } } } return strBuilder.toString(); }
In the second version of algorithm string buffer is filled in the order of input string i.e, the string buffer gets filled in the zig zag order, when the first iteration of the outer while loop completes the locations 0,5,11,17 in string builder gets filled with the locations 0,1,2,3, from the input string
public String convert(String s, int nRows) {
char[] c = s.toCharArray();
int len = c.length;
StringBuffer[] sb = new StringBuffer[nRows];
for (int z=0; z < sb.length; z++) sb[z] = new StringBuffer();
int k=0;
while (k < len) {
for (int zigZagIndex = 0; zigZagIndex < nRows && k < len; zigZagIndex++) // vertically down
sb[zigZagIndex].append(c[k++]);
for (int zigZagIndex = nRows-2; zigZagIndex >= 1 && k < len; zigZagIndex--) // obliquely up
sb[zigZagIndex].append(c[k++]);
}
for (int index = 1; index < sb.length; index++)
sb[0].append(sb[index]);//\\
return sb[0].toString();
}X. nRows StringBuilder - go down then go up
https://leetcode.com/discuss/10493/easy-to-understand-java-solution
Create nRows StringBuffers, and keep collecting characters from original string to corresponding StringBuffer. Just take care of your index to keep them in bound.
public String convert(String s, int nRows) {
char[] c = s.toCharArray();
int len = c.length;
StringBuffer[] sb = new StringBuffer[nRows];
for (int i = 0; i < sb.length; i++) sb[i] = new StringBuffer();
int i = 0;
while (i < len) {
for (int idx = 0; idx < nRows && i < len; idx++) // vertically down
sb[idx].append(c[i++]);
for (int idx = nRows-2; idx >= 1 && i < len; idx--) // obliquely up
sb[idx].append(c[i++]);
}
for (int idx = 1; idx < sb.length; idx++)
sb[0].append(sb[idx]);//\\
return sb[0].toString();
}Use a delta flag to indicate whether next move should go up or go down.
public String convert(String s, int nRows) { String[] helper = new String[nRows]; for (int i = 0; i < nRows; i ++){ helper[i] = ""; } int row = 0; int delta = 1; for (int i = 0; i < s.length(); i ++){ char c = s.charAt(i); helper[row] += c; if (row == nRows - 1){ delta = -1; } else if (row == 0){ delta = 1; } row = row + delta; row = Math.max(0, row); }//for String result = ""; for (int i = 0; i < nRows && s.length() > 0; i ++){ result += helper[i]; } return result; }https://discuss.leetcode.com/topic/21196/a-10-lines-one-pass-o-n-time-o-1-space-accepted-solution-with-detailed-explantation
The distribution of the elements is period.
P A H N
A P L S I I G
Y I R
For example, the following has 4 periods(cycles):
P | A | H | N
A P | L S | I I | G
Y | I | R |
The size of every period is defined as "cycle"
cycle = (2*nRows - 2), except nRows == 1.
In this example, (2*nRows - 2) = 4.
In every period, every row has 2 elements, except the first row and the last row.
Suppose the current row is i, the index of the first element is j:
j = i + cycle*k, k = 0, 1, 2, ...
The index of the second element is secondJ:
secondJ = (j - i) + cycle - i
(j-i) is the start of current period, (j-i) + cycle is the start of next period.
string convert(string s, int nRows) {
if(nRows <= 1) return s;
string result = "";
//the size of a cycle(period)
int cycle = 2 * nRows - 2;
for(int i = 0; i < nRows; ++i)
{
for(int j = i; j < s.length(); j = j + cycle){
result = result + s[j];
int secondJ = (j - i) + cycle - i;
if(i != 0 && i != nRows-1 && secondJ < s.length())
result = result + s[secondJ];
}
}
return result;
}public String convert(String s, int nRows) {
if(nRows <= 1)
return s;
StringBuilder[] list = new StringBuilder[nRows];
for(int i = 0; i < nRows; i++)
list[i] = new StringBuilder();
int row = 0;
int i = 0;
boolean down = true;
while(i < s.length()){
list[row].append(s.charAt(i));
if(row == 0)
down = true;
if(row == nRows - 1)
down = false;
if(down)
row++;
else
row--;
i++;
}
StringBuilder res = new StringBuilder();
for(StringBuilder sb : list)
res.append(sb.toString());
return res.toString();
}
http://www.cnblogs.com/TenosDoIt/p/3738693.html
Read full article from LeetCode - ZigZag Conversion | Darren's Blog
