链接
https://leetcode-cn.com/problems/zigzag-conversion/
耗时
解题:1h+
题解:1 h 30 min
题意
将给定字符串根据给定的行数进行Z字排列。比如输入字符串为 “LEETCODEISHIRING” 行数为 3 和 4时,排列如下所示:
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200315225854894.png)
现要求从左往右逐行读取,产生出一个新的字符串,比如 3 行的变成:“LCIRETOESIIGEDHN”, 4 行的变成:“LDREOEIIECIHNTSG”。
思路
一个非常复杂的思路:从答案出发,找到 新字符串 每个字符对应于 原字符串 的位置。观察 Z 形排列中每行字符串的个数,发现:第一行和最后一行规律相同,其余各行相同。分别讨论:
- 第一行和最后一行
所有元素可以构成等差数列,公差为:
s
e
g
=
n
u
m
R
o
w
s
∗
2
−
2
seg = numRows*2-2
seg=numRows∗2−2。轮到第一行和最后一行时,累加寻找即可。但是注意,当只有一行时,
s
e
g
=
0
seg = 0
seg=0,会陷入死循环,特判一下,使得
s
e
g
seg
seg 的最小值也是
1
1
1 即可。 - 其余各行
每个Z字形中间有3个元素,Z字形外围的2个元素的规律与第一种情况(1. 第一行和最后一行)相同,麻烦的是中间这个元素。
观察Z字形,发现:第一个角之间的元素的位置的差 和 第二个角之间的元素的位置的差 是不同的,但是两个差值的和是固定的,为:
n
u
m
R
o
w
s
∗
2
−
2
numRows*2 - 2
numRows∗2−2。
如图所示:Z字形第一个角中 E 和 C 之间的差 与 Z字形第二个角中 C 和 I 之间的差 是不同的。
并且每行的第一个角之间的差可以推导出公式:
s
e
g
=
n
u
m
R
o
w
s
∗
2
−
2
∗
r
seg = numRows*2 - 2*r
seg=numRows∗2−2∗r(
r
r
r是行数)。
那么接下来就简单了,这相当于有一个大的等比数列,然后在每两项之间添加一项,并且添加的这项与前一项的差已知。
也可以这么想:有2个固定的差值,每次相加时轮转,那么对于有两个固定的差,并且每隔一次一变化的情况,设置一个 bool 型的 flag 每次变换一下值即可。
然后就与第一种情况(1. 第一行和最后一行)相同,累加寻找即可。
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200315232334313.png)
AC代码
class Solution {
public:
string convert(string s, int numRows) {
string ans;
for(int i = 0; i < numRows; ++i) {
int pos = i;
if(i == 0 || i == numRows-1) {
int seg = max(numRows*2 - 2, 1);
while(pos < s.size()) {
ans += s[pos];
pos += seg;
}
}
else {
int seg = numRows*2 - 2*(i+1);
bool flag = 0;
while(pos < s.size()) {
ans += s[pos];
flag == 0 ? pos += seg : pos += (numRows*2 - 2 - seg);
flag = !flag;
}
}
}
return ans;
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)