Ziqzaq Dönüşüm LeetCode Həlli

Problem bəyanat

Ziqzaq Dönüşüm LeetCode Həlli – Simli "PAYPALISHIRING" a yazılır ziqzaq müəyyən sayda sətirdə nümunə: (daha yaxşı oxunmaq üçün bu nümunəni sabit şriftdə göstərmək istəyə bilərsiniz)

P   A   H   N
A P L S I I G
Y   I   R

Və sonra sətir-sətir oxuyun: "PAHNAPLSIIGYIR"

Bir sətir götürəcək kodu yazın və bir neçə sətir verilməklə bu çevrilməni həyata keçirin:

sətir çevirmə (string s, int numRows);

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Izahat

Hər dövrün ölçüsü "dövr" kimi müəyyən edilir.

cycle = (2*nRows - 2), except nRows == 1.


Bu misalda (2*nRows – 2) = 4.

Hər dövrdə birinci və sonuncu cərgə istisna olmaqla, hər bir sıra 2 elementə malikdir.

Tutaq ki, cari sıra i-dir, birinci elementin indeksi j-dir:

j = i + cycle*k, k = 0, 1, 2, ...


İkinci elementin indeksi ikinci J-dir:

secondJ = (j - i) + cycle - i


(ji) cari dövrün başlanğıcıdır, (ji) + dövr növbəti dövrün başlanğıcıdır.

Saxta kod:

1. kənar hərfləri yoxlayın (numRows = 1)
2. StringBuffers massivini işə salın.
3. Dəyişən indeksə uyğun olaraq StringBuffer-i düzəltmək üçün giriş sətirindəki hər simvolu əlavə edin
4. bütün StringBufferləri birinə birləşdirin və birləşməni qaytarın

Qeydlər:

1. Ağır string manipulyasiyamız olduqda StringBuffers Strings-dən daha yaxşıdır
2. Biz ziqzaq xarakteristikasını həyata keçirən aşağıda müzakirə olunan dəyişkən indeksi həyata keçirəcəyik

Əsas fikir:
Biz StringBuffers massivini (numRows ölçülü) yaradırıq. Daha sonra giriş sətirinin i mövqeyindəki hər simvolu 0 və numRows – 1 arasında dəyişən indeksdə StringBuffer-ə əlavə edirik. Nəhayət, biz bütün StringBufferləri bir StringBuffer-ə birləşdirə və həmin birləşməni qaytara bilərik. Ən vacib anlayışlar (1) 0 və numRows arasında dəyişən bir indeksin olacağıdır - ziqzaq çevrilməsini simulyasiya edəcək 1 və (2) bizdə ziqzaq şəkildə əldə ediləcək bir sıra StringBuffers olacaq. bu dəyişkən indeks.

Məsələn, əgər numRows = 4 və sətir “AMAZONISHIRING” olarsa
idx -> 0, 1, 2, 3, 2, 1, 0, 1, 2, 3, 2, 1, 0, 1, 2, …
i -> 0, 1, 2, 3, 4, 5, 6, 7, …

Belə ki,
A, StringBuffer massivinin idx 0-da StringBuffer-ə əlavə olunur
M, StringBuffer massivinin idx 1-də StringBuffer-ə əlavə olunur.
A -> massiv[2]
Z -> massiv[3]
O -> massiv[2]
N -> massiv[1]

Kodu

Ziqzaq çevrilməsi üçün C++ kodu

class Solution {
public:
    string convert(string s, int numRows) {
        string result="";
        if(numRows==1)
      return s;
        int step1,step2;
        int len=s.size();
        for(int i=0;i<numRows;++i){
            step1=(numRows-i-1)*2;
            step2=(i)*2;
            int pos=i;
            if(pos<len)
                result+=s.at(pos);
            while(1){
                pos+=step1;
                if(pos>=len)
                    break;
        if(step1)
          result+=s.at(pos);
                pos+=step2;
                if(pos>=len)
                    break;
        if(step2)
          result+=s.at(pos);
            }
        }
        return result;
    }
};

Ziqzaq çevrilməsi üçün Java kodu

class Solution {
    public String convert(String s, int numRows) {
        String ans="";
        if(numRows==1) return s;
        for (int i=0;i<numRows;i++) {
            int incr=2*(numRows-1);
            for (int j=i;j<s.length();j+=incr) {
                ans+=s.charAt(j);
                if(i>0 && i<numRows-1 && j+incr-(2*i)<s.length()) ans+=s.charAt(j+incr-(2*i));
            } 
        }
        return ans;
    }
}

Ziqzaq Konversiya LeetCode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

O (n)

Kosmik Mürəkkəblik

O (1)