LeetCode 0006 - ZigZag Conversion
# Hints
- 模拟 + 思维
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N
A P L S I I G
Y I R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string s, int numRows);
Example 1:
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Example 2:
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P I N
A L S I G
Y A H R
P I
# 题意
给定一个字符串,将其按照题目中所述的ZIG-ZAG方式写出,然后逐行拼接,求得到的字符串。
# 题解
容易想到直接按题目要求模拟,用空间换时间,绘制题目中所述的ZIG-ZAG图形。
事实上,因为最后要求的是逐行拼接的结果,而非这个图形,容易发现,ZIG-ZAG图形事实上等价于S形图形。以样例为例:
P I N
A L S I G
Y A H R
P I
这一图形和下面的图形的读取结果是一样的。
P I N
A L S I G
Y A H R
P I
这可以将斜线转化为竖直线,大大简化了代码实现。我们只需上下来回画S形即可。
# AC代码
class Solution {
public:
string convert(string s, int numRows) {
// 初始化
string box[numRows];
// 模拟
int column = 0;
int index = 0;
while (index < s.length()) {
if (column % 2 == 0) {
for (int i = 0; i <= numRows - 1 && index < s.length(); i ++) {
box[i] += s[index++];
}
} else {
for (int i = numRows - 2; i >= 1 && index < s.length(); i --) {
box[i] += s[index++];
}
}
column ++;
}
// 获取答案
string res;
for (int i = 0; i < numRows; i ++) {
res += box[i];
}
// 返回
return res;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01