Alexgogoing

Z字型字符变换

算法
字数统计: 810阅读时长: 3 min
2021/01/05 Share

题目

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：

1
2
3
L   C   I   R
E T O E S I I G
E   D   H   N

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。

请你实现这个将字符串进行指定行数变换的函数：

1
string convert(string s, int numRows);

示例 1:

1
2
输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"

示例 2:

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

L     D     R
E   O E   I I
E C   I H   N
T     S     G

思考

题目看起来像是一个图像类问题，我理解为考察归纳总结能力的问题。那么，我们来观察一下这个奇怪的字符排列。

如果能将其中的字符串看成一个个单元组合而成的，那么单元可以是这样的。如果可以总结出单元内的规律，就能简化问题实现降维。

image-20210104210023385

那么当前问题转换成，总结归纳一个这样的单元到底有什么样的规律。只是看这些字母，好像并不能发现什么，那么我们将这些字母转换成其对应的字符串位置下标数字。

image-20210104210736266

当行数 = n，不难得出每个单元的元素个数为2(n - 1);

单元第一列，从上到下递增，于是[0, n - 1];

单元其余元素（3、4、5）分别为2(n - 1) - 3 = 2(n - 1) - (n - 1) 2(n - 1) - 2 2(n - 1) - 1；

image-20210104212013838

当单元序号 = k，单元元素个数 = m = 2(n - 1)，换个角度观察

image-20210104213141703

第一行，0m、1m、2m......km;

第二行，0m + 1, 0m + m - 1, 1m + 1, 1m + m - 1......km + 1, km + m - 1;

第三行，0m + 2, 0m + m - 2, 1m + 2, 1m + m - 2......km + 2, km + m - 2;

……

第n行，0m + n - 1, 0m + m - (n - 1)......km + n - 1, km + m - (n - 1);

又知道m = 2(n - 1)于是km + m - (n - 1) = km + 2(n - 1) - (n - 1) = km + (n - 1);

于是总结出，在单元k中，当行数= i，λk = km + i, φk = km + (m - i)，当i = n - 1时，λk = φk；

于是我们可以得出，先移动单元数k，顺序得到一行的所有字符，然后移动行数i，顺序得到每行的所有字符。

Coding Time

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
function solution(){
  // 特殊条件，特殊处理
  if(numRows <= 1 || s.length <= 1){
        return s;
    }
  
    let result = '';
  // 每个单元元素个数
    const blockNum = 2 * (numRows - 1);
  // 外层循环，代表后移动，此处为行数
    for(let row = 0;row < numRows;row++){
      // 内层循环，代表先移动，此处为单元数
        for(let k = 0, flag = true;flag;){
          // 同行数中第一个数
            let num1 = k * blockNum + row;
          // 同行数中第二个数
            let num2 = k * blockNum + (blockNum - row);
          // 判断第一个数下标是否超过范围
            if(num1 >= s.length){
                flag = false;
          // 判断第二个数下标是否超过范围
            }else if(num2 >= s.length){
                flag = false;
                result += s[num1];
          // 记录下当前单元，进入下一个单元
            }else{
                if(row === 0 || row === numRows - 1){
                    result += s[num1];
                }else{
                    result += s[num1] + s[num2];
                }
                k++;
            }
        }
    }
    return result;
}

归纳总结大法，简称野路子解法完成。

image-20210105114043715

原文作者：alexgogoing

原文链接：https://alexgogoing.github.io/2021/01/05/Z字型字符变换/

发表日期：January 5th 2021, 11:44:20 am

更新日期：June 8th 2021, 8:13:58 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 题目
  2. 2. 思考
Total : 17
2022
2021
2020
2019
html css 布局 算法 javascript 奇技 web 性能优化