ZigZag 排列問題與經典面試題解析（LeetCode ZigZag Conversion）

一、背景：JPEG 編碼中的 Z 字形掃描

JPEG 壓縮中，8×8 圖像塊經 DCT 變換後，需按 Z 字形順序遍歷係數，將低頻係數前置，便於後續游程編碼。遍歷路徑呈對角線來回穿梭。

二、Z 字形矩陣遍歷算法（C++）

觀察規律：對角線方向交替。用 (i+j)%2 判斷方向：偶數向右上，奇數向左下。邊界處理：碰到上/下/左/右邊緣時順時針轉向。

#include <iostream>
#include <iomanip>
using namespace std;
#define SIZE 8

int main() {
    int matrix[SIZE][SIZE] = {0}, a[SIZE][SIZE] = {0};
    int *p = &matrix[0][0];
    for (int i = 0; i < SIZE*SIZE; ++i) *p++ = i; // 初始化

    cout << "原始矩陣:" << endl;
    for (int i = 0; i < SIZE; ++i) {
        for (int j = 0; j < SIZE; ++j) cout << setw(4) << matrix[i][j];
        cout << endl;
    }

    int i = 0, j = 0;
    for (int x = 0; x < SIZE; ++x)
        for (int y = 0; y < SIZE; ++y) {
            a[i][j] = matrix[x][y];
            // 邊界轉向邏輯
            if ((i == SIZE-1 || i == 0) && j%2 == 0) { j++; continue; }
            if ((j == 0 || j == SIZE-1) && i%2 == 1) { i++; continue; }
            if ((i+j)%2 == 0) { i--; j++; }
            else { i++; j--; }
        }

    cout << "\nZ字編排後:" << endl;
    for (int i = 0; i < SIZE; ++i) {
        for (int j = 0; j < SIZE; ++j) cout << setw(4) << a[i][j];
        cout << endl;
    }
    return 0;
}

三、LeetCode 6: ZigZag Conversion（字符串 Z 字形變換）

將字符串按指定行數 Z 字形排列，再按行讀取。如 "PAYPALISHIRING", 3 行：

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

輸出："PAHNAPLSIIGYIR"

解法：模擬行索引變化

用 row 當前行，step 方向（+1 或 -1）。遍歷字符，加入對應行字符串，碰到首尾行反轉方向。

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows <= 1) return s;
        vector<string> rows(numRows);
        int row = 0, step = 1;
        for (char c : s) {
            rows[row] += c;
            if (row == 0) step = 1;
            else if (row == numRows - 1) step = -1;
            row += step;
        }
        string res;
        for (auto& r : rows) res += r;
        return res;
    }
};

四、總結

矩陣 Z 字形遍歷與字符串 Z 字形變換本質相同，核心是方向交替與邊界反彈。掌握規律可輕松應對面試變種。