LeetCode刷题之旅(6)--Z字形变换(中等题)

每天属于自己的时间,就是慢慢的刷题的时候,啥也不用想,沉浸在写出最佳程序的过程中,沉浸在自己阅读大牛代码,提升自我的过程中,那种满足感,真的很让人享受<.>

题目:Z字形变换

1
2
3
4
5
6
7
将字符串 "PAYPALISHIRING"Z字形排列成给定的行数:
P A H N
A P L S I I G
Y I R

之后从左往右,逐行读取字符:"PAHNAPLSIIGYIR"实现一个将字符串进行指定行数变换的函数:
string convert(string s, int numRows);
1
2
3
4
5
6
7
8
9
10
11
12
13
示例1:
输入: s = "PAYPALISHIRING", numRows = 3
输出: "PAHNAPLSIIGYIR"

示例2:
输入: s = "PAYPALISHIRING", numRows = 4
输出: "PINALSIGYAHRPI"
解释:

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

解题思路:

方法:

思路很简单,就是从左到右按照行数依次存入,就是按照题意的规律存。通过观察,可以发现,先存第一行,然后第二行只是第一行的每个数的左右两个字符依次存取,第三行是第一行每个数的左右间隔一个数的依次存取…..
而第一行的规矩就是2(numRows-2)+2为两个字符之间的距离。第一行第一个字符,可以看做是第零行第一个字符的右下第一个字符,所以要先s[j+1],然后再存第零行第二个字符左下的字符所以是s[j+row0-i]i为行数从0开始计数。

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

if(numRows<=1)return s;
int n=s.size();
int i=0,j=0;
int row0=2*numRows-2;
string res;
for(i=0;i<numRows;i++)
{
for(j=0;j+i<n;j=j+row0)
{
res+=s[j+i];
if(i!=0&&i!=numRows-1&&j+row0-i<n)
res+=s[j+row0-i];
}
}
return res;
}
};
执行用时:28 ms
您的支持将鼓励我继续创作!