首页 > 其他 > 详细

leetcode 每日一题 6.Z字形变换

时间:2020-04-19 21:46:16      阅读:58      评论:0      收藏:0      [点我收藏+]

技术分享图片技术分享图片

1.找规律

思路:

对原字符串进行分块处理,找到每块中数字在Z形变化后的对应关系。

例如:

技术分享图片

 

通过观察发现可以以Z型的头和身为块进行分块。即  [L E E T C O]  [D E I S H I]  [R I N G]

每块的数量等于行数的二倍减去2。即 4 * 2 - 2 = 6

这里可以发现每块中的Z型头元素对应的位置相差 6 也即每块中元素的个数。

然后谈论如何将每块的Z型身子插进去,这里除了Z型头首尾元素外,我们发现其他元素位置右侧对应Z型身元素存在规律,即身元素位置=头元素位置+块的元素数量-2*头元素在块中的位置。例如:[ D E I S H I ] 中头元素 E 在原字符串中位置为7,在块中位置为1,则其对应身元素 I 的位置为  7+6-1*2 = 11。其他元素同理。

所以我们在新字符串中插入元素时,如果插入的是每块的头元素,其对应的身元素存在的话,一并插入进去。

代码:

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        length = len(s)
        newStr ""
        p = numRows*2-2
        n = math.ceil(length/p)
        for i in range(numRows):
            for j in range(n):
                k = i + p*j
                q = k+p-i*2 
                if k < length:
                    newStr += s[k]
                    if i!=0 and i!=numRows-1 and q < length:
                        newStr += s[q]
                    
        return newStr

2.用数组上下遍历插入

思路:

创建一个数组,里面包含对应行数个数的字符串。从上往下遍历,向数组中对应行数字符串插入字符。遍历到最下面时,变方向,从下往上遍历。遍历到第一行时,再变方向,从上往下。最后将数组中每个元素合并到一个字符串中。

技术分享图片

 

代码:

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        arr = [""]*numRows
        curRow = 0
        length = len(s)
        isdown = True
        for c in s:
            arr[curRow] += c
            if isdown:
                curRow +=1
            else:
                curRow -=1
            if curRow == 0 or curRow ==numRows-1:
                isdown = not isdown                    
        return "".join(arr)

 

leetcode 每日一题 6.Z字形变换

原文:https://www.cnblogs.com/nilhxzcode/p/12733539.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!