leetcodeday6 –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

第一次尝试:分别求奇数和偶数列的对应的字符串下标

假设:numrows=5,对应位置如果没有元素,设为-1

$$\begin{bmatrix} 0 & -1 &8 & -1 & 16 \\ 1 & 7 & 9 & 15 & 17 \\ 2 & 6 & 10 & 14 & 18 \\ 3 & 5 & 11 & 13 & 19 \\ 4 & -1 & 12 & -1 & 20 \end{bmatrix}$$

因为一般是对行操作,所以先将其转置:

$$\begin{bmatrix} 0 & 1 &2 & 3 & 4 \\ -1 & 7 & 6 & 5 & -1 \\ 8 & 9 & 10 & 11 & 12 \\ -1 & 15 & 14 & 13 & -1 \\ 16& 17 & 18 & 19 & 20 \end{bmatrix}$$

先求偶数行,因为每行首元素:值为 nextstart+(numRows-1)*2 ,因此每一行的值为List[i]=[j for j in range(nextstart,nextstart+numRows)]

奇数行:为上一行的尾元素的顺延,奇数行首尾元素为-1:

List[i][0]=-1
List[i][numRows-1]=-1
List[i][1:numRows-1]=list(range(List[i-1][numRows-1]+1,List[i-1]

接下来转置回来,将二维转一维,然后去掉数组中的-1和值大于序列长度的位置:

List=[i for item in List for i in item if i!=-1 and i<length]

最后根据一维数组对应位置的值就是新字符串对应下标的字符

for j in range(length):
            string[j]=s[List[j]]
        return "".join(string) 

其中numrows=1的 情况要单独考虑

# @lc code=start
class Solution:
    def convert(self, s: str, numRows: int) -> str:
        length=len(s)
        if length<=numRows or numRows==1 :
            return s

        row=(length//((numRows-1)*2)+1)*2
        List=[[-1 for m in range(numRows)] for l in range(row)]
        nextstart=0
    #第i行
        for i in range(row):
#如果是偶数行:

            if(i % 2) == 0:
                List[i]=[j for j in range(nextstart,nextstart+numRows)]
                nextstart=nextstart+(numRows-1)*2
            else:
                List[i][0]=-1
                List[i][numRows-1]=-1
                List[i][1:numRows-1]=list(range(List[i-1][numRows-1]+1,List[i-1][numRows-1]+1+numRows-2))[::-1]
        List=list(list(i) for i in zip(*List))
        List=[i for item in List for i in item if i!=-1 and i<length]
        string=list(range(length))
        for j in range(length):
            string[j]=s[List[j]]
        return "".join(string) 
            

改进:

方法一:按行排序
思路

通过从左向右迭代字符串,我们可以轻松地确定字符位于 Z 字形图案中的哪一行。

算法

我们可以使用 \(\text{min}( \text{numRows}, \text{len}(s))\) 个列表来表示 Z 字形图案中的非空行。

从左到右迭代 s,将每个字符添加到合适的行。可以使用当前行和当前方向这两个变量对合适的行进行跟踪。

只有当我们向上移动到最上面的行或向下移动到最下面的行时,当前方向才会发生改变。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/zigzag-conversion
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注