将一个给定字符串 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。