Z 字形变换

将一个给定字符串 s 根据给定的行数 numRows，以从上往下、从左到右进行 Z 字形排列，之后从左往右逐行读取，产生出一个新的字符串。

示例 1：

• 输入：s = "PAYPALISHIRING", numRows = 3
• 输出："PAHNAPLSIIGYIR"

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

示例 2：

• 输入：s = "PAYPALISHIRING", numRows = 4
• 输出："PINALSIGYAHRPI"

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

提示：

• 1 <= s.length <= 1000
• 1 <= numRows <= 1000

解题思路：

用二维矩阵模拟 Z 字形排列。设周期 m = 2*numRows-2，对每个字符按 mod = i % m 判断：

• mod < numRows：竖向部分，行号为 mod，列号为 2*(i/m)
• mod >= numRows：斜向部分，行号为 m - mod，列号为 2*(i/m)+1

最后按行遍历矩阵拼接结果。特判 numRows == 1 避免除零。

C++

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        int n = s.size();
        int m = 2 * numRows - 2;
        int k = 2 * (n / m + 1);
        vector<vector<char>> mat(numRows, vector<char>(k, 0));
        for (int i = 0; i < n; i++) {
            int mod = i % m, div = i / m;
            if (mod < numRows)
                mat[mod][2 * div] = s[i];
            else
                mat[m - mod][2 * div + 1] = s[i];
        }
        string res;
        for (int r = 0; r < numRows; r++)
            for (int c = 0; c < k; c++)
                if (mat[r][c]) res += mat[r][c];
        return res;
    }
};

Java

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;
        int n = s.length();
        int m = 2 * numRows - 2;
        int k = 2 * (n / m + 1);
        char[][] mat = new char[numRows][k];
        for (int i = 0; i < n; i++) {
            int mod = i % m, div = i / m;
            if (mod < numRows)
                mat[mod][2 * div] = s.charAt(i);
            else
                mat[m - mod][2 * div + 1] = s.charAt(i);
        }
        StringBuilder res = new StringBuilder();
        for (int r = 0; r < numRows; r++)
            for (int c = 0; c < k; c++)
                if (mat[r][c] != 0) res.append(mat[r][c]);
        return res.toString();
    }
}

Python

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        n = len(s)
        m = 2 * numRows - 2
        k = 2 * (n // m + 1)
        mat: List[List[str]] = [['' ] * k for _ in range(numRows)]
        for i in range(n):
            mod, div = i % m, i // m
            if mod < numRows:
                mat[mod][2 * div] = s[i]
            else:
                mat[m - mod][2 * div + 1] = s[i]
        res: List[str] = []
        for r in range(numRows):
            for c in range(k):
                if mat[r][c]:
                    res.append(mat[r][c])
        return ''.join(res)

Go

func convert(s string, numRows int) string {
    if numRows == 1 {
        return s
    }
    n := len(s)
    m := 2*numRows - 2
    k := 2*(n/m+1)
    mat := make([][]byte, numRows)
    for i := range mat {
        mat[i] = make([]byte, k)
    }
    for i := 0; i < n; i++ {
        mod, div := i%m, i/m
        if mod < numRows {
            mat[mod][2*div] = s[i]
        } else {
            mat[m-mod][2*div+1] = s[i]
        }
    }
    var res []byte
    for r := 0; r < numRows; r++ {
        for c := 0; c < k; c++ {
            if mat[r][c] != 0 {
                res = append(res, mat[r][c])
            }
        }
    }
    return string(res)
}

Go 简洁写法（按行直接 append，省去列索引计算）

func convert(s string, numRows int) string {
    if numRows == 1 {
        return s
    }
    rows := make([][]byte, numRows)
    m := 2*numRows - 2
    for i := 0; i < len(s); i++ {
        mod := i % m
        if mod < numRows {
            rows[mod] = append(rows[mod], s[i])
        } else {
            rows[m-mod] = append(rows[m-mod], s[i])
        }
    }
    var res []byte
    for _, row := range rows {
        res = append(res, row...)
    }
    return string(res)
}

时间 O(n)，空间 O(n)。