6. Z 字形变换

原文题目

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

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

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

https://leetcode.cn/problems/zigzag-conversion/description/

题目分析

比如输入字符串为 PAYPALISHIRING 行数为 3 时。输出结果就是 PAHNAPLSIIGYIR ，排列如下：

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

比如输入字符串为 PAYPALISHIRING 行数为 4 时，输出结果就是 PINALSIGYAHRPI，排列如下：

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

所以我们需要做的事情就是将字符串进行 Z 字形排列，然后在将每一行的字符串进行拼接，得到最终的结果。

题解思路

方式一：通过迭代方式实现

我们可以定义一个空数组，数组的长度根据行数 numRows 来决定，然后遍历字符串 PAYPALISHIRING ，将它们挨个添加到数组中，得出以下的效果图。

最后再将数组的每一行进行拼接，拼接后的字符串就是我们的结果。当我们遍历字符串时，前面四个字符 PAYP，我们可以很简单的就把它添加到数组的 0 1 2 3 下标中。但是字符 A 的下标是 4 显然是不对的，因为我们数组没有这么长。所以这道题的难点在于，要将这个下标 4 纠正为下标 2

时间复杂度：O(n)

空间复杂度：O(1)

const convert = function (s, numRows) {
    if (numRows === 1) return s

    // 获取有规律的长度
    const len = numRows * 2 - 2

    // 创建一个空数组
    const rows = new Array(numRows).fill('')

    // 向空数的每一项组插入字符串
    for (let i = 0; i < s.length; i++) {
        const n = i % len
        const row = Math.min(n, len - n)

        rows[row] += s[i]
    }

    // 将数组转换为字符串返回
    return rows.join('')
}

convert('PAYPALISHIRING', 4) // PINALSIGYAHRPI

思路分析

1. 首先创建一个空数组 rows ，长度为 numRows

2. 遍历字符串 PAYPALISHIRING ，按照字符串顺序挨个添加到数组中。

3. 在添加的过程中，数组的最大长度是 4，也就是说添加的字符不能根据原始的下标进行，否则会溢出数组长度。

4. 所以需要对每一个字符的下标重新处理。

5. 通过下图可找出规律，可将每一个 V 字形划分为一组。每一组的长度为 6 即 numRows * 2 - 2 = 6 。长度相当于是两列长度在减去头尾。

6. 通过余数 % 为每一组字符重新标记上索引。

7. 由上图可发现，下标 4 5 是不正确的，但是可发现规律，通过 6 减去它们得到的数值则是正确的。

8. 所以还需要用 6 减去每一个用余数求出来的数值，再取最小值。

9. 最后成功添加到数组中

10. 将每一行的字符进行拼接，则完成这道题了。PIN + ALSIG + YAHR + PI