问题
今天开始在leetcode刷算法题,遇到这样一道题,题目看上去就有点好玩,就进去试了一下:
将一个给定字符串 s 根据给定的行数 numRows ,以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时,排列如下:
P A H N A P L S I I G Y I R
输出结果就是"PAHNAPLSIIGYIR“
思路
最开始,对这样的题目有一丝丝摸不到头脑,于是希望可以从这个z字形排列出的结果中找到一些规律。
既然要找规律,我假定一个字符串:HELLOGEPINGLI
网络异常,图片无法展示
|
那结果如上面所示,应该是HEI(第一行对应的字符串)+EGPL(第二行对应的字符串)+LOIG(第三行对应的字符串)+LN(第四行对应的字符串)
于是现在我们有了第一个想法,我们弄一个数组,ROWS,有几行,这个数组就有几项。
下面,我们就需要研究下一个问题点了,我们如何去确定每一行对应的字符串是什么,所以,还是要找一找规律。
首先,我们一看就可以轻松的发现,4行的情况下,是每6个字符一个循环。如下图所示,循环周期是2*numRows-2。
网络异常,图片无法展示
|
为什么是2*numRows-2呢,也很容易。看下面的图可以明白,两倍的行数,再去掉头尾两个。
网络异常,图片无法展示
|
下面,我们继续以之前四行的例子继续看 字符会出现在哪一行的规律。
网络异常,图片无法展示
|
上图,position代表的是字符在原字符串中的位置,6是2*numRows-2的计算结果(2*4-2=6)。我们不难的发现,行数其实是position%(2*numRows-2)和(2*numRows-2)-position%(2*numRows-2)的最小值。
那么这样问题就可以很顺利的解决了。
代码
var convert = function(s, numRows) { if (numRows === 1) return s; const rows = new Array(numRows).fill(""); const period = 2 * numRows - 2; for(let i = 0; i < s.length; i++) { rows[Math.min(i % period, period - i % period)] += s[i]; } return rows.join(""); };
网络异常,图片无法展示
|