Zigzag Conversion

6. Z字形变换

分析

特殊情况处理：
- 当 numRows = 1 时，Z 字形退化成一行，直接返回原字符串
分行遍历：
- 首行和尾行：字符之间的间隔是固定的 cycleLen = 2 * numRows - 2
- 中间行：每个周期内有两个字符，需要分别计算两个位置
结果拼接：
- 按行依次将字符加入结果字符串

时间复杂度

总时间复杂度 O(n)

空间复杂度

空间复杂度为 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class Solution
{
public:
    string convert(string s, int numRows)
    {
        if (numRows == 1)  // 特殊情况处理
            return s;

        std::string res;
        int cycleLen = 2 * numRows - 2;  // 每个周期的长度

        for (int i = 0; i < numRows; ++i)  // 遍历每一行
        {
            if (i == 0 || i == numRows - 1)  // 首行和尾行
            {
                for (int j = i; j < s.size(); j += cycleLen)
                    res += s[j];
            }
            else  // 中间行
            {
                for (int j = i, k = cycleLen - i; j < s.size() || k < s.size(); j += cycleLen, k += cycleLen)
                {
                    if (j < s.size())  // 第一个字符
                        res += s[j];
                    if (k < s.size())  // 第二个字符（对称位置）
                        res += s[k];
                }
            }
        }
        return res;
    }
};