JavaScript解决LeetCode算法题（6）——《Z 字形变换 》

题目

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

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

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

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

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

string convert(string s, int numRows);

示例1：

输入: s = “LEETCODEISHIRING”, numRows = 3 输出: “LCIRETOESIIGEDHN”

示例2：

输入: s = “LEETCODEISHIRING”, numRows = 4 输出: “LDREOEIIECIHNTSG” 解释：

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

解题

方法1：

我们发现循环规律是2*n-2，然后把每个的字符分配到对应行，最后相加起来作为结果返回，代码：

/** * @param {string} s * @param {number} numRows * @return {string} */ var convert = function(s, numRows) { if(numRows === 1) { return s; } let a = []; let str = ''; // 初始化数组，否则开头会是undefined for(let i = 0; i < numRows; i++) { a[i] = ''; } // 除以循环数，按照余数减去中间数的绝对值然后分到各个行中 for(let i = 0; i < s.length; i++) { let index = Math.abs(i%(2*numRows-2) - (numRows-1)); a[index] += s[i]; } for(let j = numRows-1; j >= 0; j--) { str += a[j]; } // return a; return str; };

执行结果：

方法2：

我们发现第一个方法，执行速度还可以，但是占用空间比较大，我们来进行优化，将其遍历访问时直接将对应的字符拼接起来，贴代码：

/** * @param {string} s * @param {number} numRows * @return {string} */ var convert = function(s, numRows) { var len = s.length; var twoRows = 2*numRows - 2; var str = ''; if(len == 0 || numRows <= 1) { return s; } for(i = 0; i < numRows; i++){ for(j = i; j < len; j += twoRows){ str += s[j]; if(i != 0 && i != numRows - 1 && j - 2*i + twoRows < len){ str += s[j - 2*i + twoRows]; } } } return str; };

执行结果： 这里优化并不是那么明显，其实还是有空间换时间的成分。

上面两种算法的时间复杂度都是O（n）。

结语

以上是我对此题的解法，如果有小伙伴有更好的方式，或者非常有趣的思维方式，欢迎一起交流讨论。

希望此文能够解决大家工作和学习中的一些疑问，避免不必要的时间浪费，有不严谨的地方，也请大家批评指正，共同进步！

转载请注明出处，谢谢！