力扣第六题——Z字形变换

时间：2024-07-19 07:12:30

题目介绍

将一个给定字符串 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

完整代码

char * convert(char * s, int numRows){
    int n = strlen(s), r = numRows;
    if (r == 1 || r >= n) {
        return s;
    }
    int t = r * 2 - 2;
    int c = (n + t - 1) / t * (r - 1);
    char ** mat = (char **)malloc(sizeof(char *) * r);
    for (int i = 0; i < r; i++) {
        mat[i] = (char *)malloc(sizeof(char) * c); 
        memset(mat[i], 0, sizeof(char) * c);                       
    }
    for (int i = 0, x = 0, y = 0; i < n; ++i) {
        mat[x][y] = s[i];
        if (i % t < r - 1) {
            ++x; 
        } else {
            --x;
            ++y; 
        }
    }
    int pos = 0;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if(mat[i][j]) {
                s[pos++] = mat[i][j];
            }
        }
        free(mat[i]);
    }
    free(mat);
    return s;
}

 思路讲解


这段代码是实现了一个将字符串按照Z字形排列并重新排序的功能。以下是代码的思路讲解：
1. **功能描述**：
   该函数`convert`接收一个字符串`s`和一个整数`numRows`，将字符串`s`按照`numRows`行的方式进行Z字形排列，然后按行读取并返回重新排列后的字符串。
2. **边界条件处理**：
   - 如果`numRows`等于1，即只有一行，那么字符串不需要变换，直接返回原字符串。
   - 如果`numRows`大于或等于字符串长度`n`，同样不需要变换，直接返回原字符串。
3. **计算Z字形排列的周期**：
   - `t`表示Z字形排列的一个周期，即从第一行到最后一行再回到第一行的字符数。周期`t`的计算公式为`2 * numRows - 2`。
4. **计算矩阵的列数**：
   - `c`表示Z字形排列后形成的虚拟矩阵的列数。计算公式为`(n + t - 1) / t * (r - 1)`，这里的`r`是`numRows`的别名。
5. **初始化矩阵**：
   - 使用动态内存分配创建一个二维字符数组`mat`，行数为`numRows`，列数为`c`。每个元素初始化为0。
6. **填充矩阵**：
   - 遍历字符串`s`，将字符填充到矩阵`mat`中。使用变量`x`表示当前行，`y`表示当前列。
   - 通过`i % t`判断字符应该向下移动还是向上移动。如果`i % t < r - 1`，则向下移动（即增加行号`x`）；否则，向上移动（即减少行号`x`）并增加列号`y`。
7. **按行读取矩阵**：
   - 遍历矩阵`mat`，按行读取非空字符，并重新填充到字符串`s`中。使用变量`pos`记录当前填充的位置。
8. **释放内存**：
   - 释放矩阵`mat`中每一行的内存，然后释放整个矩阵的内存。
9. **返回结果**：
   - 返回重新排列后的字符串`s`。
通过以上步骤，该代码实现了将字符串按照Z字形排列并重新排序的功能。

知识点解析

Z字形变换是一种常见的字符串处理技巧，它将一个字符串按照特定的行数进行排列，形成类似英文字母“Z”的形状。下面是对实现Z字形变换算法所需的知识点进行详细解析。
#### 1. 字符串与数组
- **字符串操作**：字符串在C语言中通常以字符数组的形式存在。操作字符串时，我们需要注意字符数组的结束符`\0`。
- **数组索引**：通过索引可以访问数组中的特定元素，这对于实现Z字形变换至关重要。
#### 2. 动态内存分配
- **malloc函数**：`malloc`用于在堆区动态分配内存空间。在Z字形变换中，我们需要为行和列分配足够的内存空间。
- **free函数**：为了避免内存泄漏，使用完动态分配的内存后，需要使用`free`函数释放内存。
#### 3. 循环与条件判断
- **for循环**：用于遍历字符串中的每个字符，以及填充和读取矩阵中的每个元素。
- **if-else条件语句**：用于判断当前字符在Z字形中的位置，以决定是向下移动还是向上移动。
#### 4. 数学计算
- **周期计算**：计算Z字形的周期`t`，它决定了字符在Z字形中的移动规律。
- **矩阵列数计算**：根据字符串长度和周期，计算Z字形变换后形成的虚拟矩阵的列数。
#### 5. 字符串与矩阵的转换
- **填充矩阵**：将字符串中的字符按照Z字形的顺序填充到二维字符数组中。
- **读取矩阵**：按照行优先的顺序读取矩阵中的字符，重新组成变换后的字符串。
#### 6. 代码优化
- **边界条件处理**：在算法开始时处理边界条件，避免不必要的计算。
- **内存初始化**：使用`memset`函数初始化矩阵，确保没有未定义的字符。
#### 7. 算法复杂度
- **时间复杂度**：算法的时间复杂度为O(n)，其中n是字符串的长度，因为每个字符只需要遍历一次。
- **空间复杂度**：空间复杂度为O(n)，因为需要额外的空间来存储变换后的矩阵。
 

相关文章