6. 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".

题目翻译

字符串"PAYPALISHIRING"根据给定行数，以一个Z字形显示出来，如下所示：（您可能希望以固定字体显示此模式以获得更好的可读性）

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

然后逐行阅读： "PAHNAPLSIIGYIR" 编写获取逐行阅读Z字形字符串的代码，并将该字符串返回

string convert（string text，int nRows）;

convert("PAYPALISHIRING", 3)应该返回"PAHNAPLSIIGYIR"。

解题方案

标签： String

思路：

• 整体思路是，按照行来进行遍历，第一行和最后一行不需要考虑斜向上元素，其他行需要将斜向上元素根据数学规律进行添加

• 以上图为例，我们将变形后的数据根据斜着的 V 形来进行分组，每一组 V 字形的长度为 size = 2 * line - 2，line 是行数，对于上图 size = 8
• 对于垂直向下的一列元素来说，每一组向下的列之间间隔 size 大小，即一组元素的个数，比如0和8、2和10之间都相差了 size 大小。
• 对于斜向上的元素来说，它们的位置位于当前组 size - i（i 为该元素所在的行数，一组有 size 个字符，第 i 行就代表着倒数第 i 个元素，所以位置为 size - 1）。当前组的第一个字符所在位置为 j - i （j 为与斜向上的元素同在一行的，垂直向下的列的元素在字符串中的序号，i 为它们共同的行号）。
• 即：j-i 就是 zigzag 的起始字符，然后我们是要倒数第i个，因为一个 zigzag 有 size 个字符，所以倒数第 i 个就是 size-i ，我们要赋值的字符就是 (j-i)+(size-i)

代码：

public class Solution {
    public String convert(String s, int nRows) {  
        if(s == null || s.length()==0 || nRows <=0)  
            return "";  
        if(nRows == 1)  
            return s;  
        StringBuilder res = new StringBuilder();  
        int size = 2*nRows-2;  
        for(int i=0;i<nRows;i++) {  
            for(int j=i;j<s.length();j+=size) {  
                res.append(s.charAt(j));  
                if(i!=0 && i!=nRows-1 && (j-i)+(size-i)<s.length())  
                    res.append(s.charAt((j-i)+(size-i)));  
            }                  
        }  
        return res.toString();  
    }
}

参考资料

http://blog.csdn.net/chilseasai/article/details/47209565 http://blog.csdn.net/pistolove/article/details/41408021