1 题目

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

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

1
2
3

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

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

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

1

string convert(string s, int numRows);

2 解题

2.1 按行排序

思路

通过从左向右迭代字符串，我们可以轻松地确定字符位于 Z 字形图案中的哪一行。

算法

我们可以使用 min(numRows,len(s)) 个列表来表示 Z 字形图案中的非空行。

从左到右迭代 s，将每个字符添加到合适的行。可以使用当前行和当前方向这两个变量对合适的行进行跟踪。

只有当我们向上移动到最上面的行或向下移动到最下面的行时，当前方向才会发生改变。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

string convert_1(string s, int numRows) 
{
    if (numRows == 1) return s;
    //新增一个存储string的容器，用于存储每一行的字符串
    vector<string> rows(min(numRows, int(s.size())));
    int curRow = 0; //当前行号
    bool goingDown = false; //行的增加方向

    for (char c : s) 
    {
        rows[curRow] += c;
        //判断是否是最上面的行还是最下边的行，
        //若是，改变方向
        if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
        //根据当前方向判断行号
        curRow += goingDown ? 1 : -1;
    }

    string ret;
    //各个行的string加起来，得到返回的字符串
    for (string row : rows) ret += row;
    return ret;
}

复杂度分析：

  • 时间复杂度：$O(n)$,其中 n 是字符串的长度。

  • 空间复杂度：$O(n)$

2.2 按行访问

思路

按照与逐行读取 Z 字形图案相同的顺序访问字符串，关键寻找数学规律。

算法

首先访问 行 0 中的所有字符，接着访问 行 1，然后 行 2，依此类推…

对于所有整数 k，

  • 行 0 中的字符位于索引 k (2 ⋅ numRows − 2) 处，k表示该行的的几个字符
  • 行 numRows − 1 中的字符位于索引 k (2 ⋅ numRows − 2) + numRows − 1 处;
  • 内部的 行 i 中的字符位于索引 k (2 ⋅ numRows − 2) + i 以及 (k + 1)(2 ⋅ numRows − 2) − i 处。（注：会比第0与第numRows-1多一个）

代码实现：

 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
64

string convert_2(string s, int numRows) 
{

    if (numRows == 1) return s;

    string ret;
    int n = s.size();
    int cycleLen = 2 * numRows - 2;

    for (int i = 0; i < numRows; i++) 
    {
        /*leetcode 官网写法
        for (int j = 0; j + i < n; j += cycleLen) 
        {
        	//最上面的行与最下边的行，情况1、2以及3的第一个情况
            ret += s[j + i];
            //中间的行，3的第二种情况
            if (i != 0 && i != numRows - 1 && j + cycleLen - i < n)
                ret += s[j + cycleLen - i];
        }
        */
        //分析
        //pos索引下标
        int pos = 0;
        //第0行
        if(i == 0)
        {
            for(int k=0;(pos = k*cycleLen + i)<n;k++)
            {
                pos = k*cycleLen;
                //i=0
                //可改写为pos=k*cycleLen + i
                ret += s[pos];
            }
        }
        else if(i == numRows - 1)
        {
            for(int k=0;(pos = k*cycleLen + i)<n;k++)
            {
                pos = k*cycleLen + numRows - 1; 
                //其中numRows - 1即为i
                //可改写为pos=k*cycleLen + i
                ret += s[pos];
            }
        }
        else
        {
            for(int k=0;(pos = k*cycleLen + i)<n;k++)
            {
                //第一个数
                ret += s[pos];
                //第二个数
               if( (pos = (k+1)*cycleLen - i) <n )
                   ret += s[pos];
                
            }
        }
        //三种情况简化即为官网类似的代码

    }
    return ret;
}

复杂度分析：

  • 时间复杂度：$O(n)$,其中 n 是字符串的长度。

  • 空间复杂度：$O(n)$，在C++中，如果返回字符串不被视为额外空间，则复杂度为$O(1)$。