题目概要
将字符串按照ZigZag的顺序重新排列，求排列之后的新字符串。
题目链接
题目解析
数学规律
寻找原先的字符在经过ZigZag变换后的位置，直接计算出最后的字符串：
0 4 8 12
1 3 5 7 9 11 13
2 6 10 14
上例中的数字代表的是对应的字符索引，设n为输入的参数numRows的值，则该例中为3，容易知道
第一行的字符索引序列为
索引序列
先考虑最后一行，容易发现该行的索引序列与第一行的对应差值为n-1
中间几行与前述两者差距较大，我们再看一个简单的实例：
0 6 12 18 24
1 5 7 11 13 17 19 23 25
2 4 8 10 14 16 20 22 26
3 9 15 21 27
看似毫无规律，但当我们将其分为两列分别观察时：
下标 - 1
下标 - 2
或者
下标 - 3
下标 - 4
上述两条，也容易通过判断是否为第奇数个字符的规则合并为一条规则。
具体细节参见代码部分。
手动模拟
按照题目的要求，分配多个字符数组，完成操作后，拼接在一起。
复杂度分析
时间复杂度：O(n)
空间复杂度：O(n)
注：上述的n为字符串的长度
代码
数学规律
class Solution {
public:
string convert(string s, int numRows) {
if (numRows == 1) return s;
int delta = numRows - 1;
int sz = s.size();
string rs;
// row 0
for (int i=0; i<sz; i+=2*delta)
rs.push_back(s[i]);
// row [1, numRows-1)
for (int row=1; row<numRows-1; ++row) {
int cur = 0; // 该行第几个字符
int idx = row; // 对应原先字符串的第几个
while (idx<sz) {
if (cur%2 == 0) {
// row + 2*delta * (cur/2)
idx = row + delta * cur;
}
else {
// -row + 2*delta * ((cur+1)/2)
idx = -row + delta * (cur+1);
}
if (idx<sz)
rs.push_back(s[idx]);
++cur;
}
}
// row numRows-1
for (int i=numRows-1; i<sz; i+=2*delta)
rs.push_back(s[i]);
return rs;
}
};
手动模拟
class Solution {
public:
string convert(string s, int numRows) {
if (numRows == 1) return s;
vector<string> v_str = vector<string>();
for (int i=0;i<numRows;++i)
v_str.push_back(string());
int idx = 0; // 当前字符的索引
int row = 0; // 将被填充的字符串索引
int dir = 1; // 方向：1 => 往下 -1 => 往上
int sz = s.size();
while (idx<sz) {
v_str[row].push_back(s[idx]);
row += dir;
if (row == 0)
dir = 1;
if (row == numRows-1)
dir = -1;
++idx;
}
string rs;
for (int i=0;i<numRows; ++i)
rs += v_str[i];
return rs;
}
};
广告区域
本人和小伙伴们承接各种软件项目，有需求的可以联系我们。
QQ: 2992073083
