题目

给定一个字符串,找出不含有重复字符的最长子串的长度。
示例 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字形变换