「每日LeetCode」2022年3月1日

本文最后更新于：2023年3月19日 晚上

6.Z 字形变换

6.Z 字形变换

Category Difficulty Likes Dislikes
algorithms Medium (51.06%) 1528 -

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

Discussion | Solution

思路

使用二维矩阵模拟生成，分为两块，一个为竖向一个为斜向，实时根据每行的下标更新对应的状态即可。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/*
 * @lc app=leetcode.cn id=6 lang=javascript
 *
 * [6] Z 字形变换
 */

// @lc code=start
/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function (s, numRows) {
  if (numRows === 1) return s;

  const matrix = new Array(numRows);

  // 每一组的元素个数
  const groupLength = numRows + numRows - 2;
  // 每一组需要的纵向长度
  const groupColLength = 1 + numRows - 2;
  // 完整组的个数
  const groupCount = Math.floor(s.length / groupLength);
  // 最后一组剩余元素的个数
  const lastGroupRestCount = s.length % groupLength;
  // 每行的元素个数
  const colNum =
    groupCount * groupColLength +
    (lastGroupRestCount <= lastGroupRestCount ? 1 : 1 + groupLength - numRows);

  for (let i = 0; i < matrix.length; i++) {
    matrix[i] = new Array(colNum).fill("");
  }
  let flag = true,
    i = 0,
    j = 0,
    cur = 0;
  while (cur < s.length) {
    const char = s[cur++];
    if (flag) {
      matrix[i][j] = char;
      if (i === numRows - 1) {
        i--;
        j++;
        if (numRows > 2) flag = false;
        continue;
      }
      i++;
    } else {
      matrix[i][j] = char;
      if (i === 1) {
        i = 0;
        j++;
        flag = true;
        continue;
      }
      i--;
      j++;
    }
  }
  return matrix.map((row) => row.join("")).join("");
};
// @lc code=end