将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：

L   C   I   R
E T O E S I I G
E   D   H   N

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1:

输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"

示例 2:

输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:

L     D     R
E   O E   I I
E C   I H   N
T     S     G

https://leetcode-cn.com/problems/zigzag-conversion/

解法1

这道题本身没什么难度，但是考察逻辑思维的缜密性。我采用朴素的方法，首先计算出按Zigzag排列所需要数组的纬度，然后按照Zigzag的顺序填充这个矩阵，然后将矩阵以字符串的形式输出。题目固定了行数numRows，我们需要计算出numCols。

*   *   *
* * * * *         numRows = 3
*   *   *

*    *    *
*  * *  * *
* *  * *  *       numRows = 4
*    *    *

*     *     *
*   * *   * *
*  *  *  *  *     numRows = 5
* *   * *   *
*     *     *

通过上面3个例子观察，我们填满一整列需要numRows个字符，还需要numRows – 2个字符填充每列只有一个字符的列。我们将一整列与每列只有一个字符的列称为一个unit，那么通过观察发现构成一个unit需要numRows + numRows – 2个字符，unit的宽度为 1 + numRows – 2（1是一整列，numRows – 2是一个字符的列）。当然，可能有余下的字符无法构成一个unit，我们首先判断余下字符是否能够成一整列，然后判断余下字符能够构成多少个“只包含一个字符的列”。

我们通过上面的分析，可以计算出numCols，然后我们依照ZigZag的方式填充字符数组。最后依照行主序的方式遍历字符数组，向StringBuilder中追加即可。这道题我提交了6次才通过，分别是由于

1. 未对空字符串特殊处理
2. 字符串长度小于一个unit没特殊处理
3. numRows为1导致unit为0，没做特殊处理
4. 填充arr中只包含一个字符串的列，需要从倒数第二行开始。

所以计算numCols需要特别的小心，多尝试几个case自测下。

class Solution {
    public String convert(String s, int numRows) {
        if (s == null || s.length() == 0)
            return "";
        if (numRows <= 1)
            return s;

        int numCols;
        int unit = numRows + numRows - 2;

        // 少于一个unit，至少有一列。
        if (s.length() < unit)
            numCols = 1;
        else
            numCols = (s.length() / unit) * (1 + numRows - 2);

        // 下面通过remaining计算余下的字符能够构成几列
        int remaining = s.length() % unit;

        if (remaining != 0) {
            // 不够一个unit，先占一列
            remaining -= numRows;
            numCols++;
            // 一列装不下，剩下的字符每个各占一列
            if (remaining > 0)
                numCols += remaining;
        }

        char[][] arr = new char[numRows][numCols];
        int pos = 0;
        int unitWidth = 1 + numRows - 2;
        int rid = 0;

        for (int cid = 0; cid < numCols && pos < s.length(); cid++) {
            // 从上到下填充一整列
            if (cid % unitWidth == 0) {
                // Top down
                for (rid = 0; rid < numRows && pos < s.length(); rid++) {
                    arr[rid][cid] = s.charAt(pos++);
                }
                rid = numRows - 1;
            } else {
                // Bottom up
                arr[--rid][cid] = s.charAt(pos++);
            }
        }

        StringBuilder sb = new StringBuilder(s.length());
        for (int r = 0; r < numRows; r++) {
            for (int c = 0; c < numCols; c++) {
                if (arr[r][c] != 0)
                    sb.append(arr[r][c]);
            }
        }
        return sb.toString();
    }
}