先看題：

將一個給定字符串?s?根據(jù)給定的行數(shù)?numRows?，以從上往下、從左到右進行?Z 字形排列。

比如輸入字符串為?"PAYPALISHIRING"?行數(shù)為?3?時，排列如下：

之后，你的輸出需要從左往右逐行讀取，產(chǎn)生出一個新的字符串，比如："PAHNAPLSIIGYIR"。

解法很多，暴力一下也很好寫，這里記錄兩個比較巧妙的解法。

一、通過直接構(gòu)造，來計算答案每一行的的字母所對應(yīng)的下標(biāo)

觀察可得，對于一個行數(shù)為numRows的輸入，將每（numRows+numRows-2）個字符劃為一個周期。在每個周期內(nèi)，第一行和第numRows行只有一個字符，中間的行會有兩個字符。這些字符所對應(yīng)的下標(biāo)都能通過行數(shù)和周期數(shù)計算出來（具體參數(shù)略），因此只需要遍歷行數(shù)作為外循環(huán)，遍歷周期數(shù)作為內(nèi)循環(huán)即可。

需要注意的是要對最后一個不完整周期作額外判斷，防止越界。

時間復(fù)雜度：O(n) ，雖然看上去是雙重循環(huán)，但實際上輸入串s的每個位置只被訪問過一次，本質(zhì)上是一個對輸入串s的遍歷。

空間復(fù)雜度：O(1)，無需額外變量。

二、模擬N字形構(gòu)造過程

在這個解法中我們需要numRows個數(shù)組，用于記錄每一行的結(jié)果。

根據(jù)題意，在numRows = 3 時，在把輸入串s構(gòu)造成這樣N字型的時候，我們是遍歷s，把每一個字符挨個順著1、2、3行放入，再逆向回到2、1行，再逆向2、3行。

枚舉一下就是s[0]在第一行，s[1]在第二行，s[2]在第三行，s[3]在第二行，s[4]在第一行，s[5]在第二行，s[6]在第三行……

因此我們只需要遍歷一遍s，并用一個變量記錄當(dāng)前到第幾行，把對應(yīng)的字符放到對應(yīng)的行的數(shù)組中儲存即可。這個用于記錄第幾行的變量，在到達numRows行和第一行的時候翻轉(zhuǎn)計數(shù)，即可。通常額外采用一個flag=1或者-1來表示是在向上走還是在向下走。

需要注意的是數(shù)組下標(biāo)和對應(yīng)變量的相統(tǒng)一。

時間復(fù)雜度：O(n)?

空間復(fù)雜度：O(n)

總結(jié)：方法1空間開銷更小，但代碼寫起來略微復(fù)雜；方法2簡單易懂，代碼量少，通過flag來記錄上下行的方法簡單有效且巧妙，但對應(yīng)需要空間開銷。