LeetCode 6. Z 字形變換：數學規律與多語言實現（C++/Java/C#）

題目理解

將字符串按 numRows 行 Z 字形排列，再按行讀取。例："PAYPALISHIRING", 3 →

P   A   H   N
A P L S I I G
Y   I   R

輸出："PAHNAPLSIIGYIR"。

核心規律：周期性分組

每個完整「V」字形為一組，長度 cycle = 2*numRows - 2。第 0 行和第 numRows-1 行每組只有 1 個字符；中間行每組 2 個字符，間距分別為 2*(numRows-1-row) 和 cycle - 間距1。

C++ 實現

public String convert(String s, int numRows) {
    if (numRows == 1) return s;
    StringBuilder sb = new StringBuilder();
    int cycle = 2 * numRows - 2;
    for (int row = 0; row < numRows; ++row) {
        if (row == 0 || row == numRows - 1) {
            for (int i = row; i < s.length(); i += cycle)
                sb.append(s.charAt(i));
        } else {
            int step1 = 2 * (numRows - 1 - row);
            int step2 = cycle - step1;
            for (int i = row, toggle = 0; i < s.length(); toggle ^= 1) {
                sb.append(s.charAt(i));
                i += (toggle == 0) ? step1 : step2;
            }
        }
    }
    return sb.toString();
}

複雜度與圖解

• 時間：O(n)，每字符訪問一次。
• 空間：O(n) 輸出字符串。
• 

關鍵點總結

• 找出週期 2*numRows-2 是核心。
• 首尾行步長固定；中間行交替步長，用 toggle 控制。
• 邊界 numRows=1 直接返回原串。