首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >No.006 ZigZag Conversion

No.006 ZigZag Conversion

作者头像
mukekeheart
发布2018-02-27 12:15:50
5000
发布2018-02-27 12:15:50
举报

6. ZigZag Conversion

  • Total Accepted: 98584
  • Total Submissions: 398018
  • Difficulty: Easy

  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".

  思路:

  首先,我们需要弄清楚这个ZigZag是怎么排列的,这个单词直译过来就是折线、之字形的,在这里不好具体表达,直接放一张图在下面,大家感受一下就知道了。下面分别是行数为5行、8行、10行的情况下的打印图

  通过上面的图我们知道,这种排列是有周期的,一个“V”字形为一个周期,我们知道除了第一行和最后一行没有重叠,其他行都有重叠,所以周期为period = 2*nRows-2。所以,我们打印的时候可以之间根据这个周期来进行按行打印。

  我们假设设定的共有n行,

  • 显然,n = 1 时,转换之后的字符串最后就是原先的字符串了
  • 当n > 1时
    • 那么第 0 行,没有重复,所有字符的位置index就是0,0+period,0+2*period。。。即每个周期内添加一个字符
    • 对于第 1 行,显然有重复,所有字符的位置index就是(1,0 +period - 1 ),(1+period,0+2*period-1),(1+2*peroid,0+3*period-1).。。。即每个周期内添加两个字符
    • 。。。
    • 对于第 i 行,显然有重复,所有字符的位置index就是(i,0 +period - i ),(i+period,0+2*period-i),(i+2*peroid,0+3*period-i).。。。即每个周期内添加两个字符
    • 。。。
    • 对于第 (n-1) 行,也就是最后一行,没有重复,所有字符的位置index就是(n-1), (n-1)+ period  , (n-1)+2* period 。。。即每个周期内添加一个字符
    • 对于第0行和最后一行有一个特点就是 (period-i)%peroid == i

  所以,代码如下:

 1 public String convert(String s, int numRows) {
 2     if(s == null || s.length() <= numRows || numRows == 1){
 3         return s ;
 4     }
 5     StringBuilder res = new StringBuilder() ;
 6     char [] arr = s.toCharArray() ;
 7     int period = 2*numRows - 2 ;
 8     for(int i = 0 ; i < numRows ; i++){
 9         for(int j = i ; j < s.length(); j += period){
10             if((period-i)%period != i){
11                 res.append(arr[j]) ;
12                 if((j+period-2*i) < s.length()){
13                     res.append(arr[j+period-2*i]) ;
14                 }
15             }else{
16                 res.append(arr[j]) ;
17             }
18         }
19     }
20     
21     return res.toString() ;
22 }
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2016-07-25 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 6. ZigZag Conversion
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档