අනුපිළිවෙලින් එකම වචන මකන්න


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ෆැක්ට්සෙට්
අරා වර්ග කිරීම අඩුක්කුව String

ගැටළු ප්රකාශය

“අනුපිළිවෙලින් එකම වචන මකන්න” යන ගැටලුවේ සඳහන් වන්නේ ඔබට ලබා දී ඇති බවයි ලැයිස්තුව 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. තොගයේ ප්‍රමාණය නැවත ලබා දෙන්න.

කේතය

අනුපිළිවෙලින් එකම වචන මකා දැමීමට 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

අනුපිළිවෙලින් එකම වචන මකා දැමීමට ජාවා වැඩසටහන

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 ට වඩා අඩු නියත දිගක් ඇති බව අපි සලකා බැලුවෙමු.

අභ්‍යවකාශ සංකීර්ණතාව

සාමාන්ය (n) මක්නිසාද යත් අපි නූල් ගබඩා කිරීම සඳහා අවකාශය භාවිතා කළ බැවිනි. වත්මන් දර්ශකයේ ඇති නූල සහ තොගයේ ඉහළින් ඇති නූල් සමාන නොවන විට. අපි වත්මන් දර්ශකයේ ඇති නූල තොගයට තල්ලු කරමු. නරකම අවස්ථාවෙහිදී, අපි සියලු නූල් තොගයට තල්ලු කිරීම අවසන් කළ හැකිය. මෙම තත්වය O (n) අවකාශයේ සංකීර්ණතාවයට හේතු වේ.

තොග භාවිතා නොකර

ඇල්ගොරිතම

  1. ලැයිස්තුවක් ආරම්භ කරන්න n නූල්.
  2. ලැයිස්තුවේ 0 සිට ප්‍රමාණය දක්වා ගමන් කරන්න - 2.
    1. ලැයිස්තුවේ වත්මන් දර්ශකයේ ඇති වචනය ලැයිස්තුවේ වත්මන් දර්ශකය + 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

අනුපිළිවෙලින් එකම වචන මකා දැමීමට ජාවා වැඩසටහන

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) තොරතුරු ගබඩා කිරීම සඳහා අප අතරමැදි දත්ත ව්‍යුහයක් භාවිතා කර නැති නිසා. නූල් ගබඩා කිරීම සඳහා එකම අවකාශය අවශ්‍ය වූ අතර එය ආදානයේ කොටසක් වන අතර ඇල්ගොරිතම සඳහා අවකාශ සංකීර්ණතාව ගණනය කිරීමේදී සලකා බලනු නොලැබේ. නමුත් සමස්තයක් ලෙස වැඩසටහන තවමත් O (N) අවකාශය ගනී.