ဆက်တိုက်တူညီသောစကားလုံးများကိုအစီအစဉ်တကျတည်းဖျက်ပါ


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် အချက်အလက်
အခင်းအကျင်း sorting စုပုံထား ကြိုး

ပြProbleနာဖော်ပြချက်

ပြconseနာ "အဆက်မပြတ်တူညီစကားလုံးများကိုတစ်ဆက်တည်းဖြင့်ဖျက်ပါ" ဟုသင်ကပေးထားသည်ဟုဆိုသည် စာရင်း of n ညှို့။ တူညီသောစကားလုံးနှစ်လုံးဆက်တိုက်ပါ ၀ င်ပါက၎င်းနှစ်ခုလုံးကိုဖျက်ပစ်ပါ။ ထိုကဲ့သို့သောအားလုံးအတွက်ဖျက်ခြင်းပြီးနောက်စာရင်း၌ကျန်ရှိနေသောစကားလုံးများ / ညှို့များ၏စုစုပေါင်းအရေအတွက်ကိုပုံနှိပ်ပါ။

ဆက်တိုက်တူညီသောစကားလုံးများကိုအစီအစဉ်တကျတည်းဖျက်ပါ

နမူနာ

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

အသုံးပြုခြင်း

algorithm

  1. စာရင်းတစ်ခုကိုအစပြုပါ n ညှို့.
  2. တစ်ဦး Create စုပုံထား ဒေတာဖွဲ့စည်းပုံ။
  3. 0 မှစာရင်း၏အရွယ်အစားမှလမ်းကြောင်း - 1 ။
    1. ဆိုလိုသည်မှာ stack ၏အရွယ်အစားမှာ 0 ဖြစ်သည်
      1. စာလုံးကို stack ထဲရှိစာရင်းရှိလက်ရှိညွှန်းကိန်းတွင်တွန်း / ထည့်ပါ။
    2. အခြားတစ်ခုအနေဖြင့် string variable တစ်ခုကိုဖန်တီးပြီး၎င်းကို stack ၏ထိပ်တွင်သိမ်းထားပါ။
      1. string variable ကို list ရှိ current index ရှိစကားလုံးနှင့်နှိုင်းယှဉ်ပါ။
        1. stack ၏ထိပ်ကနေ string ကိုဖယ်ရှားပါ။
      2. ကြိုးများကွဲပြားခြားနားလျှင်။
        1. လက်ရှိအညွှန်းကိန်းရှိ string ကို stack သို့တွန်းပါ။
  4. stack ၏အရွယ်အစားကိုပြန်ပို့ပါ။

ကုဒ်

တပြိုင်နက်တည်းစကားလုံးများကိုအဆက်မပြတ်ဖျက်ပစ်ရန် 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

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (ဎ) ဘယ်မှာ n သည်စာရင်းထဲတွင်ညှို့များ၏နံပါတ်ဖြစ်ပါတယ်။ ကျွန်ုပ်တို့သည် Strings များကိုသာဖြတ်သန်းသွားသောအခါအချိန်ရှုပ်ထွေးမှုသည်ရိုးရိုး O (n) ဖြစ်ပြီး၎င်းကို algorithm ကို linear time တွင်လည်ပတ်စေသည်။ သို့သော်သတိပြုရမည့်အချက်တစ်ခုမှာ Strings များကိုနှိုင်းယှဉ်ခြင်းနှင့် Strings များသည်အချို့သောစဉ်ဆက်မပြတ်အရှည်ရှိသည်ဟုစဉ်းစားပြီးအဆိုးဆုံးကိစ္စများတွင် string ကိုနှိုင်းယှဉ်ခြင်းသည် O (length) အချိန်ယူသောကြောင့်ဖြစ်သည်။

အာကာသရှုပ်ထွေးမှု

အို (ဎ) ဘာဖြစ်လို့လဲဆိုတော့ n strings.n ကိုသိမ်းဖို့ space ကိုသုံးလိုက်တာနဲ့ current index မှာ string နဲ့ stack ရဲ့ထိပ်မှာရှိတဲ့ string ကအတူတူမဟုတ်ဘူး။ ကျနော်တို့လက်ရှိအညွှန်းကိန်းမှာ string ကို stack သို့တွန်းအားပေး။ အဆိုးဆုံးအနေနှင့်ကျွန်ုပ်တို့သည်ကြိုးများအားလုံးကို stack ထဲသို့တွန်းပို့နေလိမ့်မည်။ ဤအခြေအနေသည်အို ()) အာကာသရှုပ်ထွေးမှုကိုဖြစ်ပေါ်စေသည်။

အသုံးမပြုဘဲ Stack

algorithm

  1. စာရင်းတစ်ခုကိုအစပြုပါ n ကြိုးများ။
  2. 0 မှစာရင်း၏အရွယ်အစားမှလမ်းကြောင်း - 2 ။
    1. စာရင်းရှိလက်ရှိအညွှန်းကိန်းရှိစကားလုံးနှင့်စာရင်းရှိလက်ရှိအညွှန်းကိန်း + ၁ နှင့်နှိုင်းယှဉ်ပါ။
      1. နှစ် ဦး စလုံးညှို့ကွဲပြားခြားနားလျှင်။
        1. လက်ရှိအညွှန်းကိန်းတိုးပါ
      2. ကျန်တဲ့နှစ်ခုလုံးကကြိုးအတူတူပါ။
        1. စာရင်းမှညှို့နှစ်ခုလုံးကိုဖယ်ရှား / ဖျက်ပစ်ပါ။
        2. လက်ရှိအညွှန်းကိန်း 0 ထက်ကြီးမြတ်လျှင်စစ်ဆေးပါ
          1. လက်ရှိအညွှန်းကိန်းကိုလျှော့ချပါ။
        3. စာရင်း၏အရွယ်အစားအဖြစ်စာရင်း၏အရွယ်အစားကို update - 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

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (n ^ ၂) ဘယ်မှာ n သည်စာရင်းထဲတွင်ညှို့များ၏နံပါတ်ဖြစ်ပါတယ်။ ကျနော်တို့က vector ကနေညှို့ဖယ်ရှားပစ်နေကြသည်ကတည်းက။ vector မှမည်သည့်ဒြပ်စင်ကိုမဆိုဖယ်ထုတ်ခြင်းက linear အချိန်ဖြစ်သည်။ ဒီစစ်ဆင်ရေးကို N ကြိမ်ဖျော်ဖြေနိုင်သောကြောင့်။ အချိန်ရှုပ်ထွေး polynomial ဖြစ်ပါတယ်။

အာကာသရှုပ်ထွေးမှု

အို (၁) ဘာလို့လဲဆိုတော့ကျွန်တော်တို့ဟာသတင်းအချက်အလက်တွေကိုသိမ်းဆည်းဖို့အလယ်အလတ်ရှိတဲ့ဒေတာဖွဲ့စည်းပုံကိုအသုံးမပြုခဲ့လို့ပဲ။ string များကိုသိုလှောင်ရန်အတွက်တစ်ခုတည်းသောနေရာလိုအပ်သည်။ ၎င်းသည် input ၏အစိတ်အပိုင်းတစ်ခုဖြစ်ပြီး algorithm အတွက် space ရှုပ်ထွေးမှုကိုတွက်ချက်ရာတွင်ထည့်သွင်းစဉ်းစားလိမ့်မည်မဟုတ်ပါ။ သို့သော်အစီအစဉ်တစ်ခုလုံးအနေဖြင့်အို (N) နေရာယူထားသည်။