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