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的情况。