题目描述
将一个给定字符串 s 根据给定的行数 numRows ,以从上往下、从左到右进行 Z 字形排列。
样例
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时,排列如下:
P A H N
A P L S I I G
Y I R
算法1
(找规律、模拟) $O(n)$
当 n = 4时(只用下标模拟)
0 6 12
1 5 7 11 13
2 4 8 10 14
3 9 15
当 n = 3时
0 4 8
1 3 5 7 9
2 6 10
我们发现第一行以及最后一行的元素的下标构成等差数列的形式,d = 2 * n - 2
而对于其他列而言,除去两竖列之间的元素之外,剩余的元素也构成等差数列,所以并且下标
还和第一列的元素有关 j = 2 * n - i
C++ 代码
class Solution {
public:
string convert(string s, int n) {
string str ;
if(n == 1)return s;
for(int i = 0; i < n; i ++){
if(i == 0 || i == n - 1){
for(int j = i ; j < s.size(); j += 2 * n - 2)
str += s[j];
}else {
for(int j = i, k = 2 * n - 2 - i; j < s.size() || k < s.size(); j += 2 * n - 2 , k += 2 * n - 2){
if(j < s.size())str += s[j];
//有可能出现有些元素存在而有的元素不存在的情况,所以需要特判
if(k < s.size())str += s[k];
}
}
}
return str;
}
};