Zigzag solution


  • 0
    D

    """
    public String zigZag(String s,int numRows){
    int len = s.length();
    if(len<=numRows || numRows<=1){
    return s;
    }else{
    int per = 2*numRows - 2;
    int remainder = len % per;
    int count = len / per;
    Map<Integer,List<Integer>> map = new HashMap<>();
    for(int i=0;i<numRows;i++){
    List<Integer> list = new ArrayList<Integer>();
    for(int j=0;j<count;){
    if(i%numRows == 0){
    list.add(per * j);
    }else if(i%numRows == numRows - 1){
    list.add(per * j + (numRows - 1));
    }else{
    list.add(per * j + ( i % numRows));
    list.add(per * j + (per - i % numRows));
    }
    j++;
    }
    map.put(i, list);
    }
    //处理最后一个
    if(remainder > 0){
    for(int i=0;i<numRows;i++){
    List<Integer> list = map.get(i);
    if(i%numRows == 0){
    list.add(per * count);
    }else if(i%numRows == numRows-1){
    if(remainder >= numRows){
    list.add(per * count+ numRows - 1);
    }
    }else{
    if(remainder >= i % numRows + 1){
    list.add(per * count + i % numRows);
    if(remainder > per - i % numRows){
    list.add(per * count + per - i % numRows);
    }
    }
    }
    map.put(i, list);
    }
    }
    StringBuilder sb = new StringBuilder();
    for(int i=0;i<numRows;i++){
    List<Integer> indexes = map.get(i);
    for(int j=0;j<indexes.size();j++){
    sb.append(s.charAt(indexes.get(j)));
    }
    }
    return sb.toString();
    }
    }
    """"


  • 0
    D

    @dinghaijun said in Zigzag solution:

    """
    public String zigZag(String s,int numRows){
    int len = s.length();
    if(len<=numRows || numRows<=1){
    return s;
    }else{
    int per = 2*numRows - 2;
    int remainder = len % per;
    int count = len / per;
    Map<Integer,List<Integer>> map = new HashMap<>();
    for(int i=0;i<numRows;i++){
    List<Integer> list = new ArrayList<Integer>();
    for(int j=0;j<count;){
    if(i%numRows == 0){
    list.add(per * j);
    }else if(i%numRows == numRows - 1){
    list.add(per * j + (numRows - 1));
    }else{
    list.add(per * j + ( i % numRows));
    list.add(per * j + (per - i % numRows));
    }
    j++;
    }
    map.put(i, list);
    }
    //处理最后一个
    if(remainder > 0){
    for(int i=0;i<numRows;i++){
    List<Integer> list = map.get(i);
    if(i%numRows == 0){
    list.add(per * count);
    }else if(i%numRows == numRows-1){
    if(remainder >= numRows){
    list.add(per * count+ numRows - 1);
    }
    }else{
    if(remainder >= i % numRows + 1){
    list.add(per * count + i % numRows);
    if(remainder > per - i % numRows){
    list.add(per * count + per - i % numRows);
    }
    }
    }
    map.put(i, list);
    }
    }
    StringBuilder sb = new StringBuilder();
    for(int i=0;i<numRows;i++){
    List<Integer> indexes = map.get(i);
    for(int j=0;j<indexes.size();j++){
    sb.append(s.charAt(indexes.get(j)));
    }
    }
    return sb.toString();
    }
    }
    """"

    首选:我们考虑特殊情况,字符串长度小于n;就是说只够一列,输入什么,那么返回值就是什么,比如:intput:“abc",2,output:"abc";input:"abc",1,output:"abc"
    非特殊情况:找规律,算出每一行的字符索引,保存起来,然后按照索引将每行的字符组装起来。


  • 0
    D

    规律如下:0 6 12
    1 5 7 11 13
    2 4 8 10 14 16
    3 9 15
    如上面的显示,字符串长度为17,n=4;
    将显示结果分为2部分,一部分能够完整显示的,如索引 [0-5],[6-11],不能完整显示的:索引[12-16];完整显示部分包含一整竖列字符个数 n ,倾斜的字数 n - 2,n-2为去掉竖列公用的和下一个完整显示的竖列第一个,所以一整个完整显示的字符数为:2n -2; 能够完整显示的个数为:count = s.length() / (2n -2);
    循环计算0-n行存储的索引,每个完整显示的数为:per = 2n - 2:
    j=0 j=1 ... j= count -1
    第i=0行: per * j per * j per * j
    第i=1行: perj + i%n perj + i%n perj + i%n
    ,per
    j + per-i%n ,perj + per-i%n ,perj + per-i%n
    ...
    第i=n-1行:perj + n -1 perj + n-1 perj + n-1
    最后计算不完整的,remainder = s.length() % per,remainder >0:
    12
    13
    14 16
    15
    i=0 : 如果remainder>0, per * count
    i=1 : 如果remainder >= i % n + 1, per
    count + i%n
    如果remainder > per - i % n, percount + per - i%n
    ...
    i=n-1: 如果remainder >=n , per
    count + n -1
    最后的结果就是:
    StringBuilder sb = new StringBuilder();
    for(int i=0;i<n;i++){
    List<Integer> indexes = map.get(i);
    for(int j=0;j<indexes.size();j++){
    sb.append(s.charAt(indexes.get(j)));
    }
    }
    return sb.toString();


Log in to reply
 

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