In che modo è più efficiente ottenere il conteggio dello spazio?

Question

In che modo è più efficiente ottenere il conteggio dello spazio?

#1 da (3 voti)
#2 da (1 voti)

3

Ho appena iniziato a leggere Cracking the Coding Interview . Uno dei problemi (in particolare 1.4) dopo aver risolto e poi guardando la risposta mi ha fatto dubitare del modo in cui è stato fatto e ho deciso di postarlo qui per vedere se mi manca qualcosa.

Ecco il problema:

Write a method to replace all spaces in a string with '%20'. You may assume that the string has sufficient space at the end of the string to hold the additional characters, and that you are given the 'true' length of the string. (Note: if implementing in Java, please use a character array so that you can perform this operation in place.)

Esempio: inserire "Mr John Smith", 13 Uscita "Mr% 20John% 20Smith"

Soluzione dell'autore:

public void replaceSpaces(char[] str, int length)
{
    int spaceCount = 0, newLength, i;
    for(i=0; i<length; i++)
    {
        if (str[i] == '')
        {
           spaceCount++;
        }
    }  
    // ...  
}

Metto ... perché il resto è irrilevante alla mia domanda.

Perché eseguire il ciclo di ricerca per trovare spaceCount se puoi calcolare solo (str.length - length) / 2 ?

algorithms strings efficiency

posta AvetisG 21.02.2015 - 19:49

fonte

2 risposte

1

il ciclo spaceCount conta tutti gli spazi reali nella stringa, e ignora gli spazi alla fine (dato che ti è stata data la lunghezza effettiva della stringa meno il spazio finale nel parametro length ).

Le specifiche non dicono che la quantità di spazio rimasto alla fine della stringa coincida esattamente con lo spazio richiesto per contenere i caratteri aggiuntivi, solo che c'è spazio sufficiente.

risposta data 21.02.2015 - 19:55

fonte

Leggi altre domande sui tag algorithms strings efficiency

Ambiguità di nomi di metodi apparentemente chiari nelle API Separazione della logica dai risultati della presentazione nella ripetizione del codice

score 3 · Accepted Answer

La definizione che hai pubblicato dice:

You may assume that the string has sufficient space at the end of the string to hold the additional characters.

E non:

You may assume that the string has exactly enough space at the end of the string to hold the additional characters.

Lezione 1 nell'intervista con il codice è leggere (o ascoltare) attentamente la specifica. È completamente possibile che la lunghezza dell'array sia 1 milione, ma la stringa contiene solo due spazi. In questo caso, supponendo che tu possa semplicemente sottrarre le due lunghezze, hai assunto (senza verificare) una parte della specifica che non era esplicita, e quasi sicuramente perderesti punti.