LeetCode6 Z字型变换 2018.4.19

95 阅读 0 评论 63 点赞

我是靠谱客的博主老迟到星星，这篇文章主要介绍LeetCode6 Z字型变换 2018.4.19，现在分享给大家，希望可以做个参考。

题干：

将字符串 "PAYPALISHIRING" 以Z字形排列成给定的行数：

复制代码

1
2
3
4
5
6
7
8
P
A
H
N
A P L S I I G
Y
I
R

之后从左往右，逐行读取字符："PAHNAPLSIIGYIR"

实现一个将字符串进行指定行数变换的函数:

复制代码

1
string convert(string s, int numRows);

示例 1:

复制代码

1
2
输入: s = "PAYPALISHIRING", numRows = 3
输出: "PAHNAPLSIIGYIR"

示例 2:

复制代码

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

这种题主要就是找规律，ac代码如下

复制代码

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
#include <iostream>
#include <vector>
#include<string.h>
#include<algorithm>
#include<string>
#include <unordered_map>
using namespace std;
class Solution {//第一行和最后一行直接求方差可以解决（2n——2），中间的行还要找规律
public:
string convert(string s, int numRows)
{
if(numRows == 1)
return s;
string result = "";
int len = s.size();
int diff = 2*numRows - 2;//先求出方差
for(int i = 0;i<numRows;i++)//行,除去首位行，中间的行每行都要加一个中位数
{
for(int j = i;j<len;j += diff)
{
if(i == 0 || i == numRows - 1)//第一行和最后一行中间没有数
{
result += s[j];
}
else
{
result += s[j];
if(j + diff - i*2 < len)
result += s[j + diff - i*2];
}
}
}
return result;
}
};
int main()
{
Solution solution;
string r;
r = solution.convert("PAYPALISHIRING",3);
cout<<r<<endl;
}