Simli sıxılma LeetCode Həlli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg ByteDance Cisco Citrix eBay Expedia Facebook Goldman Sachs google IBM microsoft Nutanix Nvidia Snapchat Viza VMware Vəngilti
instacart Walmart Qlobal texnologiyaBaxılıb 21

Problem bəyanat

Sim Sıxılma LeetCode Həlli – Bir sıra simvollar nəzərə alınmaqla chars, aşağıdakı alqoritmdən istifadə edərək onu sıxın:

Boş bir sətirlə başlayın s. Hər qrup üçün ardıcıl təkrarlanan personajlar in chars:

  • Qrupun uzunluğu olarsa 1, simvol əlavə edin s.
  • Əks halda, simvolun ardınca qrupun uzunluğunu əlavə edin.

The sıxılmış sim s ayrıca geri qaytarılmamalıdır, lakin bunun əvəzinə saxlanıla bilər giriş simvol massivində chars. Qeyd edək ki, qrup uzunluqlarıdır 10 və ya daha uzun bir neçə simvola bölünəcək chars.

Bitirdikdən sonra giriş massivinin dəyişdirilməsi, qayıtmaq massivin yeni uzunluğu.

Yalnız daimi əlavə yerdən istifadə edən bir alqoritm yazmalısınız.

misal

Test işi 1:

Input:

simvol = [“a”, “a”, “b”, “b”, “c”, “c”, “c”]

Çıxış:

6

Test işi 2:

Input:

simvol = [“a”, “b”, “b”, “b”, “b”, “b”, “b”, “b”, “b”, “b”, “b”, “b” , “b”]

Çıxış:

4

Izahat

i) Qruplar “aa”, “bb”, “ccc”dir. O, “a2b2c3”-ə sıxılır. Massiv əsasən [“a”, “2”, “b”, “2”, “c”, “3”] təşkil edir.

ii) Qruplar “a”, “bbbbbbbbbbbb”dir. O, “ab12”-yə sıxılır.

Yanaşma:

Beləliklə, burada alqo izah edəcəyəm. Əvvəlcə bir nümunə götürəcəyik "aabbccc“. buna görə də bu misalda əvvəlcə sətri və ya stringbuilderə a əlavə edəcəyik, sonra onun sayını 1 edəcəyik, çünki onlardan biri var indi for loopuna keçəcəyik. For döngəsində biz iki göstəricidən istifadə edirik: biri cari, digəri isə əvvəlki əvvəlki simvol əvvəlki simvolu, cari isə cari xarakteri indi aşağıdakı kimi saxlayır:

biz 1-dən təkrar edirik, çünki 1-ci simvol artıq sətir quruculuğundadır və indi təkrarlanır

1->əvvəlki = a , curr = a belə hesab 2 olacaq. s = a

2->prev = a , curr = b, buna görə də biz artmayacağıq, əksinə başqa hissəyə keçəcəyik, burada count>1 olub olmadığını yoxlayacağıq, sonra onu əlavə edəcəyik və simvolu da əlavə edəcəyik. və sayı 1-ə sıfırlayın. a2->a2b

3->əvvəlki=b, curr =b say = 2 s=a2b

4->əvvəlki= b , curr = c sayı = 2 belə ki, əvvəlki kimi başqa hissəyə gedəcək!=curr sayı > 2 belə ki, s= a2b2-> a2b2c sayı =1

5->əvvəlki = c ,curr = c sayı =2 s =a2b2c

6->əvvəlki = c , curr = c sayı =3 s =a2b2c

İndi burada iterasiya dayanacaq və sayımız hələ də qalacaq, ona görə də nəhayət, dövrə xaricində, >1sə, sətir a2b2c3 olarsa, biz saymanı əlavə edəcəyik.

Beləliklə, sətir sıxıldı, biz onu char massivinə köçürəcəyik. və uzunluğunu qaytarın.

Simli sıxılma kodu

Java Proqramı

class Solution {
    public int compress(char[] chars) {
        StringBuilder sb = new StringBuilder();
        int  n = chars.length;
        int count = 1;
        sb.append(chars[0]);
        for(int i=1;i<n;i++)
        {
           char curr = chars[i];
           char prev = chars[i-1];
           if(prev==curr)
           {
               count++;
           }
           if(prev!=curr)
           {   if(count>1)
               sb.append(count);
               sb.append(curr);
               count = 1;
           }
        }
        if(count>1)
        {
            sb.append(count);
        }
     
        for(int i=0;i<sb.length();i++)
        {
            chars[i]=sb.charAt(i);
        }
        return sb.length();
    }
}

C ++ Proqramı

class Solution {
public:
    int compress(vector<char>& chars) {
        int nw_idx = 0;     // Next write index
        int nr_idx = 1;     // Next read index
        int cnt = 1;        // Running counter
        char prev_char = chars[0];  // Running previous character
        chars.push_back('\0');      // To make the code shorter (no special handling of last char)
        
        // Code below is more or less self explanatory
        while(nr_idx != chars.size()) {
            if(chars[nr_idx] != prev_char) {
                chars[nw_idx++] = prev_char;
                if(cnt > 1) {
                    string cnt_str = to_string(cnt);
                    for(char c : cnt_str) chars[nw_idx++] = c;
                    cnt = 1;
                }
            } else {
                cnt++;
            }
            prev_char = chars[nr_idx++];
        }
        return nw_idx;
    }
};

Simli Sıxılma LeetCode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi olacaq 

Kosmik Mürəkkəblik olacaq

Referans: https://algodaily.com/lessons/using-the-two-pointer-technique

Translate »