字符串Z字形变换

发表于 | 阅读次数: |

题目：将字符串 “ACSDEGBSLSGJSLA” 以Z字形排列成给定的行数，如下变换成3行Z字形排列：

1
2
3
A   E   L   S
C D G S S J L
S   B   G

之后，从左往右，从上往下逐行读取字符，得到：”AELSCDGSSJLSBG”。

示例1：

1
2
输入: s = "PAYPALISHIRING", numRows = 3
输出: "PAHNAPLSIIGYIR"

示例2：

1
2
3
4
5
6
7
8
输入: s = "PAYPALISHIRING", numRows = 4
输出: "PINALSIGYAHRPI"
解释:

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

解法：
按行排序：需要排成多少行即定义一个多少行的数组(3行为例：[[],[],[]])，通过从左向右依次迭代字符串，将每个字符依次放入(push)到指定的行中；另外，通过一个状态值控制方向；最终，得到的一个Z字形循环路径大致如下：

1
2
3
0   0   0   0
1 1 1 1 1 1 1
2   2   2

字符串从左到右循环过程中，根据行数定义的数组插入Z字形数据的路径如上，第一列从上到下，第二列从下到上，第三列从上到下……依次处理，最后得到代码：

CODE

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
function convertStrHandler(strData, numRows) {
  let strDataLen = strData.length,
      arrayList = [];

  if (numRows === 1) return strData;

  /**
   * 将数组 arrayList 处理成 numRows 行数的 二维数组，每一行对应一个二维数组值
   * 这里的字符串长度比 numRows 小，则直接处理字符串的长度即可
   */
  for (let i = 0; i < Math.min(numRows, strDataLen); i++) {
    arrayList[i] = [];
  }

  /**
   * 字符串从左往右依次处理，通过当前行和当前方向控制字符插入二维数组的位置
   */
  let curRowNum = 0;
  let addGoDownValFlag = false;
  for (let j = 0; j < strDataLen; j++) {
    // 当前值放入二维数组对应行 curRowNum 控制二维数组行数
    arrayList[curRowNum].push(strData[j]);
    // 二维数组 第一行 和 最后一行 的时候需要改变方向值，通过对 curRowNum 的加减 1 控制二维数组从上到下还是从下到上(从前向后循环还是从后向前)
    if (curRowNum === 0 || curRowNum === numRows - 1) addGoDownValFlag = !addGoDownValFlag;
    curRowNum += addGoDownValFlag ? 1 : -1;
  }

  /**
   * 最后处理二维数组值并进行拼接成最终值
   */
  let convertEndStrData = '';
  for (let k = 0; k < arrayList.length; k++) {
    let curArrayVal = arrayList[k];

    convertEndStrData += curArrayVal.join('');
  }

  return convertEndStrData;
}

总结：这里最终要的就是通过控制当前行和当前方向将对应的字符值插入到定义的二维数组对应的行中，最终将二维数组进行字符串连接处理。

时间复杂度： O(n)，其 n === length(str)