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".
这个问题到手想法就是找规律，把相应位置的字符依次移入即可。
规律如下：当zigzag的行数为n时，第i行依次增加2*(n-i)和2*(i-1)个字符，
例如当n=9时，取字符串的第几个值规律如下：
竖线左侧为字符串标号，右侧为增加值的规律2*(n-i)和2*(i-1)。
据此写代码：
class Solution { public String convert(String s, int numRows) { if((numRows==1)||(s.length()<=numRows)) return s; StringBuilder res=new StringBuilder(); int[][] a=new int[numRows][2]; int index=0,length=s.length(),j=0; boolean stop=true; System.out.println(length); for (int i=0;i<numRows;i++) { a[i][0]=(numRows-1-i)*2; a[i][1]=i*2; } for(int i=0;i<numRows;i++) { index=i; System.out.println(index); res.append(s.charAt(index)); j=0; stop=true; while(stop) { if(a[i][j%2]!=0) { index+=a[i][j%2]; if(index<length) { System.out.println(index); res.append(s.charAt(index)); } else stop=false; } j++; } } return res.toString(); } }
要点：
1、构建两个数组表示增加值；
2、用StringBuilder字符串编辑；
3、注意原字符串的长度，停止循环；
4、特殊情况：空字符串，字符串的长度比zigzag的长度要小。
我自我感觉时间复杂度没有那么夸张，应该在O（n）上，毕竟每个值都是直接从对应的位置取过来的。但是网站上显示很差劲。。。。
看下Solution后再更新。
原文：http://www.cnblogs.com/Einsler/p/7589463.html