leetcode: 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   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".

 

原问题链接：https://leetcode.com/problems/zigzag-conversion/

 

问题分析

    这个问题看起来比较简单，但是往往在开始分析的时候却找不到思路。按照原文的描述，我们是希望将字符串组织成之字形的方式来分布，然后再按照平行的行方式来取元素。 以问题描述中的字符串遍历方式为例，假设有字符串"abcdefg"并且排成3行，那么按照原来从头到尾遍历的话它们应该按照下图的方式进行：

    从上图中可以看到，之字形遍历的顺序是首先从上到下的走。然后再从下到上，不过从下到上遍历有一个特点，就是它往上的第一个元素其实是比前一列的元素要往上一行，同时它也不会到最上面那一行。所以在一些特殊情况比如说行数为1， 2的时候，它们实际上根本就不能够形成一个向上的回路。针对这些情况，它们就相当于是一组组从上往下的元素排列。比如行数为2的时候，它们实际上就是这么一个样式：

    再进一步来看，针对这种排列之后，希望最终返回的结果是按照从上到下的顺序一行行返回结果。假设以4行为例的话，我们取这些元素的方式则如下图：

 

     按照这个顺序得到的串是"agbfhceid"。所以如果要实现上述的过程，该怎么做呢？从前面的讨论中，我们可以声明一个给定行数的数组。数组里的每个元素可以在之字形遍历到的时候添加给定的字符。所以可以声明一个StringBuilder的数组。

    之字形遍历的过程则需要注意从上往下和从下往上的差别。另外，不管在向上还是向下遍历的时候要判断访问的元素是否已经到头了。所以根据上述的讨论可以得到如下的代码：

 

public class Solution {
    public String convert(String s, int nRows) {
        char[] c = s.toCharArray();
        StringBuilder[] builders = new StringBuilder[nRows];
        for(int i = 0; i < nRows; i++) builders[i] = new StringBuilder();
        int i = 0, len = s.length();
        while(i < len) {
            for(int j = 0; j < nRows && i < len; j++) builders[j].append(c[i++]);
            for(int j = nRows - 2; j >= 1 && i < len; j--) builders[j].append(c[i++]);
        }
        for(int j = 1; j < builders.length; j++) builders[0].append(builders[j]);
        return builders[0].toString();
    }
}

 

总结

     这个问题中间比较难构造的就是要理解之字形遍历的过程。从上往下和从下往上的时候访问的元素的索引不一样。而且用一个StringBuilder数组来作为数据结构是一个比较理想的选择。