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

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

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

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

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

string convert(string s, int numRows);

示例 1：

输入：s = “PAYPALISHIRING”, numRows = 3

输出：”PAHNAPLSIIGYIR”

示例 2：

输入：s = “PAYPALISHIRING”, numRows = 4

输出：”PINALSIGYAHRPI”

解释：

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

示例 3：

输入：s = “A”, numRows = 1

输出：”A”

提示：

  • 1 <= s.length <= 1000
  • s 由英文字母（小写和大写）、’,’ 和 ‘.’ 组成
  • 1 <= numRows <= 1000

思路

观察一下这个字符串Z字型排列，有点像正弦函数，每次都是先向下，然后再往上，到达顶部之后，又开始往下，直至全排完。那么其实我们只需要创建一个数组，这个数组中的每个元素就是排列完后的每行，每有一个字符进来，就将其加到对应的字符串中。那么如何知道应该放到哪个元素中呢？

可以看到每次都是排到numRows - 1(行数从0开始，即最后一行)行的时候，方向进行了反转，然后再到0行(视觉上的第一行)的时候，又再次发生反转，那么其实仅仅需要设置一个增量标记假设为1，行数从0开始，把对应index的值放到对应的字符串中，然后行数加上这个标记，等行数到了最后一行的时候，就将这个标记置反，每次就都是加上-1，等到了第一行，再把标记置反，循环往复，数组中的字符串就将对应的字符都加进去了，最后把数组中的字符串做一下拼接即可。

流程演示

示例1：s = “PAYPALISHIRING”, numRows = 3

创建一个数组arr，数组中有3个元素，每个元素都是””，增量标记为-1，初始行为0

  1. “P”，加入arr[0]中，arr为[“P”, “”, “”] ，到达0行，增量标记置反为1，行数+标记 = 1
  2. “A”，加入arr[1]中，arr为[“P”, “A”, “”]，到达1行，行数+标记 = 2
  3. “Y”，加入arr[2]中，arr为[“P”, “A”, “Y”]，到达2行，增量标记置反为-1，行数+标记为 = 1
  4. “P”，加入arr[1]中，arr为[“P”, “AP”, “Y”]，到达1行，行数+标记 = 0
  5. “A”，加入arr[0]中，arr为[“PA”, “AP”, “Y”] ，到达0行，增量标记置反为1，行数+标记 = 1
  6. “L”，加入arr[1]中，arr为[“PA”, “APL”, “Y”] ，到达1行，行数+标记 = 2
  7. “I”，加入arr[2]中，arr为[“PA”, “APL”, “YI”] ，到达2行，增量标记置反为-1，行数+标记为 = 1
  8. “S”，加入arr[1]中，arr为[“PA”, “APLS”, “YI”] ，到达1行，行数+标记 = 0
  9. “H”，加入arr[0]中，arr为[“PAH”, “APLS”, “YI”] ，到达0行，增量标记置反为1，行数+标记 = 1
  10. “I”，加入arr[1]中，arr为[“PAH”, “APLSI”, “YI”] ，到达1行，行数+标记 = 2
  11. “R”，加入arr[2]中，arr为[“PAH”, “APLSI”, “YIR”] ，到达2行，增量标记置反为-1，行数+标记为 = 1
  12. “I”，加入arr[1]中，arr为[“PAH”, “APLSII”, “YIR”] ，到达1行，行数+标记 = 0
  13. “N”，加入arr[0]中，arr为[“PAHN”, “APLSII”, “YIR”] ，到达0行，增量标记置反为1，行数+标记 = 1
  14. “G”，加入arr[1]中，arr为[“PAHN”, “APLSIIG”, “YIR”] ，到达1行，行数+标记 = 2
  15. 没有更多字符了，将arr中的字符串拼接得到”PAHNAPLSIIGYIR”

示例1：s = “PAYPALISHIRING”, numRows = 4

创建一个数组arr，数组中有4个元素，每个元素都是””，增量标记为-1，初始行为0

  1. “P”，加入arr[0]中，arr为[“P”, “”, “”, “”] ，到达0行，增量标记置反为1，行数+标记 = 1
  2. “A”，加入arr[1]中，arr为[“P”, “A”, “”, “”]，到达1行，行数+标记 = 2
  3. “Y”，加入arr[2]中，arr为[“P”, “A”, “Y”, “”]，到达2行，行数+标记为 = 3
  4. “P”，加入arr[3]中，arr为[“P”, “A”, “Y”, “P”]，到达3行，增量标记置反为-1, 行数+标记 = 2
  5. “A”，加入arr[2]中，arr为[“P”, “A”, “YA”, “P”] ，到达2行，行数+标记 = 1
  6. “L”，加入arr[1]中，arr为[“P”, “AL”, “YA”, “P”] ，到达1行，行数+标记 = 0
  7. “I”，加入arr[0]中，arr为[“PI”, “AL”, “YA”, “P”] ，到达0行，增量标记置反为1，行数+标记为 = 1
  8. “S”，加入arr[1]中，arr为[“PI”, “ALS”, “YA”, “P”] ，到达1行，行数+标记 = 2
  9. “H”，加入arr[2]中，arr为[“PI”, “ALS”, “YAH”, “P”] ，到达2行，行数+标记 = 3
  10. “I”，加入arr[3]中，arr为[“PI”, “ALS”, “YAH”, “PI”] ，到达3行，增量标记置反为-1, 行数+标记 = 2
  11. “R”，加入arr[2]中，arr为[“PI”, “ALS”, “YAHR”, “PI”] ，到达2行，行数+标记 = 1
  12. “I”，加入arr[1]中，arr为[“PI”, “ALSI”, “YAHR”, “PI”] ，到达1行，行数+标记 = 0
  13. “N”，加入arr[0]中，arr为[“PIN”, “ALSI”, “YAHR”, “PI”] ，到达0行，增量标记置反为1，行数+标记 = 1
  14. “G”，加入arr[1]中，arr为[“PIN”, “ALSIG”, “YAHR”, “PI”] ，到达1行，行数+标记 = 2
  15. 没有更多字符了，将arr中的字符串拼接得到”PINALSIGYAHRPI”

代码

var convert = function(s, numRows) {
  if (numRows < 2) { //如果行数小于2 那么就是一条直线，直接返回原字符串即可
    return s
  }

  //创建一个数组，每个元素是行
  const sizeArr = new Array(numRows).fill('')

  //每过 numRows - 1次为一轮，到达边界将标志置反，用当前index对term求模，如果为0，即到了边界
  const term = numRows - 1

  //初始行
  let currentRow = 0
  //每次循环增加的量
  let addVar = -1

  for (let index = 0; index < s.length; index++) {
    sizeArr[currentRow] += s[index]   //将字符添加到对应的数组元素中去
    if (index % term  === 0) { //如果到达边界 将标志位置反
      //到达转折点
      addVar = -addVar
    }
    currentRow += addVar  //用当前行数 + 标志位，即可完成向下移动或者向上移动
  }

  return sizeArr.join('') //最后将数组内的字符串拼接得到结果
};