ZigZag Conversion - LeetCode JavaScript

不念不忘少年蓝@ 2022-02-25 06:39 150阅读 0赞

## 题目 ##

> The string " PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
    A P L S I I G
    Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"  
Write the code that will take a string and make this conversion given a number of rows:  
string convert(string text, int nRows);  
convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

--------------------

## 题目解释 ##

假设我们输入的就是上面的字符串,在numRows取不同值的时候,大家看我用Excel做的简易的图:

![clipboard.png][]  
看完图应该就明白了这个题目到底是什么意思,这个题的难点在于找规律,只要找到了规律,解决这个题并不难.  
规律如下:

*  第一行或者最后一行,元素之间的间隔(distance)为  
    2 \* nRows - 2;
 *  中间部分间隔分别是:  
    distace - 2*i, 2*  i, distance - 2*i, 2*i...
    
    依照上面规律,代码如下

/**
     * @param {string} s
     * @param {number} numRows
     * @return {string}
     */
    var convert = function(s, numRows) {
        if (numRows <= 1)
            return s;
        let res = '';
        let len = s.length;
        let dis = numRows*2 - 2;
        
        /* first row */
        for (let i = 0; i < len; i+=dis) {
            res += s.charAt(i);
        }
        
        /* middle */
        for (let i = 1; i < numRows-1; i++) {
            let tempDis = 2*i;
            for (let j = i; j < len; j += tempDis) {
                res += s.charAt(j);
                tempDis = dis - tempDis;
            }
        }
        
        /* last row */
        for (let i = numRows-1; i< len; i += dis) {
            res += s.charAt(i);
        }
        return res;
    };

[clipboard.png]: /images/20220225/1fa64d98699f48bfa173d95da9116bc3.png