6. Z 字形变换

链接：https://leetcode-cn.com/problems/zigzag-conversion/

题目描述见链接内容。

解法1：二维数组

看了一阵子题目，才看明白，所谓的Z字形排列是一个放倒了的Z

想到了用二维数组解决，把所有信息按照规律填入到二维数组中即可，具体的逻辑在代码注释中：

var convert = function (s, numRows) {
  if (numRows === 1) {
    return s;
  }

  const temp = [];
  // i代表列，j代表行
  let result = '',
    i = 0,
    j = 0;

  while (i + i + j < s.length) {
    // 竖着的那一列
    if (i % (numRows - 1) === 0) {
      // 把这一列填满
      while (j < numRows) {
        if (!Array.isArray(temp[j])) {
          temp[j] = [];
        }
        // 取值规律，用归纳法就可以得到
        temp[j][i] = s[i + i + j];
        j++;
      }
      // 填满之后，需要回撤两行，才可以回到倒数第二行
      j -= 2;
    } else {
      // Z的斜边，每一列只填充一个数组
      if (!Array.isArray(temp[j])) {
        temp[j] = [];
      }
      temp[j][i] = s[i + i + j];
      // 向上回撤一行
      j--;
    }
    i++;
  }

  // 把得到二维数组连接起来
  for (let i = 0, len = temp.length; i < len; i++) {
    const row = temp[i];
    for (let j = 0, len2 = row.length; j < len2; j++) {
      if (temp[i][j]) {
        result += temp[i][j];
      }
    }
  }

  return result;
};

• 时间复杂度：${O(N)}$
• 空间复杂度：${O(N)}$
• 执行用时：124ms, 在所有JavaScript提交中击败了51%的用户，内存消耗：45MB，在所有JavaScript提交中击败了17%的用户

解法2：按行排序

看了官方题解，发现需要智商的方法，智商不够，所以想不到也正常。

最后我们的目标是按行打印，所以将Z自行的每一行分别存储，用一个变量curRow来表示当前遍历到哪一行，把对应的字符放进去，用一个变量goingDown来表示改向下一行还是该向上一行

用图解特别清晰直观：

具体代码实现如下：

var convert = function (s, numRows) {
  if (numRows === 1) {
    return s;
  }

  const rows = [];
  let goingDown = true,
    curRow = 0;

  for (let i = 0, len = s.length; i < len; i++) {
    // 拼接到对应的行中
    rows[curRow] = (rows[curRow] ? rows[curRow] : '') + s[i];
    // 根据 goingDown 决定继续向下还是向上
    curRow = curRow + (goingDown ? 1 : -1);

    // 到了第一行或者最后一行才会改变方向（注意是行，不是列）
    if (curRow === 0 || curRow === numRows - 1) {
      goingDown = !goingDown;
    }
  }

  return rows.join('');
};

• 时间复杂度：${O(N)}$
• 空间复杂度：${O(N)}$
• 执行用时：104ms, 在所有JavaScript提交中击败了93%的用户，内存消耗：41.9MB，在所有JavaScript提交中击败了71%的用户