თანმიმდევრობით წაშალეთ ერთი და იგივე სიტყვები


Რთული ტური საშუალო
ხშირად ეკითხებიან ფაქტები
Array დახარისხება დასტის სიმებიანი

პრობლემის განცხადება

პრობლემა "თანმიმდევრობით წაშალეთ იგივე სიტყვები" აცხადებს, რომ თქვენ გეძლევათ ა სიასიმები. თუ თანმიმდევრულად ორი იგივე სიტყვაა, წაშალეთ ორივე. ყველა ასეთი წყვილის წაშლის შემდეგ ამობეჭდეთ სიაში დარჩენილი სიტყვების / სტრიქონების საერთო რაოდენობა.

თანმიმდევრობით წაშალეთ ერთი და იგივე სიტყვები

მაგალითი

s[ ] = {ab, aa, aa, bcd, ab}
3
s[ ] = {cpp, cpp, java}
1

სტეკის გამოყენება

ალგორითმი

  1. ინიცირება სია n სიმები.
  2. შექმნა დასტის მონაცემთა სტრუქტურა.
  3. გადაკვეთა სიიდან 0 – მდე ზომა - 1.
    1. შეამოწმეთ ცალი ცარიელია, ანუ სტეკის ზომა არის 0
      1. დააჭირეთ / ჩასვით სიტყვა მიმდინარე ინდექსში დასტის სიაში.
    2. სხვა შექმენით სიმების ცვლადი და შეინახეთ მასში სტეკის ზედა სტრიქონი.
      1. სიმების ცვლადი შეადარე სიაში მიმდინარე ინდექსში მოცემულ სიტყვას, თუ ორივე სტრიქონი ერთნაირია.
        1. ამოიღეთ სტრიქონი დასტის ზემოდან.
      2. სხვა თუ სიმები განსხვავებულია.
        1. სტრიქონი მიმდინარე ინდექსზე დააჭირეთ დასტისკენ.
  4. დააბრუნე დასტის ზომა.

კოდი

C ++ პროგრამა თანმიმდევრობით თანმიმდევრული იგივე სიტყვების წასაშლელად

#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

Java პროგრამა თანმიმდევრობით წაშლის ზედიზედ იმავე სიტყვებს

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

სირთულის ანალიზი

დროის სირთულე

O (n) სადაც n სიაშია სტრიქონების რაოდენობა. როგორც ჩვენ სტრიქონებზე გადავიარეთ, დროის სირთულე არის უბრალოდ O (n), რაც ალგორითმს წრფივ დროში აწარმოებს. მაგრამ ერთი რამ უნდა აღინიშნოს, რომ სტრიქონების შედარება ხდება და ჩვენ ჩავთვალეთ, რომ სტრიქონებს აქვთ გარკვეული მუდმივი სიგრძე, რომელიც ნაკლებია ვიდრე N. რადგან სიმების შედარება უარეს შემთხვევაში იღებს O (სიგრძის) დროს.

სივრცის სირთულე

O (n) რადგან ჩვენ გამოვიყენეთ სივრცე n სიმების შესანახად. n როდესაც სტრიქონი მიმდინარე ინდექსში და სტრიქონის თავზე არ არის ერთი და იგივე. ჩვენ სტრიქონს ვაძლევთ მიმდინარე ინდექსში დასტისკენ. უარეს შემთხვევაში, ჩვენ შეიძლება დასრულდეს ყველა სტრიქონის დასტისკენ. ეს სცენარი იწვევს O (n) სივრცის სირთულეს.

დასტის გამოყენების გარეშე

ალგორითმი

  1. ინიცირება სია n სიმები.
  2. გადაკვეთა სიიდან 0 – მდე ზომა - 2.
    1. შეადარეთ სიას მიმდინარე ინდექსში მოცემული სიტყვა სიაში მიმდინარე ინდექსში მოცემულ სიტყვასთან.
      1. თუ ორივე სიმები განსხვავებულია.
        1. მიმდინარე ინდექსის გაზრდა
      2. სხვა თუ ორივე სტრიქონი ერთნაირია.
        1. ორივე სტრიქონი ამოიღეთ / წაშალეთ სიიდან.
        2. შეამოწმეთ არის თუ არა მიმდინარე ინდექსი 0-ზე მეტი
          1. მიმდინარე ინდექსის შემცირება.
        3. განაახლეთ სიის ზომა, როგორც სიის ზომა - 2.
  3. დააბრუნე სიის ზომა.

კოდი

C ++ პროგრამა თანმიმდევრობით თანმიმდევრული იგივე სიტყვების წასაშლელად

#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

Java პროგრამა თანმიმდევრობით წაშლის ზედიზედ იმავე სიტყვებს

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

სირთულის ანალიზი

დროის სირთულე

O (n ^ 2) სადაც n სიაშია სტრიქონების რაოდენობა. მას შემდეგ, რაც ჩვენ ვექტორს სტრიქონებს ვხსნით. ვექტორიდან ნებისმიერი ელემენტის ამოღებას წრფივი დრო სჭირდება. რადგან ეს ოპერაცია შეიძლება შესრულდეს N ჯერ. დროის სირთულე მრავალწევრია.

სივრცის სირთულე

O (1) რადგან ინფორმაციის შესანახად არ გამოვიყენეთ რაიმე შუალედური მონაცემთა სტრუქტურა. სტრიქონების შესანახად საჭიროა მხოლოდ სივრცე, რომელიც შეყვანის ნაწილია და არ განიხილება ალგორითმის სივრცის სირთულის გამოთვლისას. მაგრამ პროგრამა მთლიანობაში მაინც იღებს O (N) ადგილს.