LeetCode 6. Z 字形变换
题目描述
题意分析
将字符串中的字符按顺序写入指定行数：先向下逐行填写，到最底行后斜向上填写，到最顶行后再次向下，反复进行。最后从上到下逐行读取字符，得到转换后的字符串。
字符本身和数量都不变，变化的是读取顺序。每行内部仍保持字符在原串中的先后关系，因此只要确定每个字符属于哪一行，就不需要保存图中的列坐标和空白位置。
解法：按行模拟方向变化
核心思路
[!blue]
为每一行准备一个缓冲区，按原串顺序将字符追加到所属行。用
row表示当前字符所在行，用direction表示下一步行号的变化：向下为1，向上为-1。处理字符时先追加到
rows[row]，再决定下一步方向。若当前是首行，下一步必须向下；若当前是末行，下一步必须向上；中间行保持原方向。最后执行row += direction，让下一个字符落在正确位置。扫描过程中，每个缓冲区都恰好保存已经处理字符中属于该行的部分，而且追加顺序与原串一致。扫描结束后依次拼接各行，就等价于题目要求的按行读取。
单行时没有折返，必须提前返回，否则移动行号会越界。行数不少于字符数时，所有字符还没开始向上折返就已写完，按行读取仍是原串，也可以直接返回。
解题步骤
- 若
numRows == 1或numRows >= s.length()，返回原串。- 初始化每一行的缓冲区，并设置
row = 0、direction = 1。- 依次读取字符，追加到
rows[row]。- 在首行把方向设为
1，在末行设为-1，再移动行号。- 扫描结束后，按行号从小到大拼接缓冲区并返回。
代码实现
class Solution {
public String convert(String s, int numRows) {
if (numRows == 1 || numRows >= s.length()) {
return s;
}
StringBuilder[] rows = new StringBuilder[numRows];
for (int i = 0; i < numRows; i++) {
rows[i] = new StringBuilder();
}
int row = 0;
int direction = 1;
for (int i = 0; i < s.length(); i++) {
rows[row].append(s.charAt(i));
// 先写入当前行，再在顶端或底端调整下一步方向。
if (row == 0) {
direction = 1;
} else if (row == numRows - 1) {
direction = -1;
}
row += direction;
}
StringBuilder ans = new StringBuilder(s.length());
for (StringBuilder builder : rows) {
ans.append(builder);
}
return ans.toString();
}
}
func convert(s string, numRows int) string {
if numRows == 1 || numRows >= len(s) {
return s
}
rows := make([][]byte, numRows)
row, direction := 0, 1
for i := 0; i < len(s); i++ {
rows[row] = append(rows[row], s[i])
// 先写入当前行，再在顶端或底端调整下一步方向。
if row == 0 {
direction = 1
} else if row == numRows-1 {
direction = -1
}
row += direction
}
ans := make([]byte, 0, len(s))
for i := range rows {
ans = append(ans, rows[i]...)
}
return string(ans)
}
复杂度分析
- 时间复杂度：$O(n)$，其中 $n$ 是字符数。每个字符分配一次、拼接时复制一次；未提前返回时，行数也小于 $n$。
- 空间复杂度：$O(n)$。各行缓冲区共保存 $n$ 个字符，即使不计返回结果，也需要这些中间缓冲区。
关键点总结
[!green]
- 最终输出按行读取，因此保存每一行的字符就足够，无需创建带空格的二维网格。
- 方向只在首行或末行改变，中间行沿用原方向。
- 先保存当前位置的字符，再设置下一步方向并移动，能始终保持行号有效。
易错点总结
[!yellow]
- 单行时首行与末行重合，不能套用普通折返流程，必须提前返回。
- 先移动行号再用首行、末行调整方向，可能在转向前越过边界。
- 扫描过程中把全部字符直接追加到一个结果串，会保留原顺序；应先按行分类，再逐行拼接。
- Java 创建
StringBuilder[]后，数组元素仍为null，需要逐个初始化。
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！