题目

给定一个字符串，找出不含有重复字符的最长子串的长度。
示例 1:

1
2
3
4
5
6
输入: s = "PAYPALISHIRING", numRows = 3
输出: "PAHNAPLSIIGYIR"
解释：
P   A   H   N
A P L S I I G
Y   I   R

示例 2:

1
2
3
4
5
6
输入: s = "PAYPALISHIRING", numRows = 4输出: "PINALSIGYAHRPI"
解释:
P     I    N
A   L S   I  G
Y A   H R
P     I

分析

这道题有两种解法，一种是利用数学表达式计算出行数与元素排布位置的联系，用数学表达式表达出，不过这并不是我们想要的最优解，或者说，他并不优雅，因为没有体现出算法的美感，只是单纯的找规律了。

所以我们想，能不能不靠找规律，准备一个数组与之对应：

思路

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

算法

我们可以使用 $\min(numRows,n)$ 个列表来表示 Z 字形图案中的非空行。
从左到右迭代，将每个字符添加到合适的行。可以使用当前行和当前方向这两个变量对合适的行进行跟踪。只有当我们向上移动到最上面的行或向下移动到最下面的行时，当前方向才会发生改变。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    string convert(string s, int numRows) {

        if (numRows == 1)
            return s;

        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;
        for (string row : rows)
            ret += row;
        return ret;
    }
};

代码运行过程

以"PAYPALISHIRING"numRows=3为例：

我们首先把行数，元素数两者最小那个当做划分区域（通常都是行数小），这样我们就分成了numRows=3组，很自然，我们把前三个元素依次放到，第1、2、3组中，注意，当我们触底（curRows=3）时，需要回溯（减小curRows），所以我们创建了变量goingdown，来控制是向上还是向下。

而且只需要遍历一次，下面以goingdown的改变来分组

元素0-2

  • 第一组：P
  • 第二组：A
  • 第三组：Y

元素3-4

  • 第一组：PA
  • 第二组：AP
  • 第三组：Y

元素5-6

  • 第一组：PA
  • 第二组：APL
  • 第三组：YI

依次类推，很容易明白其中规律

个人总结

其实数学规律很容易想到，但是代码可能可能不是很容易写出来，但是上面的这种算法，很直观，为什么不容易想到呢，我认为是思维受到了限制，我们很容易地就直接造出一个与原数组等长的数组，一个一个往上去添加，但是我们可以先靠行分类，然后改变数值放入的顺序。

本体值得注意的有

1
2
3
vector<string> rows(min(numRows, int(s.size())));
···
rows[curRow] += c;

vector中的元素类型是String，这一点很巧妙，这样只需要一个加号，就能在结尾添加新字符。

1
2
goingDown = !goingDown;
curRow += goingDown ? 1 : -1;

能把代码写到如此简洁需要一个过程，当然，简单点的话可以写一个判断来改变goingdown的值

最重要的思想还是通过控制curRow的步进方向，来实现Z字形变换