首页 > 代码库 > 第6题 ZigZag转换
第6题 ZigZag转换
题目描述如下：
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 NA P L S I I GY I RAnd 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".
即给出一个字符串以及行数，根据该行数进行Z字形排列（自上而下，自左而右）：
然后从左到右，自上而下进行读取。
方法1：
该方法思路比较清晰，实现简单，但效率不高。
step1：
Z字形排列后，可以看作是由多个V构成，根据nRows和字符串的总长度可以确定V的个数和每个V的大小。
代码如下：
int vLen = 2*numRows-2;//每个V的元素个数 int numV = s.length()/vLen;//V的个数 if(s.length()%vLen!=0){ numV=numV+1; }
step2：
依次将字符串的每个字符放入到每个V中，两个for循环，外层循环遍历每个字符，内层循环遍历每个V。代码如下：
for(int i=1;i<=numV;i++){ String V=""; for(int j=1;j<=vLen&&(i-1)*vLen+j<=s.length();j++){ V=V+s.charAt((i-1)*vLen+j -1); } //System.out.println(V); list.add(V);}
for循环内的判断条件(i-1)*vLen+j<=s.length()是为了保证不溢出，因为最后一个V的长度可能小于vLen。
step3：
依次取出所有V的第一行，第二行……第numLine行的字符。代码如下：
String result = ""; for(int i=1;i<=numRows;i++){ for(int j=0;j<list.size();j++){ result=result+getVString(list.get(j),i,vLen); }}
getVString(list.get(j),i,vLen)函数用于取出V中第i行的所有字符。代码如下：
public static String getVString(String V,int linNum,int vLen){ if(V.length()<linNum) return (String) "";//如果V的长度小于行数linNum if(linNum==1) return V.charAt(0)+"";//如果linNum==1,返回V的第一个元素 if(V.length()<=(vLen+2)/2) return V.charAt(linNum-1)+"";//如果V只有左侧有值 if(linNum==(vLen+2)/2) return V.charAt((vLen+2)/2-1)+"";//如果行数等于V的总行数，则去V的底部顶点值 if(vLen+2-linNum<=V.length()) return V.charAt(linNum-1)+""+V.charAt(vLen+2-linNum-1)+""; if(vLen+2-linNum>V.length()) return V.charAt(linNum-1)+""; return "";}
完整代码如下：
1 import java.util.ArrayList; 2 import java.util.List; 3 4 public class ZigZagConversion { 5 6 public static void main(String[] args) { 7 // TODO Auto-generated method stub 8 // String s = "PAYPALISHIRING"; 9 String s="ABCDE";10 System.out.println(convert(s,4));11 }12 public static String convert(String s, int numRows) {13 if(numRows==1||s.length()<=1){14 return s;15 }16 List<String> list = new ArrayList<String>();//存放Z的V部分，每个V用一个字符串表示17 int vLen = 2*numRows-2;//每个V的元素个数18 int numV = s.length()/vLen;//V的个数19 if(s.length()%vLen!=0){20 numV=numV+1;21 }22 for(int i=1;i<=numV;i++){23 String V="";24 for(int j=1;j<=vLen&&(i-1)*vLen+j<=s.length();j++){25 V=V+s.charAt((i-1)*vLen+j -1);26 }27 //System.out.println(V);28 list.add(V);29 }30 String result = "";31 for(int i=1;i<=numRows;i++){32 for(int j=0;j<list.size();j++){33 result=result+getVString(list.get(j),i,vLen);34 System.out.println(j+":"+i);35 System.out.println(list.get(j));36 System.out.println(getVString(list.get(j),i,vLen));37 }38 }39 return result;40 }41 public static String getVString(String V,int linNum,int vLen){42 if(V.length()<linNum) return (String) "";//如果V的长度小于行数linNum43 if(linNum==1) return V.charAt(0)+"";//如果linNum==1,返回V的第一个元素44 if(V.length()<=(vLen+2)/2) return V.charAt(linNum-1)+"";//如果V只有左侧有值45 if(linNum==(vLen+2)/2) return V.charAt((vLen+2)/2-1)+"";//如果行数等于V的总行数，则去V的底部顶点值46 if(vLen+2-linNum<=V.length()) return V.charAt(linNum-1)+""+V.charAt(vLen+2-linNum-1)+"";47 if(vLen+2-linNum>V.length()) return V.charAt(linNum-1)+"";48 return "";49 }50 }
第6题 ZigZag转换
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。