Leetcode是許多歐美IT公司招聘工程師經常使用的演算法題庫，學習演算法最重要的是不斷積累。
今天我們來看一道
字串
相關的題目
6。 ZigZag Conversion
問題描述：
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）
P A H NA P L S I I GY I R
And then read line by line： “PAHNAPLSIIGYIR”
Write the code that will take a string and make this conversion given a number of rows：
string convert（string s， int numRows）；
Example 1:
Input： s = “PAYPALISHIRING”， numRows = 3Output： “PAHNAPLSIIGYIR”
Example 2:
Input： s = “PAYPALISHIRING”， numRows = 4Output： “PINALSIGYAHRPI”Explanation：P I NA L S I GY A H RP I
問題分析
-1。 字串處理問題，但是首先要理解 ZigZag的意思。ZigZag就是類似上山的小路，蜿蜒曲折 ：-）
-2。題目給出的是一個字串，和一個預定輸出的行數。
-3。這題的難度在於怎麼尋找曲折輸出字串的規律
解決方案：
Solution : 從給出的sample中我們可以發現如下規律：
1。判斷特殊情況，當numRows==1的時候，直接輸出S就可以了。
2。不然的話，我們進入我們的處理邏輯，定義好左右兩個步伐變數，step1，step2
3。迴圈的從字串左到右掃描。
4。根據我們從上面分析的 ZigZag規律圖我們發現：每兩個豎列上面的字元的同行的間隔是固定的，
符合：
step1+step2 = 2*numRows - 2
5。所以我們定義
step1= （numRows - 1 -i）*2，
step2= i*2；
6。然後我們使用StringBuilder快取並追加遍歷到的結果，最後轉化成string輸出
時間複雜度O(n),不要額外的空間複雜度。
總結：
這是一道中等難度的題，然是有很多細節的地方會阻止你寫出“
簡單易讀
”且“
無邏輯錯誤
”的程式碼。
本題有幾個地方需要注意：
ZigZag的定義和規律
怎麼處理字串，怎麼快取結果
注意每兩個
豎行
之間的 間距處理。
最好使用StringBuilder或者StringBuffer，以免生成太多的碎片化string。
關注，轉發和收藏“松鼠遊學”，
每日更新
"Leetcode"
演算法相關的面試題和解題方案並附上原始碼，歡迎有興趣的小夥伴私信私聊！
@極限尤可突破，至臻亦不可止!
