017-Z 字形变换 (ZigZag Conversion)

题目描述

将一个给定字符串 s 根据给定的行数 numRows，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

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

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

示例

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

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

输入：s = "A", numRows = 1
输出："A"

解题思路

使用模拟法，按照Z字形的规律逐行构建结果字符串。使用一个数组存储每一行的字符，然后按照Z字形的路径遍历原字符串，将字符添加到对应的行中。

JavaScript 解决方案

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
const convert = (s, numRows) => {
    if (numRows === 1 || s.length <= numRows) return s;
    
    const rows = new Array(numRows).fill('');
    let currentRow = 0;
    let direction = 1; // 1表示向下，-1表示向上
    
    for (const char of s) {
        rows[currentRow] += char;
        
        // 改变方向
        if (currentRow === 0) {
            direction = 1;
        } else if (currentRow === numRows - 1) {
            direction = -1;
        }
        
        currentRow += direction;
    }
    
    return rows.join('');
};

复杂度分析

时间复杂度：O(n)，其中 n 是字符串长度
空间复杂度：O(n)，需要存储结果字符串

测试用例

// 测试函数
const testConvert = () => {
    const testCases = [
        {
            s: "PAYPALISHIRING",
            numRows: 3,
            expected: "PAHNAPLSIIGYIR"
        },
        {
            s: "PAYPALISHIRING",
            numRows: 4,
            expected: "PINALSIGYAHRPI"
        },
        {
            s: "A",
            numRows: 1,
            expected: "A"
        },
        {
            s: "AB",
            numRows: 1,
            expected: "AB"
        },
        {
            s: "ABC",
            numRows: 2,
            expected: "ACB"
        },
        {
            s: "ABCDEF",
            numRows: 3,
            expected: "AEBDFC"
        },
        {
            s: "ABCDEFGH",
            numRows: 4,
            expected: "AGBFHCE"
        }
    ];

    testCases.forEach((testCase, index) => {
        const result = convert(testCase.s, testCase.numRows);
        const passed = result === testCase.expected;
        console.log(`测试用例 ${index + 1}: ${passed ? '通过' : '失败'}`);
        console.log(`输入: s = "${testCase.s}", numRows = ${testCase.numRows}`);
        console.log(`期望: "${testCase.expected}", 实际: "${result}"\n`);
    });
};

// 运行测试
testConvert();

关键点总结

边界处理：当行数为1或字符串长度小于等于行数时直接返回
方向控制：使用direction变量控制当前行的移动方向
行数组：使用数组存储每一行的字符
字符添加：将字符添加到当前行
结果拼接：最后将所有行拼接成结果字符串

总结

这道题考察了以下重点：

模拟技巧：如何按照特定规律处理字符串
方向控制：理解Z字形的移动规律
数组操作：如何高效地管理多行数据
边界处理：对特殊情况的处理

模拟法是最优解，时间复杂度为 O(n)，空间复杂度为 O(n)。在实际面试中，建议先画出Z字形的规律，然后实现算法。

017-Z 字形变换 (ZigZag Conversion)

On this page