LeetCode_Python(6)_Z 字形变换

需求

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

比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：
L C I R
E T O E S I I G
E D H N
输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。

示例 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

方法一

解题的过程也是总结规律的过程，找到规律则代码更优雅，更容易理解，如果完全按需求一步一步实现，通常效率会差一点，或者代码不易理解；
本题是按N字形排列，以3行为例，遍历字符串时，得到的字符对应的行号为12321232123·······，构造这样的序列，遍历时添加到不同的行中即可；
创建一个空列表，包含n个子空列表，n为行数，对应不同行的字符；
构建规律中的序列，遍历字符串将字符添加到对应的行中，通过列表推导式合并列表即可。
参考代码

def convert(s, numRows):

    # create null list
    mid = []
    n = 0
    while n < numRows:
        mid.append([])
        n += 1

    # create sequence
    tmp = []
    while len(tmp) <= len(s):
        for i in range(numRows): tmp.append(i)
        for j in range(numRows - 2, 0, -1): tmp.append(j)
    tmp = tmp[:len(s)]
    
    # get str
    for k, v in enumerate(s):
        mid[tmp[k]].append(v)

    return ''.join(''.join(x) for x in mid)

r = 3
s = 'LEETCODEISHIRING'
print(convert(s, r))
LCIRETOESIIGEDHN

方法二

创建一个空列表，包含n个子空列表，n为行数，对应不同行字符；
遍历字符串，将字符添加到空列中对应行数的子空列表中；
由于按N字形排列，遇到首行和尾行时，需要改变添加的方向；
通过列表推导式将结果列表转换成需要的字符串。

参考代码

def get_z_str(s, numRows):

    # no need to convert
    if numRows == 1:
        return s 

    # create null list
    mid = []
    i = 0
    while i < numRows:
        mid.append([])
        i += 1

    j = 0
    for k in s:
        mid[j].append(k)
        if j == 0:
            # direction change
            reverse = False
        if j < numRows - 1:
            if reverse:
                j -= 1
            else:
                j += 1
        else:
            j -= 1
            # direction change
            reverse = True
            
    return ''.join(''.join(x) for x in mid)

r = 3
s = 'LEETCODEISHIRING'
print(convert(s, r))
LCIRETOESIIGEDHN

最后编辑于：2019.01.23 01:24:38