算法实战：Z 字形变换与外观数列的模拟解法

Z 字形变换

题目描述： 将给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

例如输入字符串为 PAYPALISHIRING，行数为 3 时，排列如下： P A H N A P L S I I G Y I R 然后按行读取生成新字符串：PAHNAPLSIIGYIR。

解题思路： 这道题的核心在于找到字符在 Z 字形中的位置规律。观察发现，字符的排列是以 2 * numRows - 2 为一个周期循环的。

• 首行和末行：每行的字符索引间隔固定为 period。
• 中间行：除了首尾，每一行在一个周期内包含两个字符。第一个字符索引为 i，第二个字符索引为 period - i（其中 i 是当前行号）。

我们可以直接遍历每一行，计算该行所有字符在原字符串中的索引并拼接。这样避免了构建二维数组的空间开销，时间复杂度为 O(n)。

代码实现：

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        
        string ret;
        int period = 2 * numRows - 2;
        int n = s.size();
        
        // 处理第一行
        for (int i = 0; i < n; i += period) {
            ret += s[i];
        }
        
        // 处理中间行
        for (int k = 1; k < numRows - 1; ++k) {
            for (int i = k, j = period - k; i < n || j < n; i += period, j += period) {
                if (i < n) ret += s[i];
                if (j < n) ret += s[j];
            }
        }
        
        // 处理最后一行
        for (int i = numRows - ; i < n; i += period) {
            ret += s[i];
        }
        
         ret;
    }
};