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

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

前言

模拟类算法题的核心在于观察数据规律，将抽象的数学逻辑转化为具体的代码实现。本文将通过两道经典题目——Z 字形变换与外观数列，演示如何拆解问题、寻找周期规律以及利用双指针进行字符串处理。

Z 字形变换

题目描述：

示例：

思路分析

这道题的关键在于找到字符排列的周期性规律。假设行数为 numRows，我们可以发现字符是按照'之'字形向下再向上循环填充的。

当 numRows = 4 时，下标变化如下：

• 第 0 行：0, 6, 12...
• 第 1 行：1, 5, 7, 11...
• 第 2 行：2, 4, 8, 10...
• 第 3 行：3, 9...

不难发现，整个模式是以 2 * numRows - 2 为一个完整周期进行重复的。第一行和最后一行是等差数列，公差为周期长度；中间的行则包含两个序列，分别对应周期的前半段和后半段。

基于这个规律，我们可以分三部分处理：

1. 首行：直接按周期步长遍历。
2. 中间行：每个周期内有两个字符需要取出，一个是正向索引，一个是反向索引。
3. 末行：同样按周期步长遍历。

注意边界情况，如果 numRows 为 1，直接返回原字符串即可。

C++ 代码实现

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        
        string ret;
        int d = 2 * numRows - 2; // 周期长度
        int n = s.size();
        
        // 1. 处理第一行
         ( i = ; i < n; i += d) {
            ret += s[i];
        }
        
        
         ( k = ; k < numRows - ; k++) {
             ( i = k, j = d - k; i < n || j < n; i += d, j += d) {
                 (i < n) ret += s[i];
                 (j < n) ret += s[j];
            }
        }
        
        
         ( i = numRows - ; i < n; i += d) {
            ret += s[i];
        }
        
         ret;
    }
};