[leetcode]6. Z 字形变换

2019-01-17 本文已影响0人 LeeYunFeng

题目描述：

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 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

笨方法（最初的想法）：

基本的想法是：将整个Z字形的字符串看成是一个矩阵，这样我们可以得到每个字母的坐标，那么按列Z字形读取可以得到原字符串，按行顺序读取可以得到转换后的字符串。得到每个字母的坐标，应该是一个时间复杂度O(n)的操作。具体来实现看看，看看有没有什么坑点。

还发现另外一个规律：当numRows=3时，Z字形字符串的形态是2列一循环；当numRows=4时，Z字形字符串的形态是3列一循环。基本上，就是numRows-1列一循环，这numRows-1列共有numRows+numRows-2=2(numRows-1)个字符。根据这个规律，可以得到Z字形矩阵的列数可设为(len(s)//(2(numRows-1))+1)*(numRows-1)，这个列长度应该是大于实际长度的，但预计不影响最终结果。

对于Z字形的行走方向，事实上我们要观察的是个V字形的行走。总是第1笔为从上到下，有numRows个字符，此时横坐标不变、纵坐标加1；第2笔从下到上，有numRows-2个字符，总是横坐标加1、纵坐标减1。似乎不适合用for循环，用while循环。

另外，要考虑numRows≤1的异常情况。还有个点值得注意：不能用np.zeros()矩阵来存储字符串，直接用二维矩阵存储就好了。这个在今后的实践中也应当注意。

虽然是很快的完成了题目，但是只击败了2%的用户，实在是有点寒碜，回头看看有没有更好的解法吧。

笨方法的实现：

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if numRows<=1:
            return s
        numColumns=(len(s)//(2*(numRows-1))+1)*(numRows-1)
        m=[['' for j in range(numColumns)] for i in range(numRows)]#用于存储Z字形矩阵
        index,l=0,len(s)
        i,j=0,0 #Z字形的起点为矩阵的左上角
        while index<l:
            m[i][j]=s[index]
            if j%(numRows-1)==0:
                if i<numRows-1:
                    i+=1
                #达到最下面一行时，横坐标减1，纵坐标加1
                else:
                    i-=1
                    j+=1
            #其余列时，横坐标减1，纵坐标加1
            else:
                i-=1
                j+=1
            index+=1
        # 读出转换后的Z字形字符串，跳过为0的字符
        res=''
        for i in range(numRows):
            for j in range(numColumns):
                res+=m[i][j]
        return res

聪明的方法：

借鉴官网的思路，还有以下方法也可解决：按从左到右读取Z字形字符串，由两个变量控制内容的读取：一个是方向，另一个是行号。在第1行或者第numRows-1行方向转向，方向决定行号是递增还是递减。同一行号的字符，不断的append起来就得到对应行的字符串，把各行的字符串join起来就得到转换后的字符串。

用聪明的方法的确是显著的快了，击败了96%的用户。想了下：该方法时间复杂度是名副其实的O(n)，字符串有多长，咱们的运行时间就多长。而笨办法的时间复杂度看起来是O(n)，但循环内的操作要同时记录行号和列号，最终连接的时候也是要先行内连接、后列内连接，操作步骤更为复杂。聪明的方法果然还要要简洁明了得多，学习别人的思路和代码，果然是提升自己的最快方法。

聪明方法的实现：

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if numRows<=1:
            return s
        res=['' for i in range(numRows)]#记录各行的字符串
        nrow=0#行号
        d=False#方向：False代表向上，True代表向下
        # 从左到右读取Z字形字符串
        for i in s:
            res[nrow]+=i#同一行的字符join起来
            # 到达首行或者尾行时转向
            if nrow==0 or nrow==numRows-1:
                d=(not d)
            step=1 if d else -1# 行号变化的方向
            nrow+=step
        # 读出转换后的Z字形字符串
        return ''.join(res)

[leetcode]6. Z 字形变换

猜你喜欢

热点阅读