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 <= 1000s由英文字母（小写和大写）、','和'.'组成1 <= numRows <= 1000
代码结果
运行时间: 64 ms, 内存: 15.1 MB
/*
* 思路：
* 1. 如果行数为1，直接返回字符串本身。
* 2. 使用一个List<StringBuilder>来保存每一行的字符。
* 3. 遍历字符串，按行数向下和向上分配字符，模拟Z字形。
* 4. 最后将每一行的StringBuilder合并为结果字符串。
* 使用Java Stream API的方式来实现同样的逻辑。
*/
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.List;
import java.util.ArrayList;
public class Solution {
public String convert(String s, int numRows) {
if (numRows == 1) return s;
List<StringBuilder> rows = IntStream.range(0, Math.min(numRows, s.length()))
.mapToObj(i -> new StringBuilder())
.collect(Collectors.toList());
int[] curRow = {0};
boolean[] goingDown = {false};
s.chars().forEach(c -> {
rows.get(curRow[0]).append((char)c);
if (curRow[0] == 0 || curRow[0] == numRows - 1) goingDown[0] = !goingDown[0];
curRow[0] += goingDown[0] ? 1 : -1;
});
return rows.stream().collect(Collectors.collectingAndThen(Collectors.toList(), list -> {
StringBuilder ret = new StringBuilder();
list.forEach(ret::append);
return ret.toString();
}));
}
}解释
方法:
该题解的思路是模拟Z字形变换的过程。先创建一个长度为numRows的数组ans，数组中的每个元素代表Z字形中的一行。然后遍历字符串s，将每个字符添加到对应行的字符串中。使用变量i表示当前行，flag表示移动方向（向下为1，向上为-1）。当到达第一行或最后一行时，改变移动方向。最后将ans数组中的所有字符串拼接起来即可得到结果。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在`numRows < 2`的情况下直接返回原字符串`s`？
▷🦆
在创建`ans`数组时，为什么选择使用`["" for _ in range(numRows)]`而不是其他初始化方式？
▷🦆
为什么要使用变量`flag`来控制移动方向，而不是直接使用两个循环分别处理向下和向上的情况？
▷🦆
在判断改变移动方向的条件时，为什么是`i == 0 or i == numRows-1`？能否详细解释这个边界条件的含义？
▷🦆
最后返回结果时，为什么使用`''.join(ans)`而不是其他拼接字符串的方法？
▷