Leetcode - Medium - 6. Zigzag Conversion - Javascript

Leetcode - Medium - 6. Zigzag Conversion - Javascript

   清晨7:21       Rain Lin

---

6. Zigzag Conversion

Medium

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"







解題方向：

1. 這題的關鍵是要透過 mod 方式找出倒 N 型規則

2. 要排除 mod 是 0 or 1 的情況, 直接回傳 s

3. 倒 N 的 mod 數是 (numRow -1)x2

4. mod 後計算出的值如果大於 numRow -1, 就是反轉順序

5. 反轉順序的 mod 為 numRow -1

6. 反轉順序的 index 為 反轉mod - (第一次mod值 % 反轉mod)

7. 時間複雜度為 O(n)

程式碼 ：

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function(s, numRows) {
    const stringList = [];
    const stringLen = s.length;
    const modNum = (numRows - 1) * 2;
    const revertModNum = numRows - 1;
    
    if (modNum <= 1) { return s;};
    
    for (let i = 0; i < stringLen; i++) {
        const index = i % modNum;
        let arrayIndex;
        
        if (index > revertModNum) {
            arrayIndex = revertModNum - (index%revertModNum);
        } else {
            arrayIndex = index;
        }
        stringList[arrayIndex] = stringList[arrayIndex] ? stringList[arrayIndex] + s[i] : s[i];
    }
    
    return stringList.join('');
};

執行成果：

高手解題：

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function(s, numRows) {
    if(numRows === 1) {
        return s;
    }
    const result = new Array(numRows).fill('');
    let i = 0;
    let count = 0;
    let dir = false;
    while(i < s.length) {
        if(i % (numRows-1) === 0) dir = !dir
        result[count] += s[i];
        dir ? count++ : count--
        i++;
    }
    
    return result.join('');
};


透過取餘數為零時反轉 dir 指標

並針對對應的 couter 寫入對應的 array string

減少 mod 計算數量與複雜度