文档章节

将字符串转化成ZigZag模式

指尖跳动的精灵
 指尖跳动的精灵
发布于 2015/04/11 23:20
字数 494
阅读 1333
收藏 2

背景:

原问题出处:https://leetcode.com/problems/zigzag-conversion/

就是将一个字符串按ZigZag格式进行转换,并返回。例如字符串"ABCDEFGHIJK"

转换后(3行):

A E I
BDFHJ
C G K

  然后按行打印:AEIBDFHJCGK

如果按4行转换:

A  G
B FH
CE IK
D  J

打印:AGBFHCEIKDJ

思路:

其实这道题像是找规律题。当转换为3行时,我们可以以4为单位(4=(3-1)*2.也就是等于(行数-1)*2),将字符串分割(以ABCDEFGHIJK为例):

ABCD     EFGH   IJK

那么经过转换后打印的第0行,其实是分割后每一个数组的第0个元素:A E I 。对应到原字符串中就是第0个、第4个、第8.

所以规律为 0,4,8,...4*n..

那么经过转换后打印的第2行(最后一行):打印后的每个元素为:C G K.其实是分割后的每个数组的第二个元素(下标从0可开始) 。对应到原始字符串就是:2 ,2+4,2+4*2,..2+4*n..

从上面可以看出,第一行和最后一行的规律为(设行数为i,从0开始):i+4*n(n=0,1,2...)

其他行:

还是上面的例子,第一行输出为:B D F H J.每一个元素都是分割后的数组中的第1个和第-1个元素。对应到原字符串中为:

1,4-1,4+1,4*2-1,4*2+1...

因此规律为(设i为行数):4*n+i,4*n-i。

代码:

我的代码写的不简单,而且耗时大概110ms,也没有下面的这位朋友的代码耗时少(107ms),所以推荐该朋友的代码:

源代码出处:https://leetcode.com/discuss/11948/my-python-solution

class Solution:
    # @return a string
    def convert(self, s, nRows):
        if nRows == 1:            return s
        D = 2*nRows -2
        L = len(s)
        R = ''
        for i in range(0, nRows):
            MD = 2*nRows - 2 - 2*i
            t = i            while t < L:
                R += s[t]                if i != 0 and i!= nRows-1 and t+MD < L:
                    R += s[t+MD]
                t += D        return R


© 著作权归作者所有

共有 人打赏支持
指尖跳动的精灵
粉丝 15
博文 90
码字总数 48459
作品 0
海淀
LeetCode - ZigZagConversion

以下题干翻译自LeetCode,原文题目请参见LeetCode网址: ZigZagConversion 有一个字符串,当使用ZigZag模式写,并且指定了对应的行数时,如下所示(最好设置一个定长的字体来看): 然后我们要将...

Mock2052
2017/11/21
0
0
Leetcode_6. Zigzag convertion

6. Zigzag convertion 对输入的字符串做锯齿形变换,并输出新的字符串,所谓zigzag变化如下图所示。 将"ABCDEFGHIJKL"做4行的锯齿变换,新的字符串为:AGBFHLCEIKDJ" 实现一个根据输入字符串...

gexin1023
06/28
0
0
编码原理(七) --回顾

1 DCT变换 经过DCT变换,实现了频率的集中。 2量化 经过量化,我们对DCT变换后的系数进行以QP=28的量化,此时得到了一些左上角集中了非零值的系数矩阵。 3 ZigZag扫描 ZigZag扫描,将二维的系...

mmlf
02/07
0
0
freemarker 工作小计

一 date格式化 1.模板中传入date类型的格式化 2.模板中传入long类型的时间戳 ?c 用于将数字转换为字符串 ?number 字符串转化为数字格式 ?numbertodatetime 将数字转化成时间, 它们被用来转换...

Zzzz_WP
07/09
0
0
架构设计:系统间通信(12)——RPC实例Apache Thrift 中篇

(接上文《架构设计:系统间通信(11)——RPC实例Apache Thrift 上篇》) 3、Aapche Thrift详解 在《架构设计:系统间通信(10)——RPC的基本概念》一文中,我专门介绍了一款RPC规范的具体...

引鸩怼孑
2016/01/29
38
0

没有更多内容

加载失败,请刷新页面

加载更多

SpringData JPA 在解析实体类字段时驼峰自动添加下划线问题

SpringData JPA 使用的默认命名策略是: ImprovedNamingStrategy 。用下划线转换驼峰名,如 authorId ,转换成 author_id 。这样就遇到了一个问题:实体中驼峰命名的列名转换成下划线后,在M...

Jacktanger
20分钟前
1
0
Android JNI开发系列(十)JNI访问 Java 实例变量和静态变量

JNI访问 Java 实例变量和静态变量 Java 中的实例变量和静态变量,在本地代码中如何来访问和修改。静态变量也称为类变量(属性),在所有实例对象中共享同一份数据,可以直接通过类名.变量名来...

蔡小鹏
25分钟前
1
0
jsapi4加载的首个图层的范围被默认作为地图范围,且不能修改的解决

在map加载的第一个图层的图层范围(fullExtent),会被默认设置为map的全图范围,且不能更改,从一般地图控件角度来说,应该有fullExtent属性,作为地图的全图范围,但很遗憾jsapi4.9还没有 ...

canneljls
25分钟前
2
0
JSON.stringify()

JSON.parse()与JSON.stringify()的区别 JSON.parse()【从一个字符串中解析出json对象】 例子: //定义一个字符串 var data='{"name":"goatling"}' //解析对象 JSON.parse(data) 结果是: na...

废柴
26分钟前
1
0
HashSet

前言 Set的实现类都是基于Map来实现的(HashSet是通过HashMap实现的)。 构造图如下: 蓝色线条:继承 绿色线条:接口实现 正文 对于HashSet而言,它是基于HashMap来实现的,底层采用HashMap来保...

狼王黄师傅
28分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部