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

比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下： :::info P A H N
A P L S I I G
Y I R ::: 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，”PAHNAPLSIIGYIR”。

请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);

方法一：利用二维矩阵模拟

设Len为字符串s的长度。

当numRows=1或者完成Z字变换之后只有一列（numRows>Len）时，结果与原字符串相同，输出原结果即可。
对于一般情况，建立二维数组，将字符串按Z字变换顺序填入二维数组，然后再按行输出二维数组。

由题意得，输入字符时，会先向下输出numRows个字符，再向右上输出(numRows-2)个字符，并形成输入周期cycle=numRows+(numRows-2)=2numRows-2。
每周期会占用列数column=1+(numRows-2)=numRows-1列。

又已知字符串长度Len，即可获得字符串输入周期数Len/cycle，同时*column，即可获得二维数组的列数。

创建一个Len行column列的矩阵，然后遍历填写。初始位置在矩阵的左上角，记为(x,y)=(0,0)。当字符满足i mod t < numRows-1，向下移动，否则向右上移动。
最后逐行输出非空字符。

public class Solution
{
    public string Convert(string s, int numRows)
    {
        int Len = s.Length;
        // 排除特殊情况
        if (numRows == 1 || numRows >= Len)
        {
            return s;
        }
        int cycle = numRows * 2 - 2;// 循环的周期
        int column = (Len + cycle - 1) / cycle * (numRows - 1);  
        // 组建二维数组的列数
        // 为方便计算，将最后一个周期算作一个完整周期（不论周期是否完整）(Len + cycle - 1)
        char[][] mat = new char[numRows][];
        // 二维数组每行转化为一个一维数组
        for (int i = 0; i < numRows; ++i)
        {
            mat[i] = new char[column];
        }
        // 移动二维数组角标
        for (int i = 1, x = 0, y = 0; i < Len; i++)
        {
            mat[x][y] = s[i];
            if (i % cycle < numRows - 1)
            {
                ++x; // 向下移动
            }
            else
            {
                --x;
                ++y; // 向右上移动
            }
        }
        // 循环打印输出
        StringBuilder ans = new StringBuilder();
        foreach (char[] row in mat)
        {
            foreach (char ch in row)
            {
                if (ch != 0)
                {
                    ans.Append(ch);
                }
            }
        }
        return ans.ToString();
    }
}

方法二：压缩矩阵空间

方法一中的矩阵有大量的空间没有被使用，能否优化呢？

注意到每次往矩阵的某一行添加字符时，都会添加到该行上一个字符的右侧，且最后组成答案时只会用到每行的非空字符。因此我们可以将矩阵的每行初始化为一个空列表，每次向某一行添加字符时，添加到该行的列表末尾即可。

public class Solution
        {
            public string Convert(string s, int numRows)
            {
                int Len = s.Length;
                if (numRows == 1 || numRows >= Len)
                {
                    return s;
                }
                StringBuilder[] mat = new StringBuilder[numRows];
                for (int i = 1; i < numRows; i++)
                {
                    mat[i] = new StringBuilder();
                }
                for (int i = 1, x = 0, cycle = numRows * 2 - 2; i < Len; i++)
                {
                    mat[x].Append(s[i]);
                    if (i % cycle < numRows - 1)
                    {
                        ++x;
                    }
                    else
                    {
                        --x;
                    }
                }
                StringBuilder ans = new StringBuilder();
                foreach (StringBuilder row in mat)
                {
                    ans.Append(row);
                }
                return ans.ToString();
            }
        }