Rimozione carattere duplicato gamma

Question

Durante la lettura di un libro chiamato Cracking the coding interview da Gayle Laakmann, mi sono imbattuto in questa domanda

Progettare un algoritmo e scrivere il codice per rimuovere i caratteri duplicati in una stringa senza utilizzare alcun buffer aggiuntivo. NOTA: una o due variabili aggiuntive vanno bene. Una copia extra dell'array non lo è.

e questo codice: -

public static void removeDuplicates(char[] str) { 
     if (str == null) { 
      return; 
     } 
     int len = str.length; 
     if (len < 2) { 
      return; 
     } 

     int tail = 1; 

     for (int i = 1; i < len; ++i) { 
      int j; 
      for (j = 0; j < tail; ++j) { 
       if (str[i] == str[j]) { 
        break; 
       } 
      } 
      if (j == tail) { 
       str[tail] = str[i]; 
       ++tail; 
      } 
     } 
     str[tail] = 0; 
    } 

che si suppone per rimuovere carattere duplicato dalla matrice. Non sto tranquillo, sembra capire cosa sta facendo l'algoritmo sostituendo lo stesso personaggio ancora e ancora. Ho pensato che sono solo io a sentire che l'algoritmo non funziona, ma infatti quando ho eseguito questo codice mi stanno dando delle uscite sbagliate. Questo grave errore è nel libro o non ho capito la domanda?

Answer 1

Algo sembra funzionare, ma non di compensazione caratteri rimanenti. codice modificato a seguire e funziona: Nota: Sostituito:

str[tail] = 0; 

con:

for(; tail < len;tail++){ 
     str[tail] = 0; 
    } 

---

public static void removeDuplicates(char[] str) { 
     if (str == null) { 
      return; 
     } 
     int len = str.length; 
     if (len < 2) { 
      return; 
     } 

     int tail = 1; 

     for (int i = 1; i < len; ++i) { 
      int j; 
      for (j = 0; j < tail; ++j) { 
       if (str[i] == str[j]) { 
        break; 
       } 
      } 

      if (j == tail) { 
       str[tail] = str[i]; 
       ++tail; 
      } 

     } 
     for(; tail < len;tail++){ 
      str[tail] = 0; 
     } 

    } 

Answer 2

In array Java sono di dimensione fissa. Quindi la funzione chiamata non può cambiare la dimensione della matrice di input se trova duplicati. La tua funzione sta semplicemente facendo l'indice di inizio del sub-array che ha duplicato a 0. Così, quando si stampa il contenuto dell'array nella funzione di chiamata l'elemento che è stato fatto 0 non viene stampato, ma gli elementi seguenti (se presente) non vengono stampati.

La risposta di YoK rende tutti gli elementi della matrice secondaria duplicati a 0. In modo che quando si stampa nella funzione chiamante i duplicati non vengano stampati. Ma è necessario ricordare che la dimensione della matrice è ancora invariata.

In alternativa è possibile restituire la dimensione della matrice secondaria con caratteri univoci. Che nel tuo caso è tail.

più Un'alternativa è passare l'input come una StringBuffer e apportare le modifiche sul posto come:

public static void removeDuplicates(StringBuffer str) {       

     int len = str.length(); 

     // if the string as less than 2 char then it can't have duplicates. 
     if (len < 2) {       
       return; 
     } 

     // fist character will never be duplicate. 
     // tail is the index of the next unique character. 
     int tail = 1; 

     // iterate from 2nd character. 
     for (int i = 1; i < len; ++i) { 
       int j; 

       // is char at index i already in my list of uniq char? 
       for (j = 0; j < tail; ++j) { 
         if (str.charAt(i) == str.charAt(j)) { 
           break; 
         }  
       } 

       // if no then add it to my uniq char list. 
       if (j == tail) {      
         str.setCharAt(tail, str.charAt(i)); 

         // increment tail as we just added a new ele. 
         ++tail; 
       } 
     } 
     // at this point the characters from index [0,tail) are unique 
     // if there were any duplicates they are between [tail,input.length) 
     // so truncate the length of input to tail. 
     str.setLength(tail); 
} 

Ideone Link

Answer 3

Una soluzione con un vettore di bit.

Tempo: O (n), dove n = length of the string

Spazio: O (1)

void removeduplicatas(char str[]){ 
    int i, checker = 0, bitvalue = 0, value = 0, tail = 0; 
    i = 0; 
    tail = 0; 
    while(str[i]){ 
     value = str[i] - 'a'; 
     bitvalue = 1 << value; 
     if((checker & bitvalue) == 0){ 
      str[tail++] = str[i]; 
      checker |= bitvalue; 
     } 
     i++; 
    } 
    str[tail] = '\0'; 
} 

Answer 4

Questa è una soluzione utilizzando C++ e ricorsione per ciclicamente ogni carattere della stringa e impiegando il suddetto metodo di bitstring in un char larghezza fissa. È necessario assicurarsi che la stringa wide fissa sia più lunga dei caratteri k necessari per controllare.

#include <cstdint> 
#include <iostream> 

bool CheckUniqueChars(char *string, uint32_t index, uint32_t checker){ 

char character = string[index]; 

if(character=='\0'){ 
    return true; 
}else{ 
    int value = character - 'a'; 

    if((checker&(1<<value))>0){ 
     return false; 
    }else{ 
     checker |= (1<<value); 
     return CheckUniqueChars(string,++index,checker); 
    } 
    } 
} 


int main(int argc, char *argv[]){ 

    char *string = argv[1]; 
    uint32_t idx=0,checker=0; 

if(CheckUniqueChars(string,idx,checker)){ 
     std::cout << "all characters are unique" << std::endl; 
}else{ 
    std::cout << "there are duplicate characters" << std::endl; 
} 

return 0; 
} 

Answer 5

ho improvvisato codice in yŏk evitare di utilizzare

for(; tail < len;tail++){ 
     str[tail] = 0; 
} 

Invece possiamo impostare vuoto nel primo ciclo stesso.

public static void removeDuplicates(char[] str){ 
    if (str == null) { 
     return; 
    } 
    int len = str.length; 
    if (len < 2) { 
     return; 
    } 

    int tail = 1; 

    for(int i=1;i<len;++i){ 
     int j; 
     for(j=0;j<tail;++j){ 
      if(str[i] == str[j]) break; 
     } 
     if(j==tail){ 
      str[tail] = str[i]; 
      if(i!=tail)str[i]=0; 
      ++tail; 
     }else{ 
      str[i]=0; 
     } 

    } 
}