6. Z 字形變換

題目描述

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

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

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

之后，你的輸出需要從左往右逐行讀取，產(chǎn)生出一個新的字符串，比如："LCIRETOESIIGEDHN"。
請你實現(xiàn)這個將字符串進(jìn)行指定行數(shù)變換的函數(shù)：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

算法思想

假設(shè)輸入字符串 s 為 "LEETCODEISHIRING"， numRows 為 4，而目標(biāo)字符串是按行打印。因此，可以使用數(shù)組來存放每一行的字符串，如下圖所示：

現(xiàn)在需要解決的問題就是如果將原字符串存放到字符串?dāng)?shù)組？其本質(zhì)還是遍歷原字符串，然后找到每個字符對應(yīng)的下標(biāo)位置 index 與 numRows 之間的關(guān)系，可以發(fā)現(xiàn)每 2 * numRows - 2 為一個循環(huán)周期。

代碼實現(xiàn)

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        StringBuilder result = new StringBuilder();
        // 用數(shù)組來存放每一行的字符串
        String[] arr = new String[numRows];
        Arrays.fill(arr, "");
        // 循環(huán)周期
        int period = 2 * numRows - 2;
        for (int i = 0; i < s.length(); i++) {
            int mod = i % period;
            if (mod < numRows) {
                arr[mod] = arr[mod] + s.charAt(i);
            } else {
                arr[period - mod] = arr[period - mod] + s.charAt(i);
            }
        }

        for (int i = 0; i < numRows; i++) {
            result.append(arr[i]);
        }

        return result.toString();
    }
}