本文主要是介绍力扣经典150题第二十二题:Z 字形变换,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
- 力扣经典150题第二十二题:Z 字形变换
- 1. 题目描述
- 2. 解题思路
- 3. 解题步骤
- 4. 代码实现
- 5. 时间复杂度分析
- 6. 应用和扩展
- 7. 总结
- 8. 参考资料
力扣经典150题第二十二题:Z 字形变换
1. 题目描述
将一个给定字符串 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
2. 解题思路
利用模拟的方法,模拟字符在 Z 字形排列中的行索引变化过程。具体步骤如下:
- 使用一个长度为
numRows
的列表rows
,每个元素代表 Z 字形中的一行字符串。 - 初始化一个变量
direction
,表示当前字符遍历的行索引变化方向,初始为1
,表示向下遍历。 - 遍历字符串
s
,依次将每个字符添加到对应的行字符串中。 - 当遍历到第一行或最后一行时,需要改变
direction
方向,实现字符的上下移动。 - 最后将
rows
中的每行字符串连接起来,形成最终的 Z 字形变换后的字符串。
3. 解题步骤
- 创建一个长度为
numRows
的列表rows
,每个元素初始化为空字符串。 - 初始化变量
index
表示当前字符的行索引,direction
表示当前行索引的变化方向。 - 遍历字符串
s
,根据direction
将每个字符添加到对应的行字符串中。 - 根据
direction
判断是否需要改变行索引的方向。 - 将
rows
中的每行字符串连接起来,形成最终的 Z 字形变换后的字符串。
4. 代码实现
class Solution {public String convert(String s, int numRows) {if (numRows == 1) return s; // numRows 为 1,直接返回原字符串List<StringBuilder> rows = new ArrayList<>();for (int i = 0; i < Math.min(numRows, s.length()); i++) {rows.add(new StringBuilder());}int index = 0;int direction = 1; // 1 表示向下遍历,-1 表示向上遍历for (char ch : s.toCharArray()) {rows.get(index).append(ch);index += direction;if (index == 0 || index == numRows - 1) {direction = -direction; // 改变遍历方向}}StringBuilder result = new StringBuilder();for (StringBuilder row : rows) {result.append(row);}return result.toString();}
}
5. 时间复杂度分析
- 遍历字符串
s
,时间复杂度为 O(n),其中 n 是字符串长度。 - 将字符添加到
rows
中的相应行字符串,时间复杂度为 O(n)。 - 将
rows
中的每行字符串连接起来,时间复杂度为 O(numRows)。 - 总体时间复杂度为 O(n)。
6. 应用和扩展
- 该算法可以应用于模拟 Z 字形排列,用于字符串的排列和变换。
- 类似的模拟方法也可以用于其他字符串变换问题。
7. 总结
本文介绍了如何通过模拟 Z 字形排列的方式,将给定字符串按指定行数进行变换,得到 Z 字形变换后的结果字符串。
8. 参考资料
- LeetCode 官网
这篇关于力扣经典150题第二十二题:Z 字形变换的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!