6. ZigZag Conversion
- Total Accepted: 98584
- Total Submissions: 398018
- Difficulty: Easy
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".
思路：
首先，我们需要弄清楚这个ZigZag是怎么排列的，这个单词直译过来就是折线、之字形的，在这里不好具体表达，直接放一张图在下面，大家感受一下就知道了。下面分别是行数为5行、8行、10行的情况下的打印图
通过上面的图我们知道，这种排列是有周期的，一个“V”字形为一个周期，我们知道除了第一行和最后一行没有重叠，其他行都有重叠，所以周期为period = 2*nRows-2。所以，我们打印的时候可以之间根据这个周期来进行按行打印。
我们假设设定的共有n行，
- 显然，n = 1 时，转换之后的字符串最后就是原先的字符串了
- 当n > 1时
- 那么第 0 行，没有重复，所有字符的位置index就是0，0+period，0+2*period。。。即每个周期内添加一个字符
- 对于第 1 行，显然有重复，所有字符的位置index就是（1，0 +period - 1 ），（1+period，0+2*period-1），（1+2*peroid，0+3*period-1）.。。。即每个周期内添加两个字符
- 。。。
- 对于第 i 行，显然有重复，所有字符的位置index就是（i，0 +period - i ），（i+period，0+2*period-i），（i+2*peroid，0+3*period-i）.。。。即每个周期内添加两个字符
- 。。。
- 对于第 (n-1) 行，也就是最后一行，没有重复，所有字符的位置index就是（n-1）, （n-1）+ period ， （n-1）+2* period 。。。即每个周期内添加一个字符
- 对于第0行和最后一行有一个特点就是 (period-i)%peroid == i
所以，代码如下：
public String convert(String s, int numRows) {
if(s == null || s.length() <= numRows || numRows == 1){
return s ;
}
StringBuilder res = new StringBuilder() ;
char [] arr = s.toCharArray() ;
int period = 2*numRows - 2 ;
for(int i = 0 ; i < numRows ; i++){
for(int j = i ; j < s.length(); j += period){
if((period-i)%period != i){
res.append(arr[j]) ;
if((j+period-2*i) < s.length()){
res.append(arr[j+period-2*i]) ;
}
}else{
res.append(arr[j]) ;
}
}
}
return res.toString() ;
}