ஒரு வரிசையில் தொடர்ச்சியான அதே சொற்களை நீக்கு


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது உண்மை
அணி வரிசையாக்க ஸ்டேக் சரம்

சிக்கல் அறிக்கை

“தொடர்ச்சியான ஒரே சொற்களை ஒரு வரிசையில் நீக்கு” ​​என்ற சிக்கல் உங்களுக்கு வழங்கப்படுகிறது என்று கூறுகிறது பட்டியலில் of n சரங்களை. ஒரே மாதிரியான இரண்டு சொற்கள் தொடர்ச்சியாக இருந்தால், இரண்டையும் நீக்கவும். அத்தகைய அனைத்து ஜோடிகளையும் நீக்கிய பிறகு பட்டியலில் மீதமுள்ள சொற்கள் / சரங்களின் எண்ணிக்கையை அச்சிடுக.

ஒரு வரிசையில் தொடர்ச்சியான அதே சொற்களை நீக்கு

உதாரணமாக

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. அடுக்கின் அளவைத் திரும்புக.

குறியீடு

ஒரு வரிசையில் தொடர்ச்சியான அதே சொற்களை நீக்க சி ++ நிரல்

#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

தொடர்ச்சியான ஒரே சொற்களை ஒரு வரிசையில் நீக்க ஜாவா நிரல்

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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (n) n என்பது பட்டியலில் உள்ள சரங்களின் எண்ணிக்கை. நாம் இப்போது சரங்களை கடந்து சென்றதால், நேர சிக்கலானது வெறுமனே O (n) ஆகும், இது வழிமுறையை நேரியல் நேரத்தில் இயக்க வைக்கிறது. ஆனால் கவனிக்க வேண்டிய ஒரு விஷயம் என்னவென்றால், சரங்களை ஒப்பிட்டுப் பார்க்கிறோம், மேலும் சரங்களுக்கு சில நிலையான நீளம் N ஐ விடக் குறைவாக இருப்பதைக் கருத்தில் கொண்டுள்ளோம். ஏனெனில் மோசமான நிலையில் சரம் ஒப்பீடு O (நீளம்) நேரம் எடுக்கும்.

விண்வெளி சிக்கலானது

ஓ (n) ஏனென்றால் n சரங்களை சேமிக்க நாங்கள் இடத்தைப் பயன்படுத்தினோம். தற்போதைய குறியீட்டில் உள்ள சரம் மற்றும் அடுக்கின் மேலே உள்ள சரம் ஒரே மாதிரியாக இருக்காது. தற்போதைய குறியீட்டில் உள்ள சரத்தை அடுக்கில் தள்ளுகிறோம். மோசமான நிலையில், எல்லா சரங்களையும் அடுக்கிற்குள் தள்ளுவோம். இந்த காட்சி O (n) விண்வெளி சிக்கலில் விளைகிறது.

அடுக்கைப் பயன்படுத்தாமல்

அல்காரிதம்

  1. ஒரு பட்டியலைத் தொடங்கவும் n சரங்கள்.
  2. பட்டியலின் 0 முதல் அளவு வரை பயணிக்கவும் - 2.
    1. பட்டியலில் உள்ள தற்போதைய குறியீட்டில் உள்ள வார்த்தையை பட்டியலில் உள்ள தற்போதைய குறியீட்டு + 1 இல் உள்ள வார்த்தையுடன் ஒப்பிடுக.
      1. இரண்டு சரங்களும் வேறுபட்டால்.
        1. தற்போதைய குறியீட்டை அதிகரிக்கவும்
      2. இரண்டு சரங்களும் ஒரே மாதிரியாக இருந்தால் வேறு.
        1. பட்டியலிலிருந்து இரண்டு சரங்களையும் அகற்று / அழிக்கவும்.
        2. தற்போதைய குறியீடு 0 ஐ விட அதிகமாக இருக்கிறதா என்று சோதிக்கவும்
          1. தற்போதைய குறியீட்டைக் குறைக்கவும்.
        3. பட்டியலின் அளவை பட்டியலின் அளவாக புதுப்பிக்கவும் - 2.
  3. பட்டியலின் அளவைத் தரவும்.

குறியீடு

ஒரு வரிசையில் தொடர்ச்சியான அதே சொற்களை நீக்க சி ++ நிரல்

#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

தொடர்ச்சியான ஒரே சொற்களை ஒரு வரிசையில் நீக்க ஜாவா நிரல்

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 முறை செய்ய முடியும். நேர சிக்கலானது பல்லுறுப்புக்கோவை.

விண்வெளி சிக்கலானது

ஓ (1) ஏனெனில் தகவல்களைச் சேமிக்க எந்த இடைநிலை தரவு கட்டமைப்பையும் நாங்கள் பயன்படுத்தவில்லை. சரங்களை சேமிக்க ஒரே இடம் தேவைப்பட்டது, இது உள்ளீட்டின் ஒரு பகுதியாகும் மற்றும் வழிமுறைக்கான இட சிக்கலைக் கணக்கிடுவதில் கருதப்படாது. ஆனால் ஒட்டுமொத்தமாக நிரல் இன்னும் ஓ (என்) இடத்தை எடுக்கும்.