原题地址：Z字形变换
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "LEETCODEASHARANG" 行数为 3 时，排列如下：
L C A R
E T O E S A A G
E D H N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCARETOESAAGEDHN"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例 1:
输入: s = "LEETCODEASHARANG", numRows = 3
输出: "LCARETOESAAGEDHN"
示例 2:
输入: s = "LEETCODEASHARANG", numRows = 4
输出: "LDREOEAAECAHNTSG"
解释:L D R
E O E A A
E C A H N
T S G
按行读取
我们将第一行的一个字符到下一个字符之间的部分当作一次循环，如第一个例子中LEET、CODE、ASHA、RANG分别为一个循环。通过寻找规律，我们可以发现每个循环中的第一行和最后一行都只有一个字符，中间的行则有两个字符，这两个字符之间的间隔的字符为（numRows-n)*2-1，其中n为行号。因为垂直部分剩下的字符一定为numRows-n，斜着的部分则要少一个，最后一行没有斜着的字符。
按照这个规律，我们可以按行定位到所有的字符：
/**
* @param {string} s
* @param {number} numRows
* @return {string}
*/
const convert1 = function(s, numRows) {
if (numRows < 2) {
return s;
}
let result = '';
// 按行读取
for (let i = 0; i < numRows; i++) {
let index = i;
while (index < s.length) {
result += s[index]; // 垂直那一列的字符，所有行都有
// 除了第一行和最后一行，其它行会多一个字符
if (i > 0 && i < numRows - 1) {
let next = index + (numRows - i - 1) * 2;
if (next < s.length) { // 判断边界
result += s[next];
}
}
// 一个循环的总字符数为numRows * 2 - 1，垂直为numRows，斜着的少一个
index += (numRows - 1) * 2
}
}
return result;
};
测试：
let start = new Date();
const test = convert1;
console.log(test('LEETCODEISHIRING', 3)); // LCIRETOESIIGEDHN
console.log(test('LEETCODEISHIRING', 4)); // LDREOEIIECIHNTSG
console.log(test('A', 1)); // A
console.log(new Date().getTime() - start.getTime()); // 5
时间复杂度： 只需要遍历一次，时间复杂度为O(n)
空间复杂度： 需要一个字符串存储结果，空间复杂度为O(n)
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Jul 27,2019