題目鏈接：Z 字形變換

方法一

——找規(guī)律模擬數(shù)組

題目要求構(gòu)造一個(gè)從左到右的Z型矩陣。

通過分析，可以看出這個(gè)Z型矩陣的特點(diǎn)

Z型矩陣就是如圖中的橙色，綠色這樣部分組合在一起的，Z型矩陣就是由一個(gè)個(gè)這樣相同周期組成的。

這里有一種情況需要特殊討論，當(dāng)矩陣只有一行時(shí)，直接返回原字符。

其余情況均可滿足。

其周期的構(gòu)成滿足這樣一個(gè)規(guī)律：

在第一列向下填寫矩陣行數(shù)r個(gè)字符，接著向其右上部分共(r-2)列分別填寫一個(gè)字符。Z型矩陣的周期t=r+r-2=2*r-2,每個(gè)周期會(huì)占用矩陣的r-1列，總共有 字符長(zhǎng)度len/t個(gè)周期(將最后一個(gè)周期視作完整周期)。

因此創(chuàng)建一個(gè)具有r行c列的的二維矩陣,(這里在計(jì)算列的時(shí)候需要多+一個(gè)周期，因?yàn)槌ǖ挠?jì)算會(huì)舍去余數(shù))。一開始從(0,0)這個(gè)位置開始填寫字符，通過判斷i%t與r-1的大小決定向上移動(dòng)還是向下移動(dòng)。

共兩種情況：

i%t<r-1 ：說明這時(shí)矩陣正在填寫第一列的數(shù)字，這時(shí)只需要向下移動(dòng)

i%t>=r-1:說明第一列已經(jīng)填寫好了，這時(shí)需要向右上方進(jìn)行填寫字符，所以需要向右移動(dòng)一位，向上移動(dòng)一位。

當(dāng)一個(gè)周期運(yùn)行完時(shí)，又會(huì)回到新周期的第一列。

再次遍歷矩陣，將存儲(chǔ)有字符的位置加入到一個(gè)新的字符串中。

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows==1||numRows>=s.size())//特殊情況進(jìn)行排除
        return s;
      int r=numRows;//矩陣的行數(shù)
      int t=2*r-2;//周期所含字符個(gè)數(shù)
      int len=s.size();//字符串的長(zhǎng)度
      int c=(len+t)/t*(r-1);//二維矩陣列數(shù)
      vector<string> v1 (r,string(c,0));
    for(int i=0, x=0,y=0;i<len;i++){
        v1[x][y]=s[i];
        
        if(i%t<r-1){
            x++;//向下移動(dòng)
        }
        else{
            x--;//向上移動(dòng)
            y++;//向右移動(dòng)
        }  
    }
    string ans;
    for(int i=0;i<r;i++){//遍歷矩陣，掃描字符并添加
        for(int j=0;j<c;j++){
            if(v1[i][j])
            ans+=v1[i][j];
        }
    }
    return ans;
    }
};

時(shí)間復(fù)雜度=o(nr)

空間復(fù)雜度=o(nr)

方法二

——壓縮矩陣

在第一種方法，需要構(gòu)造一個(gè)二維矩陣，但是其實(shí)只使用了其中的部分空間，這樣就導(dǎo)致浪費(fèi)了許多空間，因此可以對(duì)矩陣進(jìn)行壓縮。

依舊是將矩陣只有一行的情況進(jìn)行額外討論，若成立，直接返回原字符串。 反之，創(chuàng)建一個(gè)r行1列的的string數(shù)組，通過判斷字符i的位置(與第一種方法的判斷方式一樣)，直接將字符填寫到數(shù)組的對(duì)應(yīng)行。 舉例說明：

這個(gè)Z型字符在模擬數(shù)組是這樣呈現(xiàn)的：

class Solution {
public:
    string convert(string s, int numRows) {
    int len=s.size();//字符串長(zhǎng)度
    int r=numRows;//矩陣行數(shù)
    int t=2*r-2;//周期所含字符個(gè)數(shù)
     if (r == 1) {
            return s;
        }
    vector<string> v1(r);
    int x=0;
        for(int i=0;i<len;i++){
            v1[x]+=s[i];
            if(i%t<r-1)
            x++;//向下移動(dòng)
            else
            x--;//向上移動(dòng)
        }
        string ans;
        for (auto &row : v1) {//遍歷矩陣，掃描字符并添加
            ans += row;
        }
    return ans;
    }
};

時(shí)間復(fù)雜度:o(n)

空間復(fù)雜度:o(n)

到此這篇關(guān)于C語言詳解Z字形變換排列的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C語言Z字形變換內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論