之字形轉換


難度級別
經常問 貝寶

在鋸齒形轉換問題中,我們給出了 長度為n的s和代表行數的整數r。 以r行的鋸齒形轉換給定的字符串,並將字符按行連接。 打印新的串聯字符串。

之字形轉換

輸入: 

s =“ TutorialCup”

R = 3

輸出: TrCuoilutap

輸入: 

s =“編程”

R = 4

輸出: 莫拉莫里根

鋸齒形轉換的說明

令字符串s =“ TutorialCup”和行數,即r = 3

初始化大小為r的字符串數組a []以形成鋸齒形圖案。 另外,初始化整數變量行以將當前行跟踪為0,並將布爾變量向下跟踪。

開始遍歷字符串,並如下更新字符串數組。 以下是上述示例的步驟–

  • 1:行= 0,向下= true,a [] = T
  • 2:行= 1,向下= true,a [] = T,u
  • 3:行= 2,向下=否,a [] = T,u,t
  • 4:行= 1,向下= true,a [] = T,uo,t
  • 5:行= 0,向下= true,a [] = Tr,uo,t
  • 6:行= 1,向下= true,a [] = Tr,uoi,t
  • 7:行= 2,向下=否,a [] = Tr,uoi,ta
  • 8:行= 1,向下= true,a [] = Tr,uoil,ta
  • 9:行= 0,向下= true,a [] = TrC,uoil,ta
  • 10:行= 1,向下= true,a [] = TrC,uoilu,ta
  • 11:行= 2,向下=否,a [] = TrC,uoilu,點擊

因此,結果字符串是TrCuoilutap

之字形轉換算法

  1. 初始化長度為n的字符串s和代表行數的整數r。
  2. 如果給定的行數(r)為1,則返回字符串。
  3. 創建一個大小為r的字符串類型的數組。
  4. 將行初始化為0,然後初始化為布爾類型。
  5. 從0遍歷到n-1,並將字符串的字符存儲在索引行的字符串數組中。
  6. 檢查該行是否等於r-1,將其更新為false。
  7. 否則,如果該行為0,則更新為true。
  8. 如果down為true,則增加該行,否則減少該行。
  9. 打印更新的字符串數組。

曲折轉換的C ++程序

#include<bits/stdc++.h> 
using namespace std; 
  
void ZigZag(string s, int r){ 
    
    if(r == 1){ 
        cout<<s;       
        return; 
    }    
  
    int n = s.length(); 
  
    string a[r]; 
  
    int row = 0; 
    bool down; 
    
    for(int i=0; i<n; ++i){ 
        
        a[row].push_back(s[i]); 
  
        if(row == r-1) 
          down = false; 
  
        else if (row == 0) 
          down = true; 
  
        (down)? (row++): (row--); 
    } 
  
    for(int i=0; i<r; ++i) 
        cout<<a[i]; 
} 

int main(){ 
    string s = "TutorialCup"; 
    int r = 3; 
    ZigZag(s, r); 
    return 0; 
}
TrCuoilutap

用於鋸齒形轉換的Java程序

import java.util.Arrays; 
  
class Concatenate{ 
  
    static void ZigZag(String s, int r){ 
  
        if(r == 1){ 
            System.out.print(s); 
            return; 
        } 
        
        char[] str = s.toCharArray(); 
  
        int n = s.length(); 
  
        String[] a = new String[r]; 
        Arrays.fill(a, ""); 
  
        int row = 0; 
        boolean down = true;
        
        for(int i=0; i<n; ++i){ 
            
            a[row] += (str[i]); 
  
            if(row == r-1){ 
                down = false; 
            }  
              
            else if(row == 0){ 
                down = true; 
            } 
  
            if(down){ 
                row++; 
            }  
            else{ 
                row--; 
            } 
        } 
  
        for(int i=0; i<r; ++i){ 
            System.out.print(a[i]); 
        } 
    } 
  
    public static void main(String[] args){
        
        String s = "TutorialCup"; 
        int r = 3; 
        ZigZag(s, r);
        
    } 
}
TrCuoilutap

之字形轉換的複雜度分析

時間複雜度: O(n)其中n是輸入字符串的大小。

輔助空間: O(n),因為我們在計算答案時將答案存儲在數組(字符串類型)中。

參考