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