南宁网站建设官网西部数码 网站建设

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

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

漫漫长路，才刚刚开始…

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

参考文章:

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

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 字形排列实际上不会改变字符串顺序。这是一个常见的字符串处理问题，涉及到字符串的遍历和重新组织。

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

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

分析步骤：

1. 初始化 rows 数组和控制变量 curRow 以及 goingDown。
2. 遍历字符串 s，将每个字符添加到正确的行。
3. 如果 curRow 达到 0 或 numRows - 1，则反转 goingDown。
4. 合并 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;
}

代码解释：

• 内存管理：使用 malloc 分配内存，并在最后使用 free 释放内存。
• 字符串操作：使用 strncpy 来复制单词。注意，复制时需要考虑单词的实际长度。

4. 总结

这个题目主要考察字符串的操作和逻辑思维。通过这种类型的题目，我们可以提升对字符串处理和模拟问题解决的能力。要提高编程能力，不仅要理解基本的数据结构和算法，还需要多做类似的练习，加强对边界条件和特殊情况的处理能力，以及对内存和性能的管理。