LeetCode 解题报告 - 6. ZigZag Conver

对 hard 类型的题，表示目前实在是 hold 不住，暂时先不刷啊。等我刷完 easy 和 medium 回头再战！ 2016/10/10
编程语言是 Java，代码托管在我的 GitHub 上，包括测试用例。欢迎各种批评指正！

<br />

题目 —— ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of row 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 text, int nRows);

convert("PAYPALISHIRING", 3)should return "PAHNAPLSIIGYIR".
<br >

解答

• 题目大意
  给出一个字符串，给出行数，按照这个行数将字符串写成 zigzag 模式，然后按行读出来。

• 解题思路

  • 我们先来观察一下这个 zigzag 模式，我们发现，是按照行读的，所以每行都可以使用一个 StringBuilder 来存储。
  • 观察列，每一个竖直的列都有 numRows 行，其他斜的列有 numRows-2 行，我们按照这个特点来填充 StringBuilder[] 数组即可。

• 代码实现

public class Solution {
    public String convert(String s, int numRows) {
        StringBuilder[] sb = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) {
            sb[i] = new StringBuilder();
        }
        int i = 0;
        while (i < s.length()) {
            for (int rowIndex = 0; rowIndex < numRows && i < s.length(); rowIndex++) {
                sb[rowIndex].append(s.charAt(i++));
            }
            for (int rowIndex = numRows - 2; rowIndex > 0 && i < s.length(); rowIndex--) {
                sb[rowIndex].append(s.charAt(i++));
            }
        }
        for (i = 1; i < numRows; i++) {
            sb[0].append(sb[i]);
        }
        return sb[0].toString();
    }
}

• 小结
  对于这种看似“花样”的题目，刚上来可能是一脸懵逼，但仔细分析过后会发现排列规律，找准数据结构（本题中就是 StringBuilder 数组）即可迅速解决。另外，本题需要注意的是，对于 StringBuilder 数组，每一个元素（对象）都需要初始化。最后还需要将所有的 StringBuilder 连接起来。