之美 – 格安

“Z 字形变换”问题的 Javascript 解答


题目:

将一个给定字符串 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"

思考:

先找规律看看

0123456
0P[1]A[5]H[9]N[13]
1A[2]P[4]L[6]S[8]I[10]I[12]G[14]
2Y[3]I[7]R[11]
示例1,numRows = 3
0123456
0P[0]I[6]N[12]
1A[1]L[5]S[7]I[11]G[13]
2Y[2]A[4]H[8]R[10]
3P[3]I[9]
示例2,numRows = 4

设字符的下标为 n

梯度(t) = numRows + (numRows -2),以示例2为例,梯度为 4 + (4 – 2) = 6

计算列数(x) :

nt = Math.floor(n / t) 得到字符 n 在第 nt 个梯度内(从 0 开始计数),每个梯度包含 tx 列,tx = numRows – 1

n % t 将所有字符放在第一个梯度内考虑,有两种情况 :

n % t < numRows 时,x 等于 0 + s[n] 所在的梯度乘以梯的长度,即: x = 0 + nt x tx,整理后是 x = nt x tx

n % t >= numRows 时,也就是 s[n] 是在 “Z“ 字的折线位置的,放到第一个梯度里面看,x 应该就是 n % numRows 的值,属于其他梯度内的数,加上梯度即可,考虑到下标是从 0 开始的,所以 x = (((n % t) + 1) % numRows) + nt x tx;

计算行数(y)

行数的计算和列数的计算思路一样,把所有字符放到第一个梯度内考虑,而且不需要再加上梯度了。同样分两种情况:

n % t < numRows 时,n % t 将 s[n] 放到第一个梯度内考虑,行数 y = n % numRows ,考虑梯度,最终结果为:y = n % t % numRows。

n % t >= numRows 时,也就是计算 “Z” 字折线上的数字。n % t 将 s[n] 放到第一个梯度内考虑,观察 s[n] 的下标与行数的关系,可以得到 s[n] 不可能出现在第一行和最后一行,第一个梯度内,n + 1 – numRows 可得到 s[n] 到表格底部的距离,numRows – 1 再减去这个距离,就得到行数 y 了,因此结果为:y = numRows – 1 – ((n % t) + 1 – numRows)。

还有一种情况是 numRows === 1 的时候,实际上把原字符串直接输出就是了。

解答

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function (s, numRows) {
  var matrix = [];

  for (var y = 0; y < numRows; y++) {
    // 构建行
    matrix[y] = [];
  }

  // 梯度
  var t = numRows + numRows - 2;

  for (var n = 0; n < s.length; n++) {
    // 测试列的判断逻辑是否正确

    // 初始化列位置
    var x = 0;

    // 初始化行位置
    var y = 0;

    // 得到元素在哪个梯度内
    var nt = Math.floor(n / t);

    // 每个梯度占据的列数
    var tx = numRows - 1;

    if (n % t < numRows) {
      x = 0 + nt * tx;
      y = (n % t) % numRows;
    } else {
      x = (((n % t) + 1) % numRows) + nt * tx;
      y = numRows - 1 - ((n % t) + 1 - numRows);
    }

    matrix[y][x] = s[n];
  }

  var result = "";

  matrix.forEach(function (element) {
    element.forEach(function (item) {
      if (item) result = result.padEnd(result.length + 1, item);
    });
  });

  return result;
};

题目来源:力扣(LeetCode)

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