Bir ardıcıllıqla eyni sözləri silin

Problem bəyanat

problem "ardıcıllıqla eyni sözləri silin" sizə verildiyini bildirir siyahı n strings. Ardıcıl olaraq iki eyni söz varsa, ikisini də silin. Bütün bu cütlərin silinməsindən sonra siyahıda qalan sözlərin / sətirlərin ümumi sayını çap edin.

Pin

misal

s[ ] = {ab, aa, aa, bcd, ab}

3

s[ ] = {cpp, cpp, java}

1

Stack istifadə

Alqoritm

1. Siyahısını başladın n strings.
2. Bir yaradın qalaq məlumatların quruluşu.
3. Siyahının ölçüsündən 0-a qədər keçin - 1.
   1. Yığının boş olub olmadığını yoxlayın, yəni yığının ölçüsü 0-dır
      1. Yığındakı siyahıda sözü indiki indeksə daxil edin / daxil edin.
   2. Başqa bir simli dəyişən yaradın və simli içindəki yığının üst hissəsində saxlayın.
      1. Hər iki simli eyni olduqda, sətir dəyişənini siyahıda mövcud indeksdəki sözlə müqayisə edin.
         1. Simli yığının üst hissəsindən çıxarın.
      2. İplər fərqli olduqda başqa.
         1. Cari indeksdəki simli yığına itələyin.
4. Yığın ölçüsünü qaytarın.

Kodu

Ardıcıl eyni sözləri ardıcıllıqla silmək üçün C ++ proqramı

#include<bits/stdc++.h> 
using namespace std; 
  
int removeConsSame(vector<string > s){ 
    stack<string> st; 
  
    for(int i=0; i<s.size(); i++){ 
        if(st.empty()){ 
            st.push(s[i]);
        }
        
        else{ 
            string str = st.top(); 
  
            if(str.compare(s[i]) == 0){ 
                st.pop(); 
            }
  
            else{
                st.push(s[i]);
            }
        } 
    } 
  
    return st.size(); 
} 
  
int main(){ 
    vector<string> s = {"ab", "aa", "aa", "bcd", "ab"};
    
    cout << removeConsSame(s); 
    
    return 0; 
}

3

Ardıcıl eyni sözləri ardıcıllıqla silmək üçün Java Proqramı

import java.util.Vector; 
import java.util.Stack; 
  
class removeSame{ 
    
    static int removeConsSame(Vector <String > s){ 
        Stack<String> st = new Stack<>(); 
       
        for(int i=0; i<s.size(); i++){ 
            if(st.empty()){ 
                st.push(s.get(i));
            }
            
            else{ 
                String str = st.peek(); 
       
                if(str.equals(s.get(i))){     
                    st.pop(); 
                }
       
                else{
                    st.push(s.get(i));
                }
            } 
        } 
        return st.size(); 
    } 
      
    public static void main(String[] args){ 
        Vector<String> s = new Vector<>(); 
  
        s.addElement("ab"); 
        s.addElement("aa"); 
        s.addElement("aa");
        s.addElement("bcd");
        s.addElement("ab");
  
        System.out.println(removeConsSame(s)); 
    } 
}

3

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n) burada n - siyahıdakı simlərin sayı. Simlərin üstündən keçdiyimiz kimi, zamanın mürəkkəbliyi sadəcə O (n) -dir, bu da alqoritmin xətti vaxtda işləməsini təmin edir. Ancaq bir şeyə diqqət yetirmək lazımdır ki, simlər müqayisə olunur və biz simlərin N-dən az olan sabit bir uzunluğa sahib olduğunu düşündük, çünki ən pis vəziyyətdə simli müqayisə O (uzunluq) vaxtını alır.

Kosmik Mürəkkəblik

O (n) n sətir saxlamaq üçün yerdən istifadə etdik.n cari indeksdəki sətir və yığının üst hissəsindəki simli eyni olmadıqda. Hazırkı indeksdəki simi yığına itələyirik. Ən pis halda, bütün ipləri yığına basmaqla nəticələnə bilərik. Bu ssenari O (n) kosmik mürəkkəbliyi ilə nəticələnir.

Stack istifadə etmədən

Alqoritm

1. Siyahısını başladın n simlər.
2. Siyahının ölçüsündən 0-a qədər keçin - 2.
   1. Siyahıda mövcud indeksdəki sözlə siyahıda mövcud indeks + 1 sözü ilə müqayisə edin.
      1. Hər iki sim də fərqlidirsə.
         1. Cari indeksi artırın
      2. Hər ikisi də eyni olduqda başqa.
         1. Hər iki simli siyahıdan silin / silin.
         2. Cari indeksin 0-dan böyük olub olmadığını yoxlayın
            1. Mövcud indeksin azalması.
         3. Siyahının ölçüsünü siyahının ölçüsü kimi yeniləyin - 2.
3. Siyahının ölçüsünü qaytarın.

Kodu

Ardıcıl eyni sözləri ardıcıllıqla silmək üçün C ++ proqramı

#include<bits/stdc++.h> 
using namespace std; 
  
int removeConsSame(vector <string > s){ 
    int n = s.size(); 
  
    for(int i=0; i<n-1; ){ 
        if(s[i].compare(s[i+1]) == 0){ 
            s.erase(s.begin()+i); 
            s.erase(s.begin()+i); 
  
            if(i > 0){ 
                i--; 
            }
  
            n = n-2; 
        } 
  
        else{
            i++;
        }
    } 
    return s.size(); 
} 
  
int main(){ 
    vector<string> s = {"ab", "aa", "aa", "bcd", "ab"};
    
    cout << removeConsSame(s); 
    
    return 0; 
}

3

Ardıcıl eyni sözləri ardıcıllıqla silmək üçün Java Proqramı

import java.util.Vector; 
  
class removeSame{ 
    
    static int removeConsSame(Vector <String > s){ 
        int n = s.size(); 
       
        for(int i=0; i<n-1; ){ 
            if(s.get(i).equals(s.get(i+1))){ 
                s.remove(i); 
                s.remove(i); 
       
                if(i > 0){ 
                    i--; 
                }
       
                n = n-2; 
            } 
       
            else{
                i++;
            }
        } 
        return s.size(); 
    } 
      
    public static void main(String[] args){ 
        Vector<String> s = new Vector<>(); 
  
        s.addElement("ab"); 
        s.addElement("aa"); 
        s.addElement("aa");
        s.addElement("bcd");
        s.addElement("ab");
  
        System.out.println(removeConsSame(s)); 
    } 
}

3

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n ^ 2) burada n - siyahıdakı simlərin sayı. Vektordan simləri götürdüyümüz üçün. Vektordan istənilən elementin çıxarılması xətti vaxt aparır. Çünki bu əməliyyat N dəfə edilə bilər. Zamanın mürəkkəbliyi polinomdur.

Kosmik Mürəkkəblik

O (1) çünki məlumat saxlamaq üçün heç bir ara məlumat quruluşundan istifadə etməmişik. Girişin bir hissəsi olan və alqoritm üçün kosmik mürəkkəbliyin hesablanmasında nəzərə alınmayan simlərin saxlanması üçün yeganə yer tələb olunurdu. Ancaq proqram bütövlükdə O (N) yer tutur.