6. N 字形变换

题目

特殊情况

当numRows为一时，直接返回字符串，因为所有字符都在同一行。

相反，如果numRows大于字符串长度时，每一行只有一个字符，按顺序拼接起来和原字符串一样，直接返回字符串。

思路一 矩阵模仿N字形遍历

给一个长度为numRows的二维数组记录，遍历字符串，把字符放到对应的数组中，然后平铺数组并组合成字符串即可。

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
function convert(s, numRows) {
  // 特殊情况
  if (numRows === 1 || numRows >= s.length) return s;
  // 构造矩阵
  let matrix = Array.from({ length: numRows }, () => []);
  // N字走向
  let direction = true;
  // 对应位置
  let idx = 0;

  for (let val of s) {
    // 字符放到对应位置
    matrix[idx].push(val);

    // 根据走向判断对应位置的变化
    if (direction) {
      idx += 1;
    } else {
      idx -= 1;
    }
    // 根据对应位置判断走向的变化
    if (idx === 0) direction = true;
    if (idx === numRows - 1) direction = false;
  }

  // 这里es6提供了平铺数组的方法，原本应该是遍历二维数组。
  return matrix.flat(Infinity).join('');
};

复杂度

时间复杂度：假设字符串长度为n，二维数组的列数numRows为r，其中有遍历字符串O(n)，加上后面遍历矩阵O(rn)，然后去除常数、系数、低阶得出时间复杂度为O(rn)。

空间复杂度：矩阵二维数组O(rn)。

思路二 构造

很明显N字形成了一个周期性的结构，有以下特征，以示例2为例：

1. 从第一行第一个（P）到第二行第二个（L），又或者从第一行第二个（I）到第二行第四个（I）。周期长度为6（2*numRows - 2）。
2. 每个周期中，除了第一行和最后一行有一个元素，中间的其余行都有两个元素。比如从第一行第一个（P）到第二行第二个（L），第一行只有一个P，最后一行只有一个P，第二行有A/L，第三行有Y/A。

思路：利用周期性用for循环遍历特定的列，如示例2中的第一、第四、第七列，而中间第二第三第五第六列都只有一个元素，对应的是上述特征2的中间行多出来的一个元素。

这里有第三个特性，比如遍历到第二行第三个（S），第二行下标为1，而按字符串的顺序来说，由A的位置，加一个周期到达A的位置，再减2*1，到达L的位置正是同一周期中同一行的另一个字符。

根据以上三个特性可以覆盖所有的字符并进行编码了：

var convert = function (s, numRows) {
  const n = s.length, r = numRows;
  // 特殊情况
  if (r === 1 || r >= n) return s;
  // 周期长度
  const t = r * 2 - 2;
  let ans = '';
  // 枚举矩阵的行
  for (let i = 0; i < r; i++) {
    // 枚举矩阵的特定列
    for (let j = i; j < n; j += t) {
      ans += s[j];
      // 是否非第一行和非最后一行，是否存在同一个周期中的第二个元素，并且不超出字符串长度
      if (0 < i && i < r - 1 && j + t - 2 * i < n) {
        // 当前周期的第二个字符
        ans += s[j + t - 2 * i];
      }
    }
  }
  return ans;
};

复杂度

时间复杂度：两层循环几乎把s的所有字符都覆盖了一遍，并且在寻找同一周期的第二个元素的时候存在if判断，所以最坏的情况则是O(n)，n为字符串s的长度。

空间复杂度：只用了常数个额外空间，O(1)。