跳到主要内容

Z 字形变换

· 阅读需 6 分钟
Eureka X
Eureka X
Mr.Nobody

力扣面试经典——6题​

💡 参考代码：​

/**
 * Z字形变换函数
 * @param s 输入字符串
 * @param numRows 指定行数
 * @return 变换后的字符串
 * 
 * 解题思路:
 * 1. 对于第0行和第numRows-1行，字符间隔固定为2*(numRows-1)
 * 2. 对于中间行，字符交替出现在两个等差数列中
 * 3. 特殊情况：numRows=1时直接返回原字符串
 */
char* convert(char* s, int numRows) {
    int len = strlen(s);
    
    // 特殊情况：行数为1或字符串长度小于行数时，直接返回原字符串
    if (numRows == 1 || numRows >= len) {
        return s;
    }
    
    // 分配结果字符串空间
    char* result = (char*)malloc((len + 1) * sizeof(char));
    int index = 0;
    
    // 计算周期长度
    int cycleLen = 2 * numRows - 2;
    
    // 按行遍历
    for (int i = 0; i < numRows; i++) {
        // 遍历每个周期
        for (int j = 0; j + i < len; j += cycleLen) {
            // 每行的第一个字符（垂直列上的字符）
            result[index++] = s[j + i];
            
            // 中间行的第二个字符（斜线上的字符）
            // 条件：不是第一行和最后一行，且索引不越界
            if (i != 0 && i != numRows - 1 && j + cycleLen - i < len) {
                result[index++] = s[j + cycleLen - i];
            }
        }
    }
    
    result[index] = '\0';  // 字符串结束符
    return result;
}

📖 总结：​

点击展开题目总结

🤔 Z字形变换

1️⃣ 题目核心信息​

🎯 功能描述：将字符串按照Z字形方式排列后，按行读取生成新字符串

📥 输入输出：

  • 输入：s（输入字符串），numRows（指定行数）
  • 输出：按Z字形排列后逐行读取的新字符串

2️⃣ 实现原理​

💡 核心思路：通过数学方法直接计算每行字符的位置，避免构造二维矩阵

📋 实现步骤：

  1. 处理特殊情况：当numRows为1或大于等于字符串长度时直接返回原字符串
  2. 计算Z字形周期长度：2*numRows-2
  3. 按行遍历，对每行计算对应字符位置
  4. 对于首尾行，字符间隔固定；对于中间行，每个周期有两个字符位置

3️⃣ 关键点解析​

🎯 代码技巧​

  • 利用周期性规律避免实际构造Z字形矩阵
  • 通过索引计算直接定位字符位置
  • 分别处理首尾行和中间行的不同字符分布规律

4️⃣ 使用场景​

✅ 适用情况：​

  • 需要按特定规律重新排列字符串
  • 字符串变换类问题
  • 需要优化空间复杂度的场景

⚠️ 前提条件：​

  • 输入字符串非空
  • 行数大于0

5️⃣ 复杂度分析​

  • ⏱️ 时间复杂度：O(n)，其中n为字符串长度，每个字符访问一次

  • 💾 空间复杂度：O(1)，不考虑结果字符串的话只使用常数额外空间

6️⃣ 注意事项​

🚩 边界情况：​

  • numRows = 1时，直接返回原字符串
  • 字符串长度为1的情况
  • numRows大于字符串长度的情况

💥 易错点：​

  • 忘记处理numRows = 1的特殊情况导致除零错误
  • 中间行字符位置计算错误
  • 字符串结束符\0忘记添加

7⃣ 补充说明​

整体思路​

这个算法采用按行读取的方式，直接从原字符串中按Z字形顺序提取字符。

代码详解​

  1. 初始化和特殊情况处理
int len = strlen(s);
// 特殊情况：行数为1或字符串长度小于行数时，直接返回原字符串
if (numRows == 1 || numRows >= len) {
    return s;
}

解释：

  • 当 numRows = 1 时，Z字形排列就是原字符串本身
  • 当 numRows >= len 时，每行最多一个字符，结果也是原字符串
  1. 关键参数计算
int cycleLen = 2 * numRows - 2;

解释：计算Z字形的周期长度

  • 例如 numRows = 3 时，cycleLen = 2*3-2 = 4
  • 这意味着每4个字符为一个完整的V字形周期
  1. 按行遍历核心逻辑
for (int i = 0; i < numRows; i++) {
    for (int j = 0; j + i < len; j += cycleLen) {
        result[index++] = s[j + i];
        
        if (i != 0 && i != numRows - 1 && j + cycleLen - i < len) {
            result[index++] = s[j + cycleLen - i];
        }
    }
}

详细例子演示​

以 s = "PAYPALISHIRING", numRows = 3 为例：

原字符串索引: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
原字符串:     P A Y P A L I S H I R  I  N  G
cycleLen = 2*3-2 = 4

第0行 (i=0)：

j=0:  j+i=0, 取s[0]='P'
j=4:  j+i=4, 取s[4]='A'  
j=8:  j+i=8, 取s[8]='H'
j=12: j+i=12,取s[12]='N'
第0行结果: PAHN

第1行 (i=1)：

j=0: j+i=1, 取s[1]='A'
     j+cycleLen-i = 0+4-1=3, 取s[3]='P'
j=4: j+i=5, 取s[5]='L'
     j+cycleLen-i = 4+4-1=7, 取s[7]='S'
j=8: j+i=9, 取s[9]='I'
     j+cycleLen-i = 8+4-1=11,取s[11]='I'
j=12:j+i=13,取s[13]='G'
第1行结果: APLSIIG

第2行 (i=2)：

j=0: j+i=2, 取s[2]='Y'
j=4: j+i=6, 取s[6]='I'
j=8: j+i=10,取s[10]='R'
第2行结果: YIR

Z字形图形化理解​

P     A     H     N        // i=0, 索引: 0,4,8,12
 A   P L   S I   I G       // i=1, 索引: 1,3,5,7,9,11,13
  Y     I     R            // i=2, 索引: 2,6,10

核心规律​

1.垂直列字符：位于索引 j + i 处

2.斜线字符：位于索引 j + cycleLen - i 处（仅中间行）

3.周期跳跃：每次跳跃 cycleLen 个位置

时间复杂度

  • 时间复杂度：O(n)，每个字符只访问一次
  • 空间复杂度：O(n)，用于存储结果字符串

这种方法避免了构造二维数组的额外空间，直接通过数学计算定位字符位置，效率很高。

这道题我至今尚未完全理解（20250815）

加载评论中...