Διαγραφή διαδοχικών ίδιων λέξεων σε μια σειρά


Επίπεδο δυσκολίας Μέσον
Συχνές ερωτήσεις Γεγονότα
Παράταξη Ταξινόμηση Στοίβα κορδόνι

Δήλωση προβλήματος

το πρόβλημα "Διαγραφή διαδοχικών ίδιων λέξεων σε μια σειρά" δηλώνει ότι σας δίνεται ένα λίστα του ν χορδές. Εάν υπάρχουν δύο ίδιες λέξεις που εμφανίζονται διαδοχικά, διαγράψτε και τις δύο. Εκτυπώστε τον συνολικό αριθμό λέξεων / συμβολοσειρών που απομένουν στη λίστα μετά τη διαγραφή όλων αυτών των ζευγών.

Διαγραφή διαδοχικών ίδιων λέξεων σε μια σειρά

Παράδειγμα

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), γεγονός που κάνει τον αλγόριθμο να τρέχει σε γραμμικό χρόνο. Αλλά ένα πράγμα που πρέπει να σημειωθεί είναι ότι οι χορδές συγκρίνονται και θεωρήσαμε ότι οι χορδές έχουν κάποιο σταθερό μήκος που είναι μικρότερο από το Ν. Επειδή η σύγκριση χορδών στη χειρότερη περίπτωση παίρνει χρόνο Ο (μήκος).

Διαστημική πολυπλοκότητα

O (n) γιατί χρησιμοποιήσαμε χώρο για την αποθήκευση n string.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

Πρόγραμμα 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 είναι ο αριθμός των συμβολοσειρών στη λίστα. Δεδομένου ότι αφαιρούμε χορδές από το διάνυσμα. Η αφαίρεση οποιουδήποτε στοιχείου από τον φορέα απαιτεί γραμμικό χρόνο. Επειδή αυτή η λειτουργία μπορεί να εκτελεστεί Ν φορές. Η πολυπλοκότητα του χρόνου είναι πολυώνυμη.

Διαστημική πολυπλοκότητα

Ο (1) επειδή δεν έχουμε χρησιμοποιήσει κάποια ενδιάμεση δομή δεδομένων για την αποθήκευση πληροφοριών. Απαιτήθηκε ο μόνος χώρος για την αποθήκευση συμβολοσειρών, η οποία αποτελεί μέρος της εισόδου και δεν θα ληφθεί υπόψη στον υπολογισμό της πολυπλοκότητας του χώρου για τον αλγόριθμο. Αλλά το πρόγραμμα στο σύνολό του εξακολουθεί να παίρνει χώρο O (N).