Halo

A magic place for coding

0%

LeetCode解题报告(43)-- 6. ZigZag Conversion

Problem

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)

1
2
3
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:

1
string convert(string s, int numRows);

Example 1:

1
2
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

1
2
3
4
5
6
7
8
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

P I N
A L S I G
Y A H R
P I

Analysis

  这道题的考点是字符串的操作,我们需要对一个字符串用N型的方式去放置这个字符串。其本质是对矩阵的操作,操作的方向有两个,一个是往上,另一个是往下。根据题目给的numRows,确定遍历的界限即可。

Solution

  使用一个变量index来访问不同行,使用dir来表示当前的移动方向(1为向下,-1为向上)。然后遍历字符串,每个字符放到对应的zig[index]中就可以了。需要注意边界情况:

  • 当向上走时,index < 0时,说明此时已经到最上一行,需要将dir设为1,index设为1;
  • 同理,当向下走时,index >= numRows时,说明此时已经走到了最下一行,需要将dir设为-1,index设为numRows - 2
      最后再将所有的行拼接起来成为一个字符串作为结果输出即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
string convert(string s, int numRows) {
if (s.size() < numRows || numRows == 1)
return s;

int dir = 1;// 1 go down, -1 go up
int index = 0; // pos in zig
string zig[numRows];
for (int i = 0; i < s.size(); i++) {
zig[index] += s[i];
index += dir;

if(index < 0) {
index = 1;
dir = 1;
}
if (index >= numRows) {
index = numRows - 2;
dir = -1;
}
}

string result;
for (int i = 0; i < numRows; i++) {
if (!zig[i].empty()) {
result += zig[i];
}
}
return result;
}
};

运行时间:约20ms,超过75.6%的CPP代码。

Summary

  这道题对算法没什么要求,其实就是一个遍历矩阵,需要耐心地找规律。网上也有一种很巧妙的解法可以参考,但是像我这样解决也是比较快速的。本题的分析到此为止,谢谢您的支持。

Welcome to my other publishing channels