Decodifica della lunghezza della corsa sul posto?

Question

Data una stringa con lunghezza di esecuzione codificata, ad esempio "A3B1C2D1E1", decodificare la stringa sul posto. La risposta per la stringa codificata è "AAABCCDE". Supponiamo che l'array codificato sia abbastanza grande da contenere la stringa decodificata, cioè si può presumere che la dimensione dell'array = MAX [length (encodedstirng), length (decodedstring)].

Questo non sembra banale, poiché la semplice decodifica A3 come 'AAA' porterà alla sovrascrittura 'B' della stringa originale.

Inoltre, non si può presumere che la stringa decodificata sia sempre più grande della stringa codificata. Es .: Stringa codificata - 'A1B1', la stringa decodificata è 'AB'. qualche idea?

E sarà sempre un paio lettera cifre, vale a dire non sarà chiesto di convertire 0515-0000055555

Answer 1

Se non lo sappiamo già, dovremmo esaminare prima, sommando le cifre, per calcolare la lunghezza della stringa decodificata.

Sarà sempre una coppia di lettere, quindi è possibile eliminare lo 1 dalla stringa senza alcuna confusione.

A3B1C2D1E1 

diventa

A3BC2DE 

Ecco del codice, in C++, per rimuovere le 1 s dalla stringa (O (n) complessità).

// remove 1s 
int i = 0; // read from here 
int j = 0; // write to here 
while(i < str.length) { 
    assert(j <= i); // optional check 
    if(str[i] != '1') { 
     str[j] = str[i]; 
     ++ j; 
    } 
    ++ i; 
} 
str.resize(j); // to discard the extra space now that we've got our shorter string 

Ora, questa stringa è garantito essere inferiore, oppure la stessa lunghezza, la stringa decodificata finale. Non possiamo fare questa affermazione sulla stringa originale, ma possiamo farcela con questa stringa modificata.

(Un passaggio facoltativo, banale, ora è quello di sostituire ogni 2 con la lettera precedente. A3BCCDE, ma non è necessario farlo).

Ora possiamo iniziare a lavorare dalla fine. Abbiamo già calcolato la lunghezza della stringa decodificata e quindi sappiamo esattamente dove sarà il carattere finale. Possiamo semplicemente copiare i caratteri dalla fine della nostra stringa breve alla loro posizione finale.

Durante questo processo di copia da destra a sinistra, se troviamo una cifra, dobbiamo fare più copie della lettera che si trova a sinistra della cifra. Potresti essere preoccupato che questo potrebbe rischiare di sovrascrivere troppi dati. Ma abbiamo dimostrato in precedenza che la nostra stringa codificata, o qualsiasi sua sottostringa, non sarà mai più lunga della sua stringa decodificata corrispondente; questo significa che ci sarà sempre abbastanza spazio.

Answer 2

Questa è una domanda molto vaga, anche se non è particolarmente difficile se si pensa a questo proposito. Come dici tu, decodificare A3 come AAA e semplicemente scriverlo sul posto sovrascriverà i caratteri B e 1, quindi perché non spostare solo quelli più distanti lungo l'array prima?

Ad esempio, una volta letto A3, si sa che è necessario creare spazio per un carattere in più, se fosse A4 ne sarebbero necessari due e così via. Per raggiungere questo obiettivo, troverai la fine della stringa nell'array (fai questo in anticipo e memorizzalo come indice).

Poi ciclo, però, spostando i personaggi ai loro nuovi slot:

Per iniziare: A|3|B|1|C|2||||||| avere una variabile denominata end memorizzare l'indice 5, vale a dire l'ultimo, non vuota, la voce.

avessi letto nella prima coppia, usando una variabile chiamata cursor per memorizzare la posizione corrente - quindi dopo aver letto nel A e 3 sarebbe impostato a 1 (slot con il 3).

Pseudocodice per il trasloco:

var n = array [cursore] - 2; // n = 1, il 3 di A3 e quindi meno 2 per consentire la coppia.

per (i = fine; i> cursor; i ++) { array [i + n] = array [i]; }

Questo lascerebbe con:

A|3|A|3|B|1|C|2|||||

Ora il A c'è già una volta, quindi ora si vuole scrivere n + 1A 's a partire dall'indice memorizzato in cursor:

for(i = cursor; i < cursor + n + 1; i++) 
{ 
    array[i] = array[cursor - 1]; 
} 

// increment the cursor afterwards! 
cursor += n + 1; 

Dando:

A|A|A|A|B|1|C|2|||||

Quindi stai indicando l'inizio della prossima coppia di valori, pronto per andare di nuovo. Mi rendo conto che ci sono alcuni buchi in questa risposta, anche se questo è intenzionale in quanto è una domanda di intervista!Ad esempio, nei casi limite specificati A1B1, è necessario un ciclo diverso per spostare i caratteri successivi all'indietro anziché in avanti.

Answer 3

Segue un'altra soluzione O (n^2).

Dato che non c'è alcun limite alla complessità della risposta, questa semplice soluzione sembra funzionare perfettamente.

while (there is an expandable element): 
    expand that element 
    adjust (shift) all of the elements on the right side of the expanded element 

Dove:

• dimensione spazio libero è il numero di elementi vuoti lasciati nella matrice.

• Un elemento espandibile è un elemento che:

  expanded size - encoded size <= free space size 
  

Il punto è che nel processo di raggiungimento dal codice run-length alla stringa espansa, ad ogni passo, v'è Almeno un elemento che può essere espanso (facile da dimostrare).

Answer 4

La seguente soluzione è O(n) e sul posto. L'algoritmo non dovrebbe accedere alla memoria che non dovrebbe, sia letto che scritto. Ho fatto un po 'di debug, e sembra corretto ai test di esempio che ho alimentato.

---

panoramica Alto livello:

• determinare la lunghezza codificato.
• Determinare la lunghezza decodificata leggendo tutti i numeri e sommandoli.
• La fine del buffer è MAX (lunghezza decodificata, lunghezza codificata).
• Decodifica la stringa partendo dalla fine della stringa. Scrivi dalla fine del buffer.
• Poiché la lunghezza decodificata potrebbe essere maggiore della lunghezza codificata, la stringa decodificata potrebbe non avviarsi all'inizio del buffer. Se necessario, correggere per questo spostando la stringa verso l'inizio.

---

int isDigit (char c) { 
    return '0' <= c && c <= '9'; 
} 

unsigned int toDigit (char c) { 
    return c - '0'; 
} 

unsigned int intLen (char * str) { 
    unsigned int n = 0; 
    while (isDigit(*str++)) { 
     ++n; 
    } 
    return n; 
} 

unsigned int forwardParseInt (char ** pStr) { 
    unsigned int n = 0; 
    char * pChar = *pStr; 
    while (isDigit(*pChar)) { 
     n = 10 * n + toDigit(*pChar); 
     ++pChar; 
    } 
    *pStr = pChar; 
    return n; 
} 

unsigned int backwardParseInt (char ** pStr, char * beginStr) { 
    unsigned int len, n; 
    char * pChar = *pStr; 
    while (pChar != beginStr && isDigit(*pChar)) { 
     --pChar; 
    } 
    ++pChar; 
    len = intLen(pChar); 
    n = forwardParseInt(&pChar); 
    *pStr = pChar - 1 - len; 
    return n; 
} 

unsigned int encodedSize (char * encoded) { 
    int encodedLen = 0; 
    while (*encoded++ != '\0') { 
     ++encodedLen; 
    } 
    return encodedLen; 
} 

unsigned int decodedSize (char * encoded) { 
    int decodedLen = 0; 
    while (*encoded++ != '\0') { 
     decodedLen += forwardParseInt(&encoded); 
    } 
    return decodedLen; 
} 

void shift (char * str, int n) { 
    do { 
     str[n] = *str; 
    } while (*str++ != '\0'); 
} 

unsigned int max (unsigned int x, unsigned int y) { 
    return x > y ? x : y; 
} 

void decode (char * encodedBegin) { 
    int shiftAmount; 
    unsigned int eSize = encodedSize(encodedBegin); 
    unsigned int dSize = decodedSize(encodedBegin); 
    int writeOverflowed = 0; 
    char * read = encodedBegin + eSize - 1; 
    char * write = encodedBegin + max(eSize, dSize); 
    *write-- = '\0'; 
    while (read != encodedBegin) { 
     unsigned int i; 
     unsigned int n = backwardParseInt(&read, encodedBegin); 
     char c = *read; 
     for (i = 0; i < n; ++i) { 
      *write = c; 
      if (write != encodedBegin) { 
       write--; 
      } 
      else { 
       writeOverflowed = 1; 
      } 
     } 
     if (read != encodedBegin) { 
      read--; 
     } 
    } 
    if (!writeOverflowed) { 
     write++; 
    } 
    shiftAmount = encodedBegin - write; 
    if (write != encodedBegin) { 
     shift(write, shiftAmount); 
    } 
    return; 
} 

int main (int argc, char ** argv) { 
    //char buff[256] = { "!!!A33B1C2D1E1\0!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" }; 
    char buff[256] = { "!!!A2B12C1\0!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" }; 
    //char buff[256] = { "!!!A1B1C1\0!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" }; 
    char * str = buff + 3; 
    //char buff[256] = { "A1B1" }; 
    //char * str = buff; 
    decode(str); 
    return 0; 
}