题目要求

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)  

示例图

  convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR"
  题目翻译：给定一个字符串，按给定的行数自上而下排列之字型，如下图。输出结果是遍历每一行把字符拼接成的字符串

题目分析

如下图，把之字型的串划分为一系列子部分，每一个子部分具有相同的结构：

结构图

1. 长度为 2*(numLows-1)
2. 首行和尾行只有一个字符，其它行均有两个字符
3. 假设某一个子部分的首元素在原字符串是S[m]，则
      第一行的字符是 s.charAt(m)
      最后一行的字符是 s.charAt(m+numLows-1)
      第 i 行的两个字符分别是s.charAt(m+i-1)和 s.charAt(m+2*numRows-i-1)

伪代码

1. 将每一个子部分的首元素下标(如上图画红框的点)存入数组
2. 从第一行开始到第numLows行循环：
     在每一行，循环取出每一个子部分，取出该子部分该行的字符：
       在该行该子部分，通过判断首尾行及边界，取出字符，存入结果字符串

代码实现

package com.linsiyue;

public class Solution {
    public String convert(String s, int numRows) {
        StringBuilder res = new StringBuilder("");
        if (numRows==1) return s;
        int numParts=s.length()/(2*numRows-2), y=s.length()%(2*numRows-2);
        if (y!=0) numParts+=1;
        int[] arr = new int[numParts];
        // 存储每一个子部分的首元素下标
        for (int i = 0; i < arr.length; i++) {
            arr[i]=i*2*(numRows-1);
        }  
        // 循环遍历每一行
        for (int i=1; i<=numRows; i++){
            // 循环遍历每一个子部分
            for (int j = 0; j < arr.length; j++) {
                int m = arr[j];
                if (i==1) {
                    res.append(s.charAt(m));
                } else if (i==numRows){
                    if (m+numRows-1<s.length())
                        res.append(s.charAt(m+numRows-1));
                } else {
                    if (m+i-1<s.length()) 
                        res.append(s.charAt(m+i-1));
                    if (m+2*numRows-i-1<s.length()) 
                        res.append(s.charAt(m+2*numRows-i-1));
                }
            }
        }       
        return res.toString();
    }
}