6. Z 字形变换

题目

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

代码

完整代码

#include <string.h>
#include <stdlib.h>

char* convert(char* s, int numRows) {
    int len = strlen(s);
    if(len <= numRows || numRows == 1) {
        return s;
    }

    char* str = (char*)malloc((len + 1) * sizeof(char));
    str[len] = '\0';
    int index = 0;
    char* p = s;

    // 处理第一行
    while(p < s + len && index < len) {
        str[index++] = *p;
        p += 2 * numRows - 2;
    }

    // 处理中间行
    for (int i = 1; i < numRows - 1; i++) {
        p = s + i;
        while(p < s + len && index < len) {
            str[index++] = *p;
            p += 2 * numRows - 2 - 2 * i;
            if(p >= s + len) {
                break;
            }
            str[index++] = *p;
            p += 2 * i;
        }
    }

    // 处理最后一行
    p = s + (numRows - 1);
    while(p < s + len && index < len) {
        str[index++] = *p;
        p += 2 * numRows - 2;
    }

    return str;
}

思路分析

该问题要求将字符串按 Z 字形排列，并按行输出。可以利用数学规律来实现，不必真的创建一个 Z 字形的二维矩阵。

初始化

• 获取字符串的长度 len。
• 如果 len 小于等于 numRows 或者 numRows 为 1，直接返回字符串 s。

处理每一行

• 对于第 0 行，字符位置为 k * (2 * numRows - 2)。
• 对于第 i 行（0 < i < numRows - 1），字符位置为 k * (2 * numRows - 2) + i 和 k * (2 * numRows - 2 - i) + 2 * i。
• 对于最后一行，字符位置为 k * (2 * numRows - 2) + (numRows - 1)。

构建结果字符串

• 依次遍历每一行，按上述规律选取字符并添加到结果字符串中。

拆解分析

初始化和特殊情况处理

int len = strlen(s);
if(len <= numRows || numRows == 1) {
    return s;
}

构建结果字符串

• 创建一个新的字符串 str 用于存放结果，并初始化索引 index 为 0。

处理第一行

char* p = s;
while(p < s + len && index < len) {
    str[index++] = *p;
    p += 2 * numRows - 2;
}

处理中间行

for (int i = 1; i < numRows - 1; i++) {
    p = s + i;
    while(p < s + len && index < len) {
        str[index++] = *p;
        p += 2 * numRows - 2 - 2 * i;
        if(p >= s + len) {
            break;
        }
        str[index++] = *p;
        p += 2 * i;
    }
}

处理最后一行

p = s + (numRows - 1);
while(p < s + len && index < len) {
    str[index++] = *p;
    p += 2 * numRows - 2;
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串的长度。每个字符处理一次。
• 空间复杂度：O(n)，用于存放结果字符串的空间。

结果