06. Z 字形变换

题目描述

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

题解

解法一：矩阵模拟

若模拟矩阵类型为 vector<vector<char>> 则需要先计算矩阵列数 col。根据 Z 字形填充规则，得到填充周期为 (row+row-2) 个字符，一个周期为 (row - 1) 列，因此列数为 (s.size() / (row + row - 2) + 1) * (row -1)。由于字符数不一定是周期的整数倍，计算周期数是需要向上取整，将最后一个周期视作完整周期。

另外设置一个填充次数 cnt，每当填充 (row - 1) 个字符时，填充方向改变，cnt++ ，填充方向由 cnt 奇偶性进行判断，奇数时填充方向为向下，偶数时填充方向为向上。

string convert2(string s, int numRows) {
  if (s.size() < 2 || numRows == 1 || s.size() <= numRows) return s;
  int col = s.size() / 2 + numRows - 1;
  vector<vector<char>> mat(col, vector<char>(numRows, '\0'));
  int x = 0, y = 0, cnt = 1;
  for (int i = 0; i < s.size(); i++) {
    mat[x][y] = s[i];
    if (i % (numRows - 1) == 0 && i != 0) {
      cnt++;
    }
    if (cnt % 2 == 0) {
      x++;
      y--;
    } else {
      y++;
    }

  }
  x = y = 0;
  std::string res;
  for(y = 0; y < numRows; y++) {
    for(x = 0; x < col; x++) {
      if (mat[x][y] != '\0') {
        res += mat[x][y];
      }
    }
  }
  return res;
}

解法二：压缩矩阵

当 numRows 较大时，解法一存在大量的冗余空间，且使用 vector<vector<char>> 需优先计算列数 col。

因此在解法二中，使用 vector<string> 按行申请空间。由于最终读取时忽略空白字符，所以直接将当前行字符追加到字符串尾部即可，消除冗余的空白空间。

由于不需要计算列数，因此在填充时仅需要记录当前行数 row 即可，当 row == 0 或 row == numRows - 1 时，填充方向翻转。翻转的方法极为巧妙：每次填充字符时，行数 row 存在两种情况，+1 或者 -1，所以设置一个标记 k = 1，在 row 符合翻转条件时，将 k 取反，即 k = -k，此时 只需要 row += k 即可完成行号的更新。

string convert(string s, int numRows) {
  if (s.size() < 2 || numRows == 1 || s.size() <= numRows) return s;
  vector<string> mat(numRows, "");
  int row = 0, k = 1;
  for(char c:s) {
    mat[row] += c;
    row += k;
    if (row == 0 || row == numRows - 1) {
      k = -k;
    }
  }
  string res;
  for(auto &t:mat) {
    res += t;
  }
  return res;
}

总结

1. 矩阵模拟，计算填充模式下的周期，和找到坐标更新模式的拐点；
2. 根据题意无视空白字符，因此可直接按行追加字符，无需留出空白位置，压缩矩阵，节省空间