将字符串转化成ZigZag模式
将字符串转化成ZigZag模式
指尖跳动的精灵 发表于3年前
将字符串转化成ZigZag模式
  • 发表于 3年前
  • 阅读 1163
  • 收藏 2
  • 点赞 0
  • 评论 0

背景:

原问题出处: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


共有 人打赏支持
粉丝 16
博文 85
码字总数 48459
×
指尖跳动的精灵
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: