题目

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

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

L C I R E T O E S I I G E D H N

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

一. 按行添加

建立指定数目的数组，遍历字符串时依次添加，最后将数组连接为字符串。

js实现

/** * @param {string} s * @param {number} numRows * @return {string} */ var convert = function(s, numRows) { var numRowList = Array.from({ length:Math.min(numRows, s.length) }, () => []) var index = 0 while (index < s.length) { for (var i=0;i<numRowList.length;i++) { if (index < s.length) { numRowList[i].push(s[index++]) } else { break } } for (var j=numRowList.length-2;j>0;j--) { if (index < s.length) { numRowList[j].push(s[index++]) } else { break } } } return [].concat(...numRowList).join('') };

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

测试结果

✔ Accepted ✔ 1158/1158 cases passed (112 ms) ✔ Your runtime beats 87.09 % of javascript submissions ✔ Your memory usage beats 31.82 % of javascript submissions (42 MB)

二. 优化的按行添加

建立指定数目的字符串，遍历时依次将每个字符串连接新字符，遍历完成后返回建立的字符串连接后的字符串

js实现

/** * @param {string} s * @param {number} numRows * @return {string} */ var convert = function(s, numRows) { var numRowList = Array.from({ length:Math.min(numRows, s.length) }, () => "") var index = 0 while (index < s.length) { for (var i=0;i<numRowList.length;i++) { if (index < s.length) { numRowList[i] += s[index++] } else { break } } for (var j=numRowList.length-2;j>0;j--) { if (index < s.length) { numRowList[j] += s[index++] } else { break } } } return ''.concat(...numRowList) };

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

测试结果

✔ Accepted ✔ 1158/1158 cases passed (96 ms) ✔ Your runtime beats 97.55 % of javascript submissions ✔ Your memory usage beats 57.88 % of javascript submissions (38.4 MB)

三. 按行访问

依次访问每行中的字符串。

js实现

/** * @param {string} s * @param {number} numRows * @return {string} */ var convert = function(s, numRows) { if (numRows === 1) { return s } var result = '' var len = s.length var loopLen = 2 * numRows - 2 // 第一层 for (var j=0;j<len;j+=loopLen) { result += s[j] } // 中间层 for (var i=1;i<numRows-1;i++) { for (var j=0;j + i < len;j += loopLen) { result += s[j+i] if (j + loopLen -i < len) { result += s[j+loopLen-i] } } } // 最后一层 for (var j=numRows-1;j<len;j += loopLen) { result += s[j] } return result };

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

测试结果

✔ Accepted ✔ 1158/1158 cases passed (84 ms) ✔ Your runtime beats 99.93 % of javascript submissions ✔ Your memory usage beats 91.52 % of javascript submissions (37.7 MB)