# 6.ZigZag Conversion <span class='tag' data-diff='medium'></span>
{%hackmd RN5D4nggQRO8wzNqxuvlNw %}

## 題目
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 s, int numRows);

**Example 1:**

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

**Example 2:**

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

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

## 思路
這題其實滿有趣的，有點像在做加密的感覺。對於這種有規律性的題目，最重要的就是先找到他們的規律性，把`numRows`為3、4、5、6的情況寫出來後，就發現它的規律如下:
- 第一列的間隔與最後一列的index間隔是 $2(n-1)$
- 中間其他列的間隔則是兩個數交替
- 這兩個數在第 $k$ 列為 $2(n-k)$ 、 $2k$，而第一列也可以視為 $k=0$ 與 $k=n$ 的特殊情況
- 每一列第一個數為 $k\ mod\ n$

所以先宣告一個生成indices的函數，給予每一列的兩個間隔，還有起始編號與字串長度，就可以回傳一串indices。

const getIndices = (a, b, min, max) => {
    let flag = true,
        indices = [];

    do{
        if(!indices.includes(min)) indices.push(min);
        min += flag ? a : b;
        flag = !flag;
    }while(min < max);

    return indices;
}

接者loop過每一列，把所有生成的indices接起來，就可以得到答案想要的字串排序順序

let k = numRows - 1,
    zigIndices = [];

for(let i = 0; i <= k; i++){
    let indices = getIndices((k-i) * 2, i * 2, i, s.length);
    zigIndices = zigIndices.concat(indices);
}

之後，在return時，只要依照這個陣列裡面的index，就可以做出重組的字串了

s = s.split("");    
return zigIndices.map(i => s[i]).join("");

此外，一開始可以先判斷一些例外情況，像是`numRows`只有1，或是字串長度小於`numRows`時，可以直接回傳該字串。