No.006 ZigZag Conversion

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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏余林丰

MyBatis之ObjectFactory

关于在MyBatis中的ObjectFactory有什么用,在官方文档中有这样的描述(大多数网上的博客都是直接引用这一描述):MyBatis 每次创建结果对象的...

2718
来自专栏从流域到海域

《笨办法学Python》 第39课手记

《笨办法学Python》 第39课手记 本节课讲列表的操作,用来做练习的代码中出现了之前用到过的几个函数,是一节复习课。你需要记住它们。 原代码如下: ten_...

2047
来自专栏大内老A

Dora.Interception, 为.NET Core度身打造的AOP框架[4]:演示几个典型应用

为了帮助大家更深刻地认识Dora.Interception,并更好地将它应用到你的项目中,我们通过如下几个简单的实例来演示几个常见的AOP应用在Dora.Int...

4326
来自专栏java思维导图

总结:JDK1.5-JDK1.8各个新特性

作者:iwen-J | 链接:https://my.oschina.net/zhuqingbo0501/blog/1784693 JDK各个版本的新特性 以...

6547
来自专栏搜云库

BTA 常问的 Java基础40道常见面试题及详细答案

最近看到网上流传着,各种面试经验及面试题,往往都是一大堆技术题目贴上去,而没有答案。

6006
来自专栏不想当开发的产品不是好测试

testNG的高级用法 --DataProvider

@DataProvider Method参数 数据提供者的第一个参数是java.lang.reflect.Method,TestNG传递这个将调用的测试方法。如...

26610
来自专栏蘑菇先生的技术笔记

探索c#之不可变数据类型

2094
来自专栏一个会写诗的程序员的博客

第9章 文件IO操作、正则表达式与多线程第9章 文件IO操作、正则表达式与多线程

我们在《第6章 扩展函数与属性》中已经介绍过Kotlin中的类扩展的特性。使用Kotlin的扩展函数功能,我们可以直接为 String 类实现一个 inc() ...

1143
来自专栏一个会写诗的程序员的博客

ES6 极简教程(ES6 Tutorial) 文 / 东海陈光剑ES6 极简教程(ES6 Tutorial)Kotlin 开发者社区

JavaScript是ECMAScript的实现和扩展,由ECMA(一个类似W3C的标准组织)参与进行标准化。ECMAScript定义了:

1003
来自专栏积累沉淀

【译】Java 8的新特性—终极版

声明:本文翻译自Java 8 Features Tutorial – The ULTIMATE Guide,翻译过程中发现并发编程网已经有同学翻译过了:...

24810

扫码关注云+社区

领取腾讯云代金券