题目描述
在行数等于3时,将字符串"PAYPALISHIRING
“按”N”字形排列,如下所示:
P A H N
A P L S I I G
Y I R
此时我们按行读取,会得到"PAHNAPLSIIGYIR"
.
要求编写一个函数,输入一个字符串和一个整数(表示行数),输出转换后的字符串:
string convert(string text, int nRows);
例如convert("PAYPALISHIRING", 3)
会返回"PAHNAPLSIIGYIR"
.
算法
(模拟找规律) $O(n)$
找下标的规律
- 首位两行为单一的等差数列
- 公差为
2 * (numRows - 1)
首项为i
- 公差为
- 中间的行为交替的等差数列
- 公差为
2 * (numRows - 1)
首项为i
和2 * (numRows - 1)- i
- 公差为
为了方便 把 2 * (numRows - 1)
拎出来
c++ 代码
class Solution {
public:
string convert(string s, int numRows) {
string res;
if(numRows == 1) return s;
int inc = (numRows - 1) * 2;
int n = s.size();
// 枚举每一行
for(int j = 0 ; j < numRows; j ++)
{
// 首尾两行
if(j == 0 || j == numRows - 1)
{
for(int i = j ; i < n; i += inc)
res += s[i];
}
// 中间的行 交替的等差数量
else
{
for(int k = j, i = inc - j; i < n || k < n; i += inc , k += inc)
{
if(k < n) res += s[k];
if(i < n) res += s[i];
}
}
}
return res;
}
};