Skip to main content

z-字形变换

题目​

将一个给定字符串 s 根据给定的行数 numRows, 以从上往下, 从左到右进行 Z 字形排列. 比如输入字符串为 "PAYPALISHIRING" 行数为 3 时, 排列如下:

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

之后, 你的输出需要从左往右逐行读取, 产生出一个新的字符串, 比如: "PAHNAPLSIIGYIR".

提示:
  • 1 <= s.length <= 1000
  • s 由英文字母(小写和大写), ',' 和 '.' 组成
  • 1 <= numRows <= 1000
示例

输入: s = "PAYPALISHIRING", numRows = 4

输出: "PINALSIGYAHRPI"

解释:

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

题解​

以 s = "PAYPALISHIRING", numRows = 4 为例, 把 Z 字形数字转换成索引排列, 然后我们来找规律.

0       6        12
1    5  7     11 13
2  4    8  10
3       9

我们从第一排可以看到循环的数字跟 6 有关, 因此可以以 6 为突破口试试:

  • 第一排 0 % 6 = 0; 6 % 6 = 0; 12 % 6 = 0. 可以看到取余都是 0, 即可根据余数判断这几个字母是第一排.
  • 第二排 1 % 6 = 1; 5 % 6 = 5; 7 % 6 = 1; 11 % 6 = 5; 13 % 6 = 1. 可以看到余数都是 1 或者 5, 对于 5, 可以通过 6 - 5 变成 1.
  • 第三排 2 % 6 = 2; 4 % 6 = 4; 8 % 6 = 2; 10 % 6 = 4. 可以看到余数都是 2 或者 4, 对于 4, 可以通过 6 - 4 变成 2.
  • 第四排 3 % 6 = 3; 9 % 6 = 3. 可以看到取余都是 3, 即可根据余数判断这几个字母都是第三排.

当然这个 6 是怎么来的呢? 即 (numRows - 1) * 2.

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function (s, numRows) {
  // 如果 numRows 比 2 小, 是没法变成 Z 型的, 直接返回 s 即可
  if (numRows < 2) return s

  const n = s.length

  // 初始化一个数组, 数组长度为 numRows
  const res = Array(numRows).fill('')

  // 循环, 也就是示例中的 6
  const cycle = (numRows - 1) * 2

  for (let i = 0; i < n; i++) {
    // 计算余数
    const carry = i % cycle

    // 计算索引, 如果余数小于 numRows, 那就用这个余数即可, 否则用循环数减去该余数
    const idx = carry < numRows ? carry : cycle - carry

    res[idx] += s[i]
  }

  // 最后把数组合并成字符串即可
  return res.join('')
}