做u盘的老外网站,手机网站用什么系统,为什么辽宁省城乡建设厅网站打不开,logopond设计网站题目 将一个给定字符串 s 根据给定的行数numRows #xff0c;以从上往下、从左到右进行Z字形排列。比如#xff1a;输入字符串为PAYPALISHIRING#xff0c;行数为3时#xff0c;排列如下。最后#xff0c;你的输出需要从左往右逐行读取#xff0c;产生出一个…题目 将一个给定字符串 s 根据给定的行数numRows 以从上往下、从左到右进行Z字形排列。比如输入字符串为PAYPALISHIRING行数为3时排列如下。最后你的输出需要从左往右逐行读取产生出一个新的字符串比如PAHNAPLSIIGYIR。
P A H N
A P L S I I G
Y I R 示例 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 模拟生成法 模拟生成法通过直接模拟Z字形路径的构建过程来求解其基本思路为创建一个二维数组来存储每行的字符根据Z字形的移动规律填充字符。对于每一列从上到下再从下到上交替填充字符直到所有字符都被放置。最后将二维数组的内容依次连接成一个字符串。使用模拟生成法求解本题的主要步骤如下。 1、初始化。创建一个二维列表大小为numRows行用于存储Z字形排列的每个字符。同时初始化行索引 row为0方向变量goingDown为True表示当前正向下移动False表示向上移动。 2、遍历字符串。对于输入字符串 s 中的每个字符根据当前的行索引row将字符放入二维列表的对应位置。 3、更新行索引和方向。根据当前的移动方向更新行索引如果到达第一行或最后一行则改变移动方向。 4、构造结果字符串。最后遍历二维列表将所有字符按顺序连接成一个字符串并返回。 根据上面的算法步骤我们可以得出下面的示例代码。
def zigzag_conversion_by_simulation(s: str, numRows: int) - str:if numRows 1 or numRows len(s):# 特殊情况处理只有一行或行数大于等于字符串长度时直接返回原字符串return s# 初始化二维列表rows [] * numRowsrow 0goingDown Truefor char in s:# 在当前行添加字符rows[row] charif goingDown:# 增加行索引row 1# 到达最后一行准备向上if row numRows - 1:goingDown Falseelse:# 减少行索引row - 1# 回到第一行准备向下if row 0:goingDown Truereturn .join(rows)print(zigzag_conversion_by_simulation(PAYPALISHIRING, 3))
print(zigzag_conversion_by_simulation(PAYPALISHIRING, 4))
print(zigzag_conversion_by_simulation(A, 1)) 一次遍历法 通过观察Z字形排列的规律可以发现字符串中的字符实际上是以一定的周期性“跳跃”到下一行或上一行。我们可以直接通过计算确定每个字符应该落在哪一行而不需要实际创建二维数组。使用一次遍历法求解本题的主要步骤如下。 1、计算周期。首先识别Z字形排列的周期性。对于每一组完整的“向下-向上”往返涉及2*numRows - 2个字符。另外还需考虑边界情况即当行数为1或字符串长度不足以形成完整周期的场景。 2、遍历并直接构建结果。通过计算当前字符在Z字形中的实际行位置直接在结果字符串中构建输出。利用数学公式确定字符应落在哪一行依据当前字符索引和Z字形的行数动态调整。
def zigzag_conversion_by_traversal(s: str, numRows: int) - str:if numRows 1 or numRows len(s):# 特殊情况处理只有一行或行数大于等于字符串长度时直接返回原字符串return sresult [] * numRowsn len(s)# 完整周期字符数cycle 2 * numRows - 2for i in range(n):# 计算当前字符在Z字形中的行位置在每个周期内字符在前numRows-1行是递增之后是递减row_index i % cycle if i % cycle numRows else cycle - i % cycle# 将字符添加到对应行result[row_index] s[i]# 将结果列表中的字符串合并为一个字符串return .join(result)print(zigzag_conversion_by_traversal(PAYPALISHIRING, 3))
print(zigzag_conversion_by_traversal(PAYPALISHIRING, 4))
print(zigzag_conversion_by_traversal(A, 1)) 总结 模拟生成法的时间复杂度为O(n)其中n是输入字符串的长度。空间复杂度为O(numRows * m)其中m是字符串s中最长行的字符数。最坏情况下如果numRows较大且字符串分布均匀可能需要较大的空间来存储二维数组。模拟生成法直接反映了Z字形的实际构建过程逻辑清晰实现直观易于理解和编码。缺点在于空间效率较低当numRows很大时可能会占用较多的空间。 一次遍历法的时间复杂度也为O(n)空间复杂度为O(numRows)只需一个大小为numRows的列表来暂存每行的字符。相比模拟法空间需求更低特别是当字符串很长而numRows较小时。缺点在于实现相对抽象理解其背后的数学逻辑可能需要更多的思考。
