LeetCode---Problem6 ZigZag Conversion
问题描述： 给定字符串s，按照给定的行数numRows，写成zigZag样式(Z字型样式/锯齿型样式)，要求按照从上到下，从左到右的顺序依次遍历的字符形成的新字符串conversionString。例如String s = "PAYPALISHIRING",numRows = 3按照从上到下，从左到右的顺序conversionString = "PAHNAPLSIIGYIR"一张手绘图,简单明了呈现代码思路 代码 public String convert(String s, int numRows) { if(null==s || numRows<=0) { return null; } if(1==numRows || s.length()<=numRows) { return s; } char[] sb = new char[s.length()]; int pos = 0; //int count = numRows - 1; int i = 0; int index = i; int dis = 2*(numRows-1); //首行 while(index<s.length()) { sb[pos++] = s.charAt(index); index += dis; } //中间numRows-2行 for(i=1;i<numRows-1;i++) { index = i; //中间行相邻两个节点之间的距离有两个值,第一次是dis=2(numRows-(i+1)),因为三个节点构成一个完整的周期,在 //整个周期上的距离为s,s=2*numRows-1-1,所以第二次节点间距离为dis = s-dis,接着就又是dis dis = 2*(numRows-(i+1)); while(index<s.length()) { sb[pos++] = s.charAt(index); index += dis; dis = 2*(numRows-1) - dis; } } //此时i=count=numRows-1即尾行 index = i; dis = 2*(numRows-1); while(index<s.length()) { sb[pos++] = s.charAt(index); index += dis; } return new String(sb); } 这个是提交通过的代码题目本身并不难，之前一次提交的代码，执行超时了，现展示如下: public String convert(String s, int numRows) { if(null==s || numRows<=0) { return null; } if(s.length()<=numRows) { return s; } char[] sb = new char[s.length()]; int pos = 0; for(int i=0;i<numRows;i++) { int index = i; int dis = 2*(numRows-(i+1)); while(index<s.length()) { //首行和尾行遇到dis==0的情况下,不给数组赋值 if(0!=dis) { sb[pos++] = s.charAt(index); } //index移动 index = index + dis; //一个周期共有2*numRows-1个节点,总距离为2*numRows-1-1=2*(numRows-1) dis = 2*(numRows-1) - dis; } } return new String(sb); } 上面代码提交超时,究其原因代码 while(index<s.length()) { //首行和尾行遇到dis==0的情况下,不给数组赋值 if(0!=dis) { sb[pos++] = s.charAt(index); } //index移动 index = index + dis; //一个周期共有2*numRows-1个节点,总距离为2*numRows-1-1=2*(numRows-1) dis = 2*(numRows-1) - dis; } 其中的if语句每次都要进行判断，实际上只在首行和尾行中会遇到，代码看起来整起些，但执行的时间长了。查找算法中经常使用的哨兵就是为了减少数据比对的次数。当然了，上面的代码也没有判断1==numRows的情况。
