題目鏈接

https://leetcode-cn.com/problems/zigzag-conversion/

題目描述

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

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

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

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

請你實現這個將字符串進行指定行數變換的函數：

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

解題方案

思路

• 標簽：字符串

• 整體的思路是遍歷字符串，遍歷過程中將每行都看成新的字符串構成字符串數組，最后再將該數組拼接起來即可

• 如果numRows=1則說明當前字符串即為結果，直接返回

• 否則整個字符串需要經歷，向下向右，向下向右，這樣的反復循環過程，設定down變量表示是否向下，loc變量表示當前字符串數組的下標

• 如果down為true，則loc+=1，字符串數組下標向后移動，將當前字符加入當前字符串中

• 如果down為false，則表示向右，則loc-=1，字符串數組下標向前移動，將當前字符加入當前字符串中

• 時間復雜度：O(n)，n為字符串s的長度

代碼

• Java版本

class Solution {
    public String convert(String s, int numRows) {
        if(numRows == 1)
            return s;
        
        int len = Math.min(s.length(), numRows);
        String []rows = new String[len];
        for(int i = 0; i< len; i++) rows[i] = "";
        int loc = 0;
        boolean down = false;

        for(int i=0;i<s.length();i++) {
            rows[loc] += s.substring(i,i+1);
            if(loc == 0 || loc == numRows - 1)
                down = !down;
            loc += down ? 1 : -1;
        }
        
        String ans = "";
        for(String row : rows) {
            ans += row;
        }
        return ans;
    }
}

• JavaScript版本

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function(s, numRows) {
    if(numRows == 1)
        return s;

    const len = Math.min(s.length, numRows);
    const rows = [];
    for(let i = 0; i< len; i++) rows[i] = "";
    let loc = 0;
    let down = false;

    for(const c of s) {
        rows[loc] += c;
        if(loc == 0 || loc == numRows - 1)
            down = !down;
        loc += down ? 1 : -1;
    }

    let ans = "";
    for(const row of rows) {
        ans += row;
    }
    return ans;
};

畫解