Solution by JAVA(lucid)


  • 0
    Z

    idea
    if we could know the index of each character which is in the original string,the problem will be solved easily.Now we need to find the regulationin the conversion process by some example.

    example
    e.g1:
    string:“abcdefabcdef” nRows:4
    after conversion:
    0_1504328622413_1f33b63d-edb0-4eaa-b146-1185db6ad06f-图片.png
    as shown in the figure above,the old string was divided into two units and every unit was integrated which is we want to see.
    obviously,the result String is "aabfbfcecedd",but it is most primary purposes to find the law.
    It is not difficult to find that when we know the "nRows",we can figure out a lot of information include "nCols" which refer to the unit count,int this example,the "nCols" is 2,the quantity of total characters in a unit,the relationship between index ,"nRows" and "nCols".
    Law summary:
    Assuming the "nRows" is n,the quantity of total characters in a unit is n+n-2,being 2n-2.the "nCols" is {s.length()/(2n-2)} ,{x} expressed the smallest integer that is not less than x.
    the index law:
    0_1504331750230_a863adc1-a17f-4c65-b94e-bf7a3b57069c-图片.png

    0_1504331518183_25ee1034-4a49-4dd7-8c9c-39ecfb9e972b-图片.png
    when we konw the index of the first unit,the rest of unit will be determinated.
    now we focus that how to express first unit by "n" when "nRows" is "n".
    the first unit index:
    0_1504332701126_a52af89a-aca7-4c2e-96b8-b1a2bd140339-图片.png
    now we have konwn all index of characters in the new String "pciture" after Zigzag conversion.
    then what we need to do is to write into "result string" line by line according the "picture".it is easy.
    All of these are based on conditions that the "s" can be divided into some unbroken units.however if the "s" doesn't satisfy this condition,what should we do?
    e.g2:
    string:“abcdefabcdefg” nRows:4
    after conversion,we konw the last unit only have one character “g”.some errors will occurre in the program under the circumstances.
    Don't worry,we can sovle by adding right quantity of character such as "#" behind the original s
    in this e.g. ,we need to add 5 "#",then s= “abcdefabcdefg#####”.After that,Follow the steps of example 1,finally we will get "reslut string" include the characters we added.It is true "result String" after getting rid of these redundant characters.
    Java Code
    public String convert(String s, int numRows) {
    if(s==""||numRows==1){
    return s;
    }
    String rString="";
    int l=s.length();
    int numCols=(int) Math.ceil((double)l/(double)(2numRows-2));
    int jiange=2
    numRows-2;
    while(numCols*(2numRows-2)>l){
    s=s+"#";
    l++;
    }
    //first row
    for(int col=0;col<numCols;col++){
    rString=rString+s.charAt(0+col
    jiange);
    }
    //form seconde to numRows-1 row
    for(int row=2;row<=numRows-1;row++){
    for(int col=0;col<numCols;col++){
    rString=rString+s.charAt(row-1+coljiange)+s.charAt(2numRows-row-1+coljiange);
    }
    }
    //the nRows row
    for(int col=0;col<numCols;col++){
    rString=rString+s.charAt(numRows-1+col
    jiange);
    }
    System.out.println("one to nRows row:"+rString);
    return rString.replace("#", "");

    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.