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

算法实战：Z 字形变换与外观数列

Z 字形变换

问题描述

将给定字符串按照指定行数进行 Z 字形排列，然后按行读取生成新字符串。

思路分析

观察 Z 字形排列规律，可以发现字符下标是以 2 * numRows - 2 为一个周期循环的。第一行和最后一行的字符间隔固定为周期长度，而中间行的字符则分为两部分：一部分在垂直列上，另一部分在对角线上。

具体实现时，我们可以分别处理第一行、中间行和最后一行：

1. 第一行：下标从 0 开始，每次增加周期长度。
2. 中间行：每轮周期包含两个字符，一个在当前行号位置，另一个在对称位置（周期长度减去当前偏移）。
3. 最后一行：下标从 numRows - 1 开始，每次增加周期长度。

注意边界情况，当行数为 1 时，直接返回原字符串即可。

C++ 代码实现

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