ಅನುಕ್ರಮದಲ್ಲಿ ಸತತ ಒಂದೇ ಪದಗಳನ್ನು ಅಳಿಸಿ


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಫ್ಯಾಕ್ಟ್‌ಸೆಟ್
ಅರೇ ವಿಂಗಡಿಸಲಾಗುತ್ತಿದೆ ಸ್ಟಾಕ್ ಸ್ಟ್ರಿಂಗ್

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

“ಅನುಕ್ರಮದಲ್ಲಿ ಒಂದೇ ಪದಗಳನ್ನು ಅಳಿಸಿ” ಎಂಬ ಸಮಸ್ಯೆ ನಿಮಗೆ ನೀಡಲಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ ಪಟ್ಟಿ ನ ಎನ್ ತಂತಿಗಳು. ಒಂದೇ ರೀತಿಯ ಎರಡು ಪದಗಳು ಸತತವಾಗಿ ಇದ್ದರೆ, ಎರಡನ್ನೂ ಅಳಿಸಿ. ಅಂತಹ ಎಲ್ಲಾ ಜೋಡಿಗಳನ್ನು ಅಳಿಸಿದ ನಂತರ ಪಟ್ಟಿಯಲ್ಲಿ ಉಳಿದಿರುವ ಒಟ್ಟು ಪದಗಳು / ತಂತಿಗಳ ಸಂಖ್ಯೆಯನ್ನು ಮುದ್ರಿಸಿ.

ಅನುಕ್ರಮದಲ್ಲಿ ಸತತ ಒಂದೇ ಪದಗಳನ್ನು ಅಳಿಸಿ

ಉದಾಹರಣೆ

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 ಎಂಬುದು ಪಟ್ಟಿಯಲ್ಲಿರುವ ತಂತಿಗಳ ಸಂಖ್ಯೆ. ನಾವು ತಂತಿಗಳ ಮೇಲೆ ಹಾದುಹೋಗಿರುವಂತೆ, ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ಸರಳವಾಗಿ 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

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್ ^ 2) ಇಲ್ಲಿ n ಎಂಬುದು ಪಟ್ಟಿಯಲ್ಲಿರುವ ತಂತಿಗಳ ಸಂಖ್ಯೆ. ನಾವು ವೆಕ್ಟರ್‌ನಿಂದ ತಂತಿಗಳನ್ನು ತೆಗೆದುಹಾಕುತ್ತಿದ್ದೇವೆ. ವೆಕ್ಟರ್‌ನಿಂದ ಯಾವುದೇ ಅಂಶವನ್ನು ತೆಗೆಯುವುದು ರೇಖೀಯ ಸಮಯ ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ. ಏಕೆಂದರೆ ಈ ಕಾರ್ಯಾಚರಣೆಯನ್ನು N ಬಾರಿ ಮಾಡಬಹುದು. ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ಬಹುಪದೀಯವಾಗಿದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (1) ಏಕೆಂದರೆ ಮಾಹಿತಿಯನ್ನು ಸಂಗ್ರಹಿಸಲು ನಾವು ಯಾವುದೇ ಮಧ್ಯಂತರ ದತ್ತಾಂಶ ರಚನೆಯನ್ನು ಬಳಸಿಲ್ಲ. ತಂತಿಗಳನ್ನು ಸಂಗ್ರಹಿಸಲು ಮಾತ್ರ ಸ್ಥಳಾವಕಾಶ ಬೇಕಾಗಿತ್ತು, ಇದು ಇನ್ಪುಟ್ನ ಭಾಗವಾಗಿದೆ ಮತ್ತು ಅಲ್ಗಾರಿದಮ್ಗಾಗಿ ಸ್ಥಳ ಸಂಕೀರ್ಣತೆಯನ್ನು ಲೆಕ್ಕಹಾಕುವಲ್ಲಿ ಪರಿಗಣಿಸಲಾಗುವುದಿಲ್ಲ. ಆದರೆ ಒಟ್ಟಾರೆಯಾಗಿ ಪ್ರೋಗ್ರಾಂ ಇನ್ನೂ ಒ (ಎನ್) ಜಾಗವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ.