6. Z 字形变换

6. Z 字形变换

题目

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1：

输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

示例 2：

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

示例 3：

输入：s = "A", numRows = 1
输出："A"

提示：

• 1 <= s.length <= 1000
• s 由英文字母（小写和大写）、',' 和 '.' 组成
• 1 <= numRows <= 1000

题解

解法1

设字符串总长度为 n ，行数为 numRows ，那么从上到下再到上，一个循环的长度为 m=2*(numRows-1)。
对于第 k 个字符，排列后的：

• 横坐标为 i=min(k%m,m-k%m)
• 纵坐标为 (k//m)*m/2+max(0,k%m-m/2)

我们以横纵坐标为 key 进行排序，排序后即为所求字符串。

class Solution:
    def convert(self, s: str, numRows: int):
        n = len(s)
        m = 2*(numRows-1)
        m_2 = numRows-1
        if m == 0:
            return s

        def f(k):
            i = min(k % m, m-k % m)
            j = (k//m)*m_2+max(0, k % m-m_2)
            return n*i+j

        P=sorted(range(n),key=f)
        return "".join([s[i] for i in P])

代码很优美，只是速度略慢。。。

解法2

直接找规律，行数越往下，对应位置字符的间隔越小：

s = "PAYPALISHIRING"
m = 2*(numRows-1)
for k in range(m):
    print(s[k::m])

# PAHN
# ALIG
# YIR
# PSI

然后就可以很优雅地写出代码：

class Solution:
    def convert(self, s: str, numRows: int):
        n = len(s)
        m = 2*(numRows-1)
        m_2 = numRows-1
        if m == 0:
            return s
        L = []
        L.append(s[::m])
        for k in range(1, m_2):
            s1 = s[k::m]
            s2 = s[m-k::m]
            s3 = [None]*(len(s1)+len(s2))
            s3[::2] = s1
            s3[1::2] = s2
            L.append("".join(s3))
        L.append(s[m_2::m])
        return "".join(L)

当然，这样的话，由于大量复制字符串，所以速度比较慢。

想快的话，就不用切片，只是这样写起来太恶心了。。。

class Solution:
    def convert(self, s: str, numRows: int):
        n = len(s)
        m = 2*(numRows-1)
        m_2 = numRows-1
        if m == 0:
            return s
        L = []
        for i in range((n+m-1)//m):
            L.append(s[i*m])
        for k in range(1, m_2):
            for i in range(n//m):
                L.append(s[i*m+k])
                L.append(s[(i+1)*m-k])
            if (n//m)*m+k < n:
                L.append(s[(n//m)*m+k])
            if (n//m+1)*m-k < n:
                L.append(s[(n//m+1)*m-k])
        for i in range((n+m_2-1)//m):
            L.append(s[i*m+m_2])
        return "".join(L)

解法3

最后看到了别人的代码。。。为什么可以这么简洁！！！

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows < 2: return s
        res = ["" for _ in range(numRows)]
        i, flag = 0, -1
        for c in s:
            res[i] += c
            if i == 0 or i == numRows - 1: flag = -flag
            i += flag
        return "".join(res)

作者：jyd
链接：https://leetcode-cn.com/problems/zigzag-conversion/solution/zzi-xing-bian-huan-by-jyd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。