跳到主要内容

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);

示例​

输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

提示：

  • 1 <= s.length <= 1000
  • s 由英文字母（小写和大写）、',' 和 '.' 组成
  • 1 <= numRows <= 1000

解题思路​

模拟 Z 字形排列

  1. 边界处理：当行数为1或更少时，Z字形排列等同于原字符串，直接返回
  2. 识别周期性：Z字形排列具有周期性，周期长度为 cycle = 2 × numRows - 2
  • 每个周期包含完整的向下和向上的字符序列
  1. 字符定位：
  • 对于字符串中的第i个字符，计算其在周期中的位置：pos = i % cycle
  • 如果 pos < numRows，字符位于垂直下降部分，直接对应第 pos 行
  • 如果 pos >= numRows，字符位于斜上部分，通过 cycle - pos 计算实际行号

时间复杂度：O(n) 空间复杂度：O(n)

C++ 解法​

#include <string>
#include <vector>

class Solution {
public:
    std::string convert(std::string s, int numRows)
    {
        if (numRows <= 1) return s;
        std::vector<std::string> rows(numRows);
        int cycle = 2 * numRows - 2; // Z字形的周期

        for (int i = 0; i < s.length(); i++) {
            int pos = i % cycle;   // 当前字符所在的行
            if (pos >= numRows) {
                pos = cycle - pos; // 反向计算
            }
            rows[pos] += s[i];     // 加入到对应的行
        }
        std::string res;
        for (const auto &row : rows)
            res += row;
        return res;
    }
};

LeetCode链接： 6. Z 字形变换