Scrivere un metodo per sostituire tutti gli spazi di una stringa con '% 20'

Question

Ho una domanda su un problema di programmazione dal libro Cracking The Code Intervista di Gayl Laakmann McDowell, 5th Edition.

Il problema afferma: Scrivere un metodo per sostituire tutti gli spazi in una stringa con '% 20'. Si supponga che la stringa abbia spazio sufficiente alla fine della stringa per contenere caratteri aggiuntivi e che venga fornita una lunghezza reale di una stringa. Ho usato il codice di libri, l'implementazione della soluzione in Java utilizzando un array di caratteri (considerato il fatto che Java stringhe sono immutabili):

public class Test { 
    public void replaceSpaces(char[] str, int length) { 
     int spaceCount = 0, newLength = 0, i = 0; 

     for(i = 0; i < length; i++) { 
      if (str[i] == ' ') 
       spaceCount++; 
     } 

     newLength = length + (spaceCount * 2); 
     str[newLength] = '\0'; 
     for(i = length - 1; i >= 0; i--) { 
      if (str[i] == ' ') { 
       str[newLength - 1] = '0'; 
       str[newLength - 2] = '2'; 
       str[newLength - 3] = '%'; 
       newLength = newLength - 3; 
      } 
      else { 
       str[newLength - 1] = str[i]; 
       newLength = newLength - 1; 
      } 
     } 
     System.out.println(str); 
    } 

    public static void main(String[] args) { 
     Test tst = new Test(); 
     char[] ch = {'t', 'h', 'e', ' ', 'd', 'o', 'g', ' ', ' ', ' ', ' ', ' ', ' '}; 
     int length = 6; 
     tst.replaceSpaces(ch, length); 
    } 
} 

L'uscita sto ottenendo dalla chiamata replaceSpaces() è: l'% 20do che sta tagliando l'ultimo carattere dell'array originale. Mi sono grattato la testa per questo, qualcuno può spiegarmi perché l'algoritmo lo sta facendo?

Answer 1

Si passa la lunghezza come 6, che sta causando questo. Passa lunghezza 7 incluso lo spazio. Altri saggi

for(i = length - 1; i >= 0; i--) { 

non prenderà in considerazione l'ultimo carattere.

Answer 2

Con questi due cambiamenti che ho ottenuto l'output: l'% 20dog

1) Modificare lo spazio contare fino a 2 [poiché lunghezza include già 1 dei 3 caratteri necessari per% 20]

newLength = length + (spaceCount * 2); 

2) loop dovrebbe iniziare alla durata

for(i = length; i >= 0; i--) { 

Answer 3

Si tratta di domande intervista jab?

In RealD programmazione mondo vorrei suggerire: URLEncoder.encode()

Answer 4

void Rep_Str(char *str) 
{ 
    int j=0,count=0; 
    int stlen = strlen(str); 
    for (j = 0; j < stlen; j++) 
    { 
     if (str[j]==' ') 
     { 
      count++; 
     } 
    } 

    int newlength = stlen+(count*2); 
    str[newlength--]='\0'; 
    for (j = stlen-1; j >=0 ; j--) 
    { 
     if (str[j]==' ') 
     { 
      str[newlength--]='0'; 
      str[newlength--]='2'; 
      str[newlength--]='%'; 
     } 

     else 
     { 

      str[newlength--]=str[j]; 
     } 

    } 


} 

This code works :) 

Answer 5

Questo è il mio codice per questa domanda. Sembra che lavori per me. Se sei interessato, per favore dai un'occhiata. È scritto in JAVA

public class ReplaceSpaceInString { 
    private static char[] replaceSpaceInString(char[] str, int length) { 
    int spaceCounter = 0; 

    //First lets calculate number of spaces 
    for (int i = 0; i < length; i++) { 
     if (str[i] == ' ') 
     spaceCounter++; 
    } 

    //calculate new size 
    int newLength = length + 2*spaceCounter; 

    char[] newArray = new char[newLength+1]; 
    newArray[newLength] = '\0'; 

    int newArrayPosition = 0; 

    for (int i = 0; i < length; i++) { 
     if (str[i] == ' ') { 
     newArray[newArrayPosition] = '%'; 
    newArray[newArrayPosition+1] = '2'; 
    newArray[newArrayPosition+2] = '0'; 
    newArrayPosition = newArrayPosition + 3; 
     } 
     else { 
    newArray[newArrayPosition] = str[i]; 
    newArrayPosition++; 
     } 
    }    
    return newArray; 
    } 

    public static void main(String[] args) { 
    char[] array = {'a','b','c','d',' ','e','f','g',' ','h',' ','j'}; 
    System.out.println(replaceSpaceInString(array, array.length)); 
    } 
} 

Answer 6

È inoltre possibile utilizzare il metodo di sottostringa e l'ascii per lo spazio (32).

public String replaceSpaceInString(String s){ 
    int i; 
    for (i=0;i<s.length();i++){ 
     System.out.println("i is "+i); 
     if (s.charAt(i)==(int)32){ 
      s=s.substring(0, i)+"%20"+s.substring(i+1, s.length()); 
      i=i+2;    
      } 
    } 
    return s; 
    } 

A prova:

System.out.println(cc.replaceSpaceInString("mon day ")); 

uscita:

mon%20day%20 

Answer 7

È possibile utilizzare StringBuilder?

`

public String replaceSpace(String s) 
{ 
    StringBuilder answer = new StringBuilder(); 
    for(int i = 0; i<s.length(); i++) 
    { 
     if(s.CharAt(i) == ' ') 
     { 
      answer.append("%20"); 
     } 
     else 
     { 
      answer.append(s.CharAt(i)); 
     } 
    } 
    return answer.toString(); 
} 

`

Answer 8

Si potrebbe solo fare questo Non c'è bisogno di calcolare la lunghezza o qualsiasi altra cosa stringhe sono immutabili comunque

import java.util.*; 
public class ReplaceString { 


public static void main(String[] args) { 
    Scanner in=new Scanner(System.in); 
    String str=in.nextLine(); 
    String n=""; 
    for(int i=0;i<str.length();i++) 
    { 
     if(str.charAt(i)==' ') 
      n=n+"%20"; 
     else 
      n=n+str.charAt(i); 
    } 
    str=n; 
    System.out.println(str); 




} 

}

Answer 9

public String replace(String str) { 
    String[] words = str.split(" "); 
    StringBuilder sentence = new StringBuilder(words[0]); 

    for (int i = 1; i < words.length; ++i) { 
     sentence.append("%20"); 
     sentence.append(words[i]); 
    } 

    return sentence.toString(); 
} 

Answer 10

Questo funziona correttamente. Tuttavia, l'uso di un oggetto StringBuffer aumenta la complessità dello spazio.

Scanner scn = new Scanner(System.in); 
    String str = scn.nextLine(); 
    StringBuffer sb = new StringBuffer(str.trim()); 

    for(int i = 0;i<sb.length();i++){ 
     if(32 == (int)sb.charAt(i)){ 
      sb.replace(i,i+1, "%20"); 
     } 
    } 

Answer 11

public static String replaceAllSpaces(String s) { 
    char[] c = s.toCharArray(); 
    int spaceCount = 0; 
    int trueLen = s.length(); 
    int index = 0; 
    for (int i = 0; i < trueLen; i++) { 
     if (c[i] == ' ') { 
      spaceCount++; 
     } 
    } 
    index = trueLen + spaceCount * 2; 
    char[] n = new char[index]; 
    for (int i = trueLen - 1; i >= 0; i--) { 
     if (c[i] == ' ') { 
      n[index - 1] = '0'; 
      n[index - 2] = '2'; 
      n[index - 3] = '%'; 
      index = index - 3; 
     } else { 
      n[index - 1] = c[i]; 
      index--; 
     } 
    } 
    String x = new String(n); 
    return x; 
} 

Answer 12

Un altro modo di fare questo. Io parto dal presupposto gli spazi finali non hanno bisogno di essere convertiti in% 20 e che gli spazi finali forniscono spazio sufficiente per% 20s di essere farcito tra

public class Main { 

    public static void main(String[] args) { 

     String str = "a sd fghj "; 
     System.out.println(replacement(str));//a%20sd%20fghj 
    } 

    private static String replacement(String str) { 
     char[] chars = str.toCharArray(); 
     int posOfLastChar = 0; 
     for (int i = 0; i < chars.length; i++) { 
     if (chars[i] != ' ') { 
      posOfLastChar = i; 
     } 
     } 

     int newCharPosition = chars.length - 1; 

     //Start moving the characters to th end of the array. Replace spaces by %20 
     for (int i = posOfLastChar; i >= 0; i--) { 

     if (chars[i] == ' ') { 
      chars[newCharPosition] = '0'; 
      chars[--newCharPosition] = '2'; 
      chars[--newCharPosition] = '%'; 
     } else { 
      chars[newCharPosition] = chars[i]; 
     } 

     newCharPosition--; 
     } 

     return String.valueOf(chars); 
    } 
} 

Answer 13

public class ReplaceChar{ 

public static void main(String []args){ 
    String s = "ab c de "; 
    System.out.println(replaceChar(s)); 

} 

public static String replaceChar(String s){ 

    boolean found = false; 
    StringBuilder res = new StringBuilder(50); 
    String str = rev(s); 
    for(int i = 0; i <str.length(); i++){ 

     if (str.charAt(i) != ' ') { found = true; } 
     if (str.charAt(i) == ' '&& found == true) { res.append("%02"); }    
     else{ res.append(str.charAt(i)); } 
    } 
     return rev(res.toString()); 
} 

// Function to reverse a string 
public static String rev(String s){ 
    StringBuilder result = new StringBuilder(50); 
    for(int i = s.length()-1; i>=0; i--){ 
     result.append(s.charAt(i)); 
    } 
    return result.toString(); 
}} 

Un approccio semplice:

1. Invertire la stringa specificata e controllare dove viene visualizzato il primo carattere.
2. Utilizzo del generatore di stringhe per aggiungere "02%" per gli spazi, poiché la stringa è invertita.
3. Infine, inverte nuovamente la stringa.

Nota: invertiamo la stringa in modo da impedire l'aggiunta di "% 20" agli spazi finali.

Spero che questo aiuti!

Answer 14

La domanda nel libro indica che la sostituzione dovrebbe essere in posizione, quindi non è possibile assegnare array aggiuntivi, dovrebbe usare uno spazio costante. Si dovrebbe anche prendere in considerazione molti casi limite, questa è la mia soluzione:

public class ReplaceSpaces { 

    public static void main(String[] args) { 
     if (args.length == 0) { 
      throw new IllegalArgumentException("No string"); 
     } 
     String s = args[0]; 
     char[] characters = s.toCharArray(); 

     replaceSpaces(characters); 
     System.out.println(characters); 
    } 

    static void replaceSpaces(char[] s) { 
     int i = s.length-1; 
     //Skipping all spaces in the end until setting `i` to non-space character 
     while(i >= 0 && s[i] == ' ') { i--; } 

     /* Used later to check there is enough extra space in the end */ 
     int extraSpaceLength = s.length - i - 1; 

     /* 
     Used when moving the words right, 
     instead of finding the first non-space character again 
     */ 
     int lastNonSpaceCharacter = i; 

     /* 
     Hold the number of spaces in the actual string boundaries 
     */ 
     int numSpaces = 0; 

     /* 
     Counting num spaces beside the extra spaces 
     */ 
     while(i >= 0) { 
      if (s[i] == ' ') { numSpaces++; } 
      i--; 
     } 

     if (numSpaces == 0) { 
      return; 
     } 

     /* 
     Throw exception if there is not enough space 
     */ 
     if (extraSpaceLength < numSpaces*2) { 
      throw new IllegalArgumentException("Not enough extra space"); 
     } 

     /* 
     Now we need to move each word right in order to have space for the 
     ascii representation 
     */ 
     int wordEnd = lastNonSpaceCharacter; 
     int wordsCounter = 0; 

     int j = wordEnd - 1; 
     while(j >= 0) { 
      if (s[j] == ' '){ 
       moveWordRight(s, j+1, wordEnd, (numSpaces-wordsCounter)*2);   
       wordsCounter++; 
       wordEnd = j; 
      } 
      j--; 
     } 

     replaceSpacesWithAscii(s, lastNonSpaceCharacter + numSpaces * 2); 

    } 

    /* 
    Replaces each 3 sequential spaces with %20 
    char[] s - original character array 
    int maxIndex - used to tell the method what is the last index it should 
    try to replace, after that is is all extra spaces not required 
    */ 
    static void replaceSpacesWithAscii(char[] s, int maxIndex) { 
     int i = 0; 

     while (i <= maxIndex) { 
      if (s[i] == ' ') { 
       s[i] = '%'; 
       s[i+1] = '2'; 
       s[i+2] = '0'; 
       i+=2; 
      } 
      i++; 
     } 
    } 

    /* 
    Move each word in the characters array by x moves 
    char[] s - original character array 
    int startIndex - word first character index 
    int endIndex - word last character index 
    int moves - number of moves to the right 
    */ 
    static void moveWordRight(char[] s, int startIndex, int endIndex, int moves) { 

     for(int i=endIndex; i>=startIndex; i--) { 
      s[i+moves] = s[i]; 
      s[i] = ' '; 
     } 

    } 

} 

Answer 15

Ecco la mia soluzione. A verificare il codice ASCII 32 poi inserisce% 20 anziché it.Time complessità di questa soluzione è O (N)

public String replace(String s) { 

     char arr[] = s.toCharArray(); 
     StringBuilder sb = new StringBuilder(); 

     for (int i = 0; i < arr.length; i++) { 
      if (arr[i] == 32) 
       sb.append("%20"); 
      else 
       sb.append(arr[i]); 

     } 

     return sb.toString(); 
    } 

Answer 16

motivo non usare 'sostituire' metodo?

public String replaceSpaces(String s){ 
    return s.replace(" ", "%20");} 

Answer 17

Hm ... Mi sto interrogando anche su questo problema. Considerando quello che ho visto qui. La soluzione libro non si adatta Java perché utilizza sul posto

char [] 

modifica e soluzioni qui che utilizzano char [] o tornare vuoto non si adattano anche perché Java non usa i puntatori.

Stavo pensando, la soluzione ovvia sarebbe

private static String encodeSpace(String string) { 
    return string.replcaceAll(" ", "%20"); 
} 

ma questo non è probabilmente quello che il vostro intervistatore vorrebbe vedere :)

// make a function that actually does something 
private static String encodeSpace(String string) { 
    //create a new String 
    String result = new String(); 
    // replacement 
    final String encodeSpace = "%20"; 

    for(char c : string.toCharArray()) { 
     if(c == ' ') result+=encodeString; 
     else result+=c; 
    } 

    return result; 
} 

questo guarda bene ho pensato, e si solo bisogno di un passaggio attraverso la stringa, quindi la complessità dovrebbe essere O (n), giusto? Sbagliato! Il problema è in

result += c; 

, che è lo stesso di

result = result + c; 

che in realtà copie una stringa e crea una copia di esso. In stringhe Java sono rappresentati come

private final char value[]; 

che li rende immutabile (per ulteriori informazioni Vorrei verificare java.lang.String e come funziona). Questo fatto aumenterà la complessità di questo algoritmo in O (N^2) e un subdolo reclutatore può usare questo fatto per fallire: P Così, sono arrivato con una nuova soluzione di basso livello che non userete mai in pratica, ma che è buono in teoria :)

private static String encodeSpace(String string) { 

    final char [] original = string != null? string.toCharArray() : new char[0]; 
    // ASCII encoding 
    final char mod = 37, two = 50, zero = 48, space = 32; 
    int spaces = 0, index = 0; 

    // count spaces 
    for(char c : original) if(c == space) ++spaces; 

    // if no spaces - we are done 
    if(spaces == 0) return string; 

    // make a new char array (each space now takes +2 spots) 
    char [] result = new char[string.length()+(2*spaces)]; 

    for(char c : original) { 
     if(c == space) { 
      result[index] = mod; 
      result[++index] = two; 
      result[++index] = zero; 
     } 
     else result[index] = c; 
     ++index; 
    } 

    return new String(result); 
} 

Answer 18

ma mi chiedo che cosa è sbagliato con il seguente codice:

private static String urlify(String originalString) { 

     String newString = ""; 
     if (originalString.contains(" ")) { 
      newString = originalString.replace(" ", "%20"); 
     } 
     return newString; 
    }