分享Z字形排列字符串的解法，包括二維矩陣模擬、行模擬（壓縮矩陣、代碼精簡）、偽直接構建和真直接構建，真直接構建需處理周期和行字符數，直接拼接結果字符串。

題目：將一個給定字符串 s 根據給定的行數 numRows ，以從上往下、從左到右進行 Z 字形排列。

這一題作為中等難度，下面和大家分享幾種不同的解法。

01、二維矩陣模擬法

所謂二維矩陣模擬法就是首先構建一個二維矩陣，然后按照題目要求把字符串從上到下，從左到右，把字符一個一個排列到二維矩陣中，然后按行遍歷二維矩陣把字符拼接起來即可。

根據上面整體思路，我們可以分為以下幾個步驟：

（1）特殊情況處理，對于行數入參為1行，或者字符串長度小于行數入參，可以直接返回字符串無需處理；

（2）構建行數為行數入參，列數為字符串長度的二維矩陣，并把字符串所有字符填充至二維矩陣中；

安裝題目要求應該是Z字形，也可以理解成倒N字，其實我們可以稍微變通一下，我們組成一個W形效果也是一樣的

經過小小的變形最終效果是一樣的，雖然二維矩陣空間變大了，但是我們處理難度會大大降低。因為對于W形列索引只需要以1為步長向前移動即可，而無需像Z字形需要復雜的判斷。而行索引兩者處理方式相同，從第1行開始向下移動時候步長為1，當到最后1行后步長改為-1，變為向上移動。

這就是為什么二維矩陣的列數選擇為字符串長度的原因，可以大大降低處理難度。

（3）按行遍歷二維矩陣，并取非空字符，拼接出結果。

具體代碼如下：

//二維矩陣模擬法
public static string Matrix(string s, int numRows)
{
    //行數為 1 或者字符串長度小于等于行數，直接返回原字符串
    if (numRows == 1 || s.Length <= numRows)
    {
        return s;
    }
    //構建二維矩陣，用于存儲 Z 字形排列的字符
    var matrix = new char[numRows, s.Length];
    //當前行索引
    var rowIndex = 0;
    //行移動步長，向下移動步長為 1 ，向上移動步長為 -1
    var rowStep = 1;
    //遍歷字符串
    for (var i = 0; i < s.Length; i++)
    {
        //將當前字符放入二維矩陣中對應的位置
        matrix[rowIndex, i] = s[i];
        if (rowIndex == 0)
        {
            //如果當前行是第一行，則改變行為 1
            //代表字符移動方向為向下
            rowStep = 1;
        }
        else if (rowIndex == numRows - 1)
        {
            //如果當前行是最后一行，則改變行為 -1
            //代表字符移動方向為向上
            rowStep = -1;
        }
        // 根據行步長更新當前行的索引
        rowIndex += rowStep;
    }
    //用于存儲最終結果的字符串
    var result = new StringBuilder();
    //遍歷二維矩陣的行
    for (var r = 0; r < numRows; r++)
    {
        //遍歷二維矩陣的列
        for (var c = 0; c < s.Length; c++)
        {
            //不為空的字符添加到結果字符串中
            if (matrix[r, c] != 0)
            {
                result.Append(matrix[r, c]);
            }
        }
    }
    // 返回最終的 Z 字形變換后的字符串
    return result.ToString();
}

02、行模擬法（壓縮矩陣）

可以發現二維矩陣模擬法還是比較簡單的，也吻合我們直觀的思維習慣，但是也有一個很大的缺陷，無論是Z字形還是W字形就是浪費很多空間。

因此我們可以對二維矩陣模擬法進行改進，把其行進行壓縮，因為最后我們需要以行來展示最終結果，因此我們只需要每一行構建一個字符串，相關行字符串只需要拼接至當前行字符串結尾即可，這樣可以最大限度節省空間，需要多少用多少。

該方法需要解決一個核心問題——行索引計算。

再我們需要動態計算一個值時，同時需要找出其規律，要不是公式規律，要不就是周期規律，而本題是在重復Z字形，顯然更符合周期規律。而如果以第一行第一個字符為起點，則終點為下個第一行第一個字符之前的一個字符。也就是第一行只有起點一個點，而最后一行只有拐點一個點。因此可以得出周期公式為：[period = numRows * 2 - 2]。

同時行數是入參是已知的，因此我們就可以通過當前字符在當前周期的哪個位置[i % period]，再與拐點位置比較確定行索引的前進方向即可。

下面我們一起看看具體代碼；

//行模擬法（壓縮矩陣）
public static string Row(string s, int numRows)
{
    //行數為 1 或者字符串長度小于等于行數，直接返回原字符串
    if (numRows == 1 || s.Length <= numRows)
    {
        return s;
    }
    //構建字符串數組，每一個StringBuilder代表一行所有字符
    var rows = new StringBuilder[numRows];
    for (int i = 0; i < numRows; ++i)
    {
        rows[i] = new StringBuilder();
    }
    //當前行索引
    var rowIndex = 0;
    // Z 字形變換周期
    var period = numRows * 2 - 2;
    //遍歷字符串
    for (int i = 0; i < s.Length; ++i)
    {
        //將當前字符添加到相對應行的末尾
        rows[rowIndex].Append(s[i]);
        //計算當前字符在周期內的那個位置
        //以最后一行的元素為分界線
        //一個周期前半部分為向下移動
        //后半部分為向上移動
        if (i % period < numRows - 1)
        {
            //向下移動
            ++rowIndex;
        }
        else
        {
            //右上移動
            --rowIndex;
        }
    }
    //把字符串數組拼接為最終結果
    var result = new StringBuilder();
    foreach (var row in rows)
    {
        result.Append(row);
    }
    return result.ToString();
}

03、行模擬法（代碼精簡）

對于有代碼潔癖的我，對上一個解法做了寫代碼精簡，主要精簡了三塊代碼。

（1）字符串數組構建；

這里通過使用Array.ConvertAll方法實現字符串數組的聲明與初始化合二為一。

（2）行索引計算方式；

這里利用周期內關于拐點對稱性，直接計算出行索引。如果當前字符所在周期索引為periodIndex，則其對稱索引為period – periodIndex，而行號則為兩者中較小值。

（3）字符串數組拼接字符串；

而拼接方式我們可以直接使用string.Join的重載方法直接拼接。

具體代碼如下：

//行模擬法（代碼精簡）
public static string RowCompact(string s, int numRows)
{
    //行數為 1 或者字符串長度小于等于行數，直接返回原字符串
    if (numRows == 1 || s.Length <= numRows)
    {
        return s;
    }
    //構建字符串數組，每一個StringBuilder代表一行所有字符
    var rows = Array.ConvertAll(new StringBuilder[numRows], _ => new StringBuilder());
    // Z 字形變換周期
    var period = 2 * numRows - 2;
    for (var i = 0; i < s.Length; i++)
    {
        //計算當前字符在周期內的那個位置
        var periodIndex = i % period;
        //獲取當前行索引，利用周期內對稱性，取最小值確保rowIndex不超過周期的中點
        var rowIndex = Math.Min(periodIndex, period - periodIndex);
        rows[rowIndex].Append(s[i]);
    }
    return string.Join<StringBuilder>("", rows);
}

04、偽直接構建

前面的方法的思路都是類似的，是先構建行數組，然后把每行字符串拼接好后，再拼接成最終結果。那我們是否可以不去構建行數組，而是直接構建最終字符串呢？

通過前面的解法我們得到Z字形變換周期，這就意味著我們可以根據周期有一次只處理一行字符的條件。而其中重點就是首行和尾行都只有一個字符，而中間的行最多有兩個字符。

這樣我們就可以循環行數，一行一行構建結果字符串了，具體實現代碼如下：

//偽直接構建
public static string Build(string s, int numRows)
{
    //行數為 1 或者字符串長度小于等于行數，直接返回原字符串
    if (numRows == 1 || s.Length <= numRows)
    {
        return s;
    }
    //定義結果動態字符串
    var result = new StringBuilder();
    // Z 字形變換周期
    var period = numRows * 2 - 2;
    //遍歷行
    for (var i = 0; i < numRows; ++i)
    {
        //遍歷每個周期的起始位置，從 0 開始，步長為 period
        for (var j = 0; j + i < s.Length; j += period)
        {
            //當前周期的第一個字符，添加至結果中
            result.Append(s[j + i]);
            //根據 Z 字形特性，在一個周期內
            //除了第一行和最后一行只有一個字符
            //其他行則至少有一個字符，最多有兩個字符
            //因此下面除了第一行和最后一行外，處理當前周期第二個字符
            if (0 < i && i < numRows - 1 && j + period - i < s.Length)
            {
                result.Append(s[j + period - i]);
            }
        }
    }
    return result.ToString();
}

我之所以稱此法為偽直接構建，因為我認為還不夠直接，我認為的直接構建是：遍歷字符串后直接構建出結果。

05、真直接構建

通過前面的方法，關于Z 字形變換周期計算，關于行的計算，都已經有相應的辦法，因此理論上我們是可以通過直接遍歷字符串而直接拼接出結果字符串。我們可以梳理一下大致思路。

（1）首先我們構建一個字符數組，擁有存放所有字符；

（2）在這個字符數組中，我們需要動態計算出每一行字符一共站了多少字符，只有這樣才能確定下一行第一個字符的起始位置，也就是相當于我們需要動態把字符數組分成n段，每一段代表一行字符；

（3）需要單獨處理最后一個周期，因為最后一個周期字符是不確定的，而且它會影響每一行字符的總數，因此需要分類處理好，才能保證第（2）點的計算正確；

因此如果我們需要計算當前行之前行的所有字符總數，則可以分為兩部分即完整周期+最后一個周期。

以上圖為例，行數為5，最后一個周期字符可能是A-H，即1-8個任意個數，我們需要找到其中規律來確定最后一個周期中，每一行占了多少個字符。

如果以紅色橫線表示當前處理行，紅色豎虛線為周期對稱線，則可以把最后一個周期中最后一個字符分布在1、2、3、4四個區域中總結為以三種情況。

（1）當最后字符在1區域，則當前行之前所有行的最后一個周期字符總數為最后字符的索引；

（2）當最后字符在3、4區域，則當前行之前所有行的最后一個周期字符總數為當前行號減1；

（3）當最后字符在2區域，則當前行之前所有行的最后一個周期字符總數為最后字符的索引減去3、4區域的總字符數；

如此我們就可以一次直接構建出結果字符串，當然其中還有一些細節需要處理，比如中間行都有兩個字符，而第二個字符需要格外注意，下面我們直接看看整體實現代碼：

//真直接構建
public static string Build2(string s, int numRows)
{
    //行數為 1 或者字符串長度小于等于行數，直接返回原字符串
    if (numRows == 1 || s.Length <= numRows)
    {
        return s;
    }
    //定義結果字符數組
    var result = new char[s.Length];
    // Z 字形變換周期
    var period = 2 * numRows - 2;
    //總的周期數
    var totalPeriod = (s.Length + period - 1) / period;
    //最后一個字符的周期索引
    var lastPeriodIndex = s.Length % period;
    lastPeriodIndex = lastPeriodIndex == 0 ? (period - 1) : (lastPeriodIndex - 1);
    //遍歷字符串
    for (var i = 0; i < s.Length; i++)
    {
        //當前字符串周期索引
        var periodIndex = i % period;
        //當前行索引
        var rowIndex = Math.Min(periodIndex, period - periodIndex);
        //當前字符索引，以在第幾個周期為基礎
        var index = (i / period);
        //處理非第一行情況
        if (rowIndex > 0)
        {
            //當前行的起始索引為此行之前所有行的所有字符總和
            //第一行總字符數為總周期數
            //第二行總字符數為分為兩部分之后，
            //第一部分是(totalPeriod - 1)個周期，此部分每個周期有2個元素，
            //第二部分是最后一個周期中此行的字符個數，需要動態計算
            index += totalPeriod + (totalPeriod - 1) * 2 * (rowIndex - 1);
            //除首尾行外中間行最多有兩個字符
            if (rowIndex != numRows - 1)
            {
                //第二個字符索引起始需要在第幾個周期為基礎上在加一個第幾個周期
                index += (i / period);
            }
            //判斷最后一個字符周期索引所在位置
            //動態計算此行之前最后一個周期中包含幾個字符
            if (lastPeriodIndex < rowIndex)
            {
                //小于當前行數，則包含最后一個周期的所有字符
                index += lastPeriodIndex;
            }
            else if (lastPeriodIndex < period - rowIndex)
            {
                //小于當前字符對稱點，則包含當前行數減1個字符
                index += rowIndex - 1;
            }
            else
            {
                //否則包含最后一個周期所有字符減去此行下面所有行最后一個周期的所有字符
                index += lastPeriodIndex - ((numRows - 1 - rowIndex) * 2 + 1);
            }
        }
        if (periodIndex <= numRows - 1)
        {
            //處理所有行的第一個字符
            result[index] = s[i];
        }
        else
        {
            //處理中間行第二個字符
            result[index + 1] = s[i];
        }
    }
    return new string(result);
}

注：測試方法代碼以及示例源碼都已經上傳至代碼庫，有興趣的可以看看。https://gitee.com/hugogoos/Planner