算法相关

LeetCode:字符串Z形变换

2019-07-17  本文已影响29人  前端艾希

About

LeetCode刷题第7天,经过这几天的预热,脑子活络起来了,做题速度有了很大的提升,今天这道题为一道中等难度的题,花费了我近1小时,虽然时间还是很长,但是相对刚接触LeetCode有了很大的提升,我会继续坚持。

字符串Z形变换

题目描述

将一个给定字符串根据给定的行数,以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时,排列如下:

L   C   I   R
E T O E S I I G
E   D   H   N
之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"LCIRETOESIIGEDHN"。

请你实现这个将字符串进行指定行数变换的函数:

string convert(string s, int numRows);
示例 1:

输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"
示例 2:

输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:

L     D     R
E   O E   I I
E C   I H   N
T     S     G

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/zigzag-conversion

解题思路

以前在牛客网上刷到一道顺时针打印二维数组的题,跟这个比较类似,我认为做这类题都是要找到它的周期以及周期的规律,这样我们就可以使用循环结构解题了~

  1. 拿到题后,我先自己画了画,找到其中一种周期如下图所示:


    周期.jpeg
  2. 找到周期后分析周期规律为:操作行数的顺序为2,1,0,1,2,3 。一个周期的操作次数为(numRows -1)*2。
  3. 将一个周期分为两部分,前半部分的规律是随着index增加行数减小,后半部分随着index增加行数增加。
  4. 在while循环中嵌套for循环,因为字符串的长度不一定能够整除numRows,所以for循环中可能会出现list out of range的错误,一旦出现该错误就说明字符串已经遍历完毕了。
  5. 字符串遍历完毕后,调用将二维列表转成字符串的方法返回结果。

代码如下(Python3)

class Solution:
    def assemble(self, array):
        result = ''
        for item in array:
            result += ''.join(i for i in item)
        return result
    def convert(self, s: str, numRows: int) -> str:
        if numRows <= 0:
            return False
        elif numRows == 1:
            return s
        if len(s) <= numRows:
            return s
        s = list(s)
        result = [ [s.pop(0)] for item in range(numRows)]
        while len(s):
            for i in range((numRows - 1) * 2):
                for j in range(numRows - 1):
                    try:
                        result[numRows-2 - j].append(s.pop(0))
                    except BaseException:
                        return self.assemble(result)
                for k in range(numRows - 1):
                    try:
                        result[k + 1].append(s.pop(0))
                    except BaseException:
                        return self.assemble(result)
        return self.assemble(result)

解法2

上面那种解法只是该类题的一种通解,运用在这道题上明显太麻烦,如果我们用一个指针指向需要被操作的行数,我们会发现行数的变化规律为:行数从0开始自增到最大行数-1然后开始自减到0,依次循环,所以我们可以通过一个指针指向需要备操作的行数,然后往里面追加字符,代码如下:

#-*- coding:utf-8 -*-
#Author: Bing Xu

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows <= 0:
            return False
        elif numRows == 1:
            return s
        length = len(s)
        if length <= numRows:
            return s
        temp = ['' for i in range(numRows)]
        index = 0
        i = 0
        while index < length:
            while index < length and i < numRows - 1 :
                temp[i] += s[index]
                index += 1
                i += 1
            while index < length and i > 0:
                temp[i] += s[index]
                index += 1
                i -= 1
        result = ''.join(str(item) for item in temp)
        return result

运行结果

image.png

解法3

其实我们也可以根据字符串字符的index直接算出来它归属于哪一行,但是其实时间复杂度不会变,并且我们还是需要一个新的列表去记录,对内存的消耗也不会减少,所以我没有用代码实现这种算法,只是一种思维的拓宽吧。

结束语

看到博客的小伙伴给我点个赞吧,每日更新哦~

上一篇 下一篇

猜你喜欢

热点阅读