当前位置：首页 > news >正文

代码训练LeetCode(32)Z字形变换

news 2025/6/14 19:59:50

代码训练(32)LeetCode之Z字形变换

Author: Once Day Date: 2025年6月12日

漫漫长路，才刚刚开始…

全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客

参考文章:

6. Z 字形变换 - 力扣（LeetCode）
力扣 (LeetCode) 全球极客挚爱的技术成长平台

文章目录

- - 代码训练(32)LeetCode之Z字形变换
  - - 1. 原题
    - 2. 分析
    - 3. 代码实现
    - 4. 总结

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"

2. 分析

本题要求将给定的字符串 s 按照 Z 字形排列，并按行读取形成一个新的字符串。当 numRows 为 1 或者 numRows 大于等于字符串长度时，Z 字形排列实际上不会改变字符串顺序。这是一个常见的字符串处理问题，涉及到字符串的遍历和重新组织。

我们可以通过模拟行的读取过程来解决这个问题：

创建一个数组 rows，大小为 min(numRows, len(s))，用来存储每一行的字符。
遍历字符串 s 中的每个字符，并根据当前字符的位置，决定它应该放在 rows 的哪一行。
使用一个变量 curRow 来跟踪当前行的位置，使用 goingDown 标记当前是向下还是向上填充字符。
根据 goingDown 的状态，更新 curRow 的值，如果达到 Z 字形的顶部或底部，改变方向。
最后，将 rows 中的所有行合并，形成最终的字符串。

分析步骤：

初始化 rows 数组和控制变量 curRow 以及 goingDown。
遍历字符串 s，将每个字符添加到正确的行。
如果 curRow 达到 0 或 numRows - 1，则反转 goingDown。
合并 rows 数组得到结果字符串。

举例分析：例如，输入 "PAYPALISHIRING", numRows = 3：

初始化 rows = ["", "", ""]，curRow = 0，goingDown = true。
按顺序处理每个字符：
- ‘P’ -> 第0行
- ‘A’ -> 第1行
- ‘Y’ -> 第2行 (此时到底部，改变方向)
- ‘P’ -> 第1行
- ‘A’ -> 第0行 (到顶部，改变方向)
- … 依此类推。
最后合并得到 "PAHNAPLSIIGYIR"。

性能优化关键点：

内存管理：确保为每个行分配足够的空间，并在最后正确释放内存。
字符串操作：避免使用过多的字符串连接操作，因为这会增加时间复杂度。在本实现中，我们使用 strcat，在实际高性能需求下可能需要优化。

3. 代码实现

#include <stdio.h>
#include <string.h>
#include <stdlib.h>char* convert(char* s, int numRows) {if (numRows == 1) return s;int len = strlen(s);char **rows = malloc(sizeof(char*) * numRows);for (int i = 0; i < numRows; i++) {rows[i] = malloc(sizeof(char) * (len + 1));rows[i][0] = '\0'; // 初始化空字符串}int curRow = 0;int goingDown = 0;for (int i = 0; i < len; i++) {strcat(rows[curRow], (char[]){s[i], '\0'});if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;curRow += goingDown ? 1 : -1;}char *result = malloc(sizeof(char) * (len + 1));result[0] = '\0';for (int i = 0; i < numRows; i++) {strcat(result, rows[i]);free(rows[i]);}free(rows);return result;
}int main() {char input[] = "PAYPALISHIRING";int numRows = 3;char* output = convert(input, numRows);printf("Output: %s\n", output);free(output);return 0;
}