力扣第六题——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),因为需要额外的空间来存储变换后的矩阵。