6. Z 字形变换
原文题目
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串。
请你实现这个将字符串进行指定行数变换的函数。
题目分析
比如输入字符串为 PAYPALISHIRING 行数为 3 时。输出结果就是 PAHNAPLSIIGYIR ，排列如下：
P A H N
A P L S I I G
Y I RP 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 IP 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)
js
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) // PINALSIGYAHRPIconst 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思路分析
- 首先创建一个空数组
rows，长度为numRows
- 遍历字符串
PAYPALISHIRING，按照字符串顺序挨个添加到数组中。
- 在添加的过程中，数组的最大长度是
4，也就是说添加的字符不能根据原始的下标进行，否则会溢出数组长度。
- 所以需要对每一个字符的下标重新处理。
- 通过下图可找出规律，可将每一个
V字形划分为一组。每一组的长度为6即numRows * 2 - 2 = 6。长度相当于是两列长度在减去头尾。
- 通过余数
%为每一组字符重新标记上索引。
由上图可发现，下标
45是不正确的，但是可发现规律，通过6减去它们得到的数值则是正确的。所以还需要用
6减去每一个用余数求出来的数值，再取最小值。
- 最后成功添加到数组中
- 将每一行的字符进行拼接，则完成这道题了。
PIN + ALSIG + YAHR + PI