06. Z字形變換

06. Z字形變換

難度中等610收藏分享切換為英文關注反饋

將一個給定字符串根據(jù)給定的行數(shù)，以從上往下、從左到右進行 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)這個將字符串進行指定行數(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

解法一：利用周期特性

根據(jù)z字排列的特性，發(fā)現(xiàn)字符串成周期排列，周期為2 * numRows -2，
發(fā)現(xiàn)第n行的元素，為每個周期的第i個或者第（周期-i）個

    public static String convert1(String s, int numRows) {
        if(numRows == 1) return s;
        int len = s.length();
        int cycle = 2 * numRows -2;
        StringBuilder sBuffer = new StringBuilder(len);
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < len; j++) {
                if (j % cycle == i || j % cycle == (cycle - i)) {
                    sBuffer.append(s.charAt(j));
                }
            }
        }       
        return sBuffer.toString();
    }

時間復雜度：O(n)，其中 n == len（s）* numRows。每個索引被訪問 numRows 次。
空間復雜度：O(n)。創(chuàng)建了一個 len（s）大小的StringBuilder。

解法二：第一種解法的升級

去掉了跳過了許多沒必要的檢測，省去了大量的時間

算法：

每次一行一行訪問，對于第k個周期：

  • 首先，先對邊界行，做出判斷：
    • 第0行字符位于 k * ( 2 * numRows - 2 ) 處
    • 第numRows - 1 行中字符位于索引 k * （ 2 * numRows -2 ）+numRow - 1
  • 其次，處理中間一般行：
    • 第i行中的字符位于索引 k * （ 2 * numRows - 2 ）+ i 以及（ k + 1）*（2 * numRows - 2 ）- i 處
    public static String convert2(String s, int numRows) {
        if(numRows == 1) return s;
        int len = s.length();
        int cycle = 2 * numRows -2;
        StringBuilder sBuilder = new StringBuilder(len);
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j + i < len; j += cycle) {
                sBuilder.append(s.charAt(j + i));
                if (i != 0 && i != numRows - 1 && j + cycle - i < len)
                    sBuilder.append(s.charAt(j + cycle - i));
            }
        }
        return sBuilder.toString();
    }

解法三：按行排序

思路：

遍歷字符串，判斷確定字符屬于Z字形的哪一行，然后放在對于的行。

算法：

我們可以遍歷一遍字符串，可以使用當前行和當前方向兩個變量來對合適的行進行跟蹤。

只有當我們向上移動到最上面或者向下移動到最下面時，才會更改方向。

public static String convert3(String s, int numRows) {
    if(numRows == 1) return s;
    
    List<StringBuilder> rows = new ArrayList<>();
    
    //創(chuàng)建結果行集合（每行元素按照StringBuilder存放）
    for(int i = 0; i<Math.min(numRows, s.length());i++) {
        rows.add(new StringBuilder());
    }
    
    //當前行序號
    int curRow = 0;
    
    //direction 為方向，false 為向上，true為向下。
    boolean direction = false;
    
    for (char c : s.toCharArray()) {
        rows.get(curRow).append(c);
        if(curRow == 0 || curRow == numRows -1 ) {
            direction = !direction;
        }
        //direction為true表示向下，false表示向上
        curRow += direction ? 1 : -1;
    }
            
    StringBuffer result = new StringBuffer();
    for (StringBuilder row : rows) {
        result.append(row);
    }
    return result.toString();       
}

測試類：

package com.company.project.hot100;

import java.util.List;
import java.util.ArrayList;

/*
 * 6. Z 字形變換
將一個給定字符串根據(jù)給定的行數(shù)，以從上往下、從左到右進行 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)這個將字符串進行指定行數(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
 */
public class Question06 {

    /**
     *  解法一：利用周期特性
     * 根據(jù)z字排列的特性，發(fā)現(xiàn)字符串成周期排列，周期為2 * numRows -2，
     * 發(fā)現(xiàn)第n行的元素，為每個周期的第i個或者第（周期-i）個
     * @param s
     * @param numRows
     * @return
     */
    public static String convert1(String s, int numRows) {
        if(numRows == 1) return s;
        int len = s.length();
        int cycle = 2 * numRows -2;
        StringBuilder sBuilder = new StringBuilder(len);
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < len; j++) {
                if (j % cycle == i || j % cycle == (cycle - i)) {
                    sBuilder.append(s.charAt(j));
                }
            }
        }       
        return sBuilder.toString();
    }

    
    /**
     * 解法二：第一種解法的升級
     * 去掉了跳過了許多沒必要的檢測，省去了大量的時間
     * 
     * 算法：
     * 
     * @param s
     * @param numRows
     * @return
     */
    public static String convert2(String s, int numRows) {
        if(numRows == 1) return s;
        int len = s.length();
        int cycle = 2 * numRows -2;
        StringBuilder sBuilder = new StringBuilder(len);
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j + i < len; j += cycle) {
                sBuilder.append(s.charAt(j + i));
                if (i != 0 && i != numRows - 1 && j + cycle - i < len)
                    sBuilder.append(s.charAt(j + cycle - i));
            }
        }
        return sBuilder.toString();
    }
    
    /**
     * 解法三：按行分組
     * 我們可以遍歷一遍字符串，可以使用當前行和當前方向兩個變量來對合適的行進行跟蹤。
     * 只有當我們向上移動到最上面或者向下移動到最下面時，才會更改方向。
     * @param s
     * @param numRows
     * @return
     */
    public static String convert3(String s, int numRows) {
        if(numRows == 1) return s;
        
        List<StringBuilder> rows = new ArrayList<>();
        
        //創(chuàng)建結果行集合（每行元素按照StringBuilder存放）
        for(int i = 0; i<Math.min(numRows, s.length());i++) {
            rows.add(new StringBuilder());
        }
        
        //當前行序號
        int curRow = 0;
        
        //direction 為方向，false 為向上，true為向下。
        boolean direction = false;
        
        for (char c : s.toCharArray()) {
            rows.get(curRow).append(c);
            if(curRow == 0 || curRow == numRows -1 ) {
                direction = !direction;
            }
            //direction為true表示向下，false表示向上
            curRow += direction ? 1 : -1;
        }
                
        StringBuffer result = new StringBuffer();
        for (StringBuilder row : rows) {
            result.append(row);
        }
        return result.toString();       
    }
    
    
    public static void main(String[] args) {
        String s = "LEETCODEISHIRING";
        int numRows = 4;
        System.out.println(convert3(s, numRows));
    }
}
?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容