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 NA P L S I I GY 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：：
The key here is to figure out the index pattern, just draw several concrete example could hele:
nRow = 2:0 2 4 6 8 10 121 3 5 7 9 11 13nRow = 3: 0 4 8 12 1 3 5 7 9 112 6 10nRow = 4:0 6 121 5 7 11 132 4 8 103 9
So inorder to get the final string, we need to scan from the left to right row by row, for the first and last row, the difference
between every two is 2 * nRow – 2, and for the middle say i-th rows, the difference between every two is either 2 * nRow – 2 – 2 * ior 2 * i in turn. Following this, a linear scan of the original string could give us the final result string by pushing the corresponding character at specific index into the final resulted string.第0, len-1行各个字符之间的间隔为2×nRows - 2
第1~len-2行之间会有两个固定间隔之间会有其他字符插入
规律：index + 2 * nRows - 2 * i - 2, 这里i是指行号
1 public class Solution { 2 public static String convert(String s, int nRows) { 3 // Start typing your Java solution below 4 // DO NOT write main() function 5 if (s == null || s.length() == 0 || nRows <= 1) { 6 return s; 7 } 8 int len = s.length(); 9 StringBuffer buffer = new StringBuffer();10 int diff = 2 * nRows - 2;11 for (int i = 0; i < nRows && i < len; i++) {12 if (i == 0 || i == nRows - 1) {13 buffer.append(s.charAt(i));14 int index = i;15 while (index + diff < len) {16 buffer.append(s.charAt(index + diff));17 index = index + diff;18 }19 } 20 else{21 buffer.append(s.charAt(i));22 int index = i;23 while (2 * nRows - 2 * i - 2 + index < len24 || index + diff < len) {25 if(2 * nRows - 2 * i - 2 + index < len){26 buffer.append(s.charAt(2 * nRows - 2 * i - 2 + index));27 }28 if (index + diff < len) {29 buffer.append(s.charAt(index + diff));30 }31 index += diff;32 }33 }34 }35 return buffer.toString();36 }37 } 第二遍：
1 public class Solution { 2 public String convert(String s, int nRows) { 3 // Note: The Solution object is instantiated only once and is reused by each test case. 4 StringBuffer sb = new StringBuffer(); 5 for(int i = 0; i < nRows; i ++){ 6 int j = i; 7 int k = 0; 8 while(j < s.length()){ 9 sb.append(s.charAt(j));10 if ( nRows == 1 ){11 j ++;12 }13 if(i == 0 || i == nRows - 1){14 j += (nRows - 1) * 2;15 }else{16 j += (k % 2 == 1) ? ((nRows - 1) * 2- nRows * 2 + (i + 1) * 2) : (nRows * 2-(i + 1) * 2);17 }18 k ++;19 }20 }21 return sb.toString();22 }23 } 第三遍：
1 public class Solution { 2 public String convert(String s, int nRows) { 3 if(s == null || s.length() == 0) return ""; 4 if(nRows == 1) return s; 5 StringBuilder sb = new StringBuilder(); 6 for(int i = 0; 2*(nRows - 1) * i < s.length(); i ++){ //first row 7 sb.append(s.charAt(2*(nRows - 1) * i)); 8 } 9 10 for(int j = 1; j < nRows - 1; j ++){11 for(int i = 0; (j + 2 * i * (nRows - 1)) < s.length(); i ++){12 sb.append(s.charAt((j + 2 * i * (nRows - 1))));13 if((2 * (nRows - 1) * (i + 1) - j) < s.length())14 sb.append(s.charAt(2 * (nRows - 1) * (i + 1) - j));15 }16 }17 18 for(int i = 0; (nRows - 1) * (2 * i + 1) < s.length(); i ++){ //last row19 sb.append(s.charAt((nRows - 1) * (2 * i + 1)));20 }21 return sb.toString();22 }23 }