mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
49 lines
1.6 KiB
Markdown
49 lines
1.6 KiB
Markdown
# [6. ZigZag Conversion](https://leetcode.com/problems/zigzag-conversion/)
|
||
# 思路
|
||
题意是将一个字符串里的所有字符按照ZigZag的规则重新排列后按序输出。例如
|
||
```
|
||
Input: s = "PAYPALISHIRING", numRows = 4
|
||
Output: "PINALSIGYAHRPI"
|
||
Explanation:
|
||
|
||
第0行: P I N
|
||
第1行: A L S I G
|
||
第2行: Y A H R
|
||
第3行: P I
|
||
```
|
||
可以看到这种排列是有周期性的，上例周期T为6，一般化的 `T = 2 * numRows - 2`(特殊情况：当numRows为1时T为1)。
|
||
把题目意思搞清楚了这题也就迎刃而解了。
|
||
就拿上面的例子来说，
|
||
* 第0行的"PIN"在s中的下标分别是0、6、12 --> 0、0 + T、0 + 2T ...
|
||
* 第1行的"ALSIG"在s中的下标分别是1、5，7、11，13 --> 1、5，1 + T、5 + T，1 + 2T、5 + 2T ...
|
||
* 第2行的"YAHR"在s中的下标分别是2、4，8、10 --> 2、4，2 + T、4 + T，2 + 2T、4 + 2T ...
|
||
* 第3行的"PI"在s中的下标分别是3、9 --> 3、3 + T、3 + 2T ...
|
||
|
||
由上面分析不难写出代码。
|
||
|
||
# C++
|
||
``` C++
|
||
class Solution {
|
||
public:
|
||
string convert(string s, int numRows) {
|
||
if(numRows == 1) return s;
|
||
string ans = "";
|
||
int T = 2 * numRows - 2;
|
||
for(int i = 0; i < numRows; i++){
|
||
int pos1 = i, pos2 = T - i;
|
||
while(1){
|
||
if(pos1 >= s.size()) break;
|
||
ans += s[pos1];
|
||
pos1 += T;
|
||
if(i != 0 && i != numRows - 1){ // 不是0行也不是最后一行
|
||
if(pos2 >= s.size()) break;
|
||
ans += s[pos2];
|
||
pos2 += T;
|
||
}
|
||
}
|
||
}
|
||
return ans;
|
||
}
|
||
};
|
||
```
|