博文中会简要介绍Leetcode P0006题目分析及解题思路。
“ZigZag Conversion”是一道比较简单的纯字符串问题，主要考察细心和耐心程度，题干如下：
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 RAnd 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);
这道题说白了就是在找规律。偶数zigzag段在行上增长，奇数zigzag段在行上减少和列上增加。
以下是Java的题解代码实现。
class Solution {
public String convert(String s, int numRows) {
if (s == null || s.length() <= 1 || numRows <= 1)
return s;
char[][] zigzag = new char[numRows][s.length()];
char[] chars = s.toCharArray();
int row = 0, col = 0, idx = 0, cycle = 0;
while (idx < chars.length) {
cycle = idx / (numRows-1);
zigzag[row][col] = chars[idx];
if (cycle%2 == 0) {
++row;
}
else {
--row;
++col;
}
++idx;
}
StringBuilder stringBuilder = new StringBuilder();
for (int i1=0; i1<numRows; ++i1) {
for (int j2=0; j2<chars.length; ++j2) {
if (zigzag[i1][j2] > 0) {
stringBuilder.append(zigzag[i1][j2]);
}
}
}
return stringBuilder.toString();
}
}
以下是C++的题解代码实现。
class Solution {
public:
string convert(string s, int numRows) {
if (s.length() <= 1 || numRows <= 1)
return s;
vector<vector<char>> zigzag(numRows, vector<char>(s.length(), '0'));
int row = 0, col = 0, idx = 0, cycle = 0;
while (idx < s.length()) {
cycle = idx / (numRows-1);
zigzag[row][col] = s[idx];
if (cycle%2 == 0) {
++row;
}
else {
--row;
++col;
}
++idx;
}
string ret = "";
for (int i1=0; i1<numRows; ++i1) {
for (int j2=0; j2<s.length(); ++j2) {
if (zigzag[i1][j2] != '0') {
ret += zigzag[i1][j2];
}
}
}
return ret;
}
};