时间戳

首页 > 技术文章 > ZigZag Conversion

ZigZag Conversion

K-artorias 2018-01-17 21:50 原文

题目：

该字符串"PAYPALISHIRING"以一个Z字形模式写在给定行数上，如下所示：（您可能希望以固定字体显示此模式以获得更好的可读性），输入是string和纵向长度，即行数。

 

输出就是PAHNAPLSIIGYIR

我的方法：

想法1：建立一个char类型的二维数组，char[i][j]，i表示行长，为了使行长够长，让i=string的length；j是列长，列长必须等于输入的行数，然后就是输入，要注意按照z形式输入，当string中所有元素都输入完成后，再横向读出，就有了最后结果。

public static String convert(String s, int numRows) {
        if(numRows == 1)
            return s;
        char[][] cs = new char[s.length()][numRows];
        boolean bool = true;
        int i=0, j=0;
        for(int n=0; n<s.length(); n++){//写入
            cs[i][j] = s.charAt(n);
            if(j == numRows-1){
                bool = false;
            }else if(j == 0){
                bool = true;
            }
            if(bool){
                j++;
                continue;
            }
            j--;
            i++;
        }
        String s1 = "";
        for(int p=0; p<numRows; p++){
            for(int q=0; q<s.length(); q++){
                s1 = s1.trim() + cs[q][p];
            }
        }
        return s1.trim();
    }

上述方法可行，但是时间超过限制

想法2：设置一个string[rows]，rows等于列长（即输入的那个行数），然后又因为当读到字符串的第n位时，应该放在第string[num]个字符串上，其中假设x=n%(2*rows-2)，当x>(rows-1)时，num=rows-x。代码如下：

 

 

但是还是时间复杂度过大。为了降低时间复杂度，应使用StringBuilder和append这两个函数，提高String的读写拼接速度，下边是对想法2的修改

 

leetcode方法：

下面两个是leetcode讨论区的方法：

方法1：

class Solution {
    public String convert(String s, int numRows) {
    if(numRows<=1)return s;
    StringBuilder[] sb=new StringBuilder[numRows];
    for(int i=0;i<sb.length;i++){
        sb[i]=new StringBuilder("");   //init every sb element **important step!!!!
    }
    int incre=1;
    int index=0;
    for(int i=0;i<s.length();i++){
        sb[index].append(s.charAt(i));
        if(index==0){incre=1;}
        if(index==numRows-1){incre=-1;}
        index+=incre;
    }
    String re="";
    for(int i=0;i<sb.length;i++){
        re+=sb[i];
    }
    return re.toString();
    }
}

方法2：

public String convert(String s, int nRows) {
    char[] c = s.toCharArray();
    int len = c.length;
    StringBuffer[] sb = new StringBuffer[nRows];
    for (int i = 0; i < sb.length; i++) sb[i] = new StringBuffer();
    
    int i = 0;
    while (i < len) {
        for (int idx = 0; idx < nRows && i < len; idx++) // vertically down
            sb[idx].append(c[i++]);
        for (int idx = nRows-2; idx >= 1 && i < len; idx--) // obliquely up
            sb[idx].append(c[i++]);
    }
    for (int idx = 1; idx < sb.length; idx++)
        sb[0].append(sb[idx]);
    return sb[0].toString();
}

　　

推荐阅读