2015年9月16日星期三

Leetcode 6 ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P   A   H   N
A P L S I I G
Y   I   R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string text, int nRows);
convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

Solution 1: Just a programming problem.

 public class Solution {  
   public String convert(String s, int numRows) {  
     if (numRows==0) return "";  
     if (numRows==1) return s;  
     int n=s.length();  
     StringBuilder[] row=new StringBuilder[numRows];  
     for (int i=0; i<numRows; i++) row[i]=new StringBuilder();  
     int j=0;  
     while (j<n) {  
       for (int i=0; i<numRows && j<n; i++) row[i].append(s.charAt(j++));  
       for (int i=numRows-2; i>0 && j<n; i--) row[i].append(s.charAt(j++));  
     }  
     String res="";  
     for (int i=0; i<numRows; i++) res=res+row[i].toString();  
     return res;  
   }  
 }  

Solution 2: No additional memory.
 public class Solution {  
   public String convert(String s, int numRows) {  
     if (numRows==0) return "";  
     if (numRows==1) return s;  
     int n=s.length();  
     StringBuilder res=new StringBuilder();  
     for (int i=0; i<numRows; i++) {  
       for (int j=i; j<n; j+=2*numRows-2) {  
         res.append(s.charAt(j));  
         if (i!=0 && i!=numRows-1 && j+2*(numRows-1-i)<n)  
           res.append(s.charAt(j+2*(numRows-1-i)));  
       }  
     }  
     return res.toString();  
   }  
 }  

没有评论:

发表评论