java - 文字列内のすべてのスペースを「％20」に置き換えるメソッドを記述します

Question

ゲイル・ラークマン・マクダウェル著 『世界で闘うプログラミング力』第5版から、プログラミングの問題について質問があります。

問題は次のように述べています。文字列内のすべてのスペースを「％20」に置き換えるメソッドを記述します。文字列の末尾に追加の文字を保持するのに十分なスペースがあり、文字列の実際の長さが与えられていると想定します。私は本のコードを使用し、文字配列を使用してJavaでソリューションを実装しました（Java文字列は不変であるという事実を前提としています）。

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);  
    }
}

replaceSpaces()呼び出しから得られる出力は次のとおりです。元の配列の最後の文字を切り取った％20do 。私はこれに頭を悩ませてきましたが、アルゴリズムがこれを行っている理由を誰かが私に説明できますか？

Answer 1

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 2

長さを6として渡しているため、これが発生しています。パスの長さはスペースを含めて7です。さもないと

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

最後の文字は考慮されません。

Answer 3

これらの2つの変更により、出力が得られました：％20dog

1）スペース数を2に変更します[長さには、％20に必要な3文字のうちの1文字がすでに含まれているため]

newLength = length + (spaceCount * 2);

2）ループは長さで開始する必要があります

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

Answer 4

これが私の解決策です。私はASCIIコード32をチェックし、その代わりに％20を入れます。このソリューションの時間計算量は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 5

これがこの質問の私のコードです。私のために働いているようです。興味のある方は是非ご覧ください。それは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

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];
        }
    }
}

このコードは機能します:)

Answer 7

部分文字列メソッドとスペースのASCIIを使用することもできます（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;
    }

テストする：

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

出力：

mon%20day%20

Answer 8

あなたはこれを行うことができます。長さなどを計算する必要はありません。文字列はとにかく不変です。

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 replaceStringWithSpace(String str){
     return str.replaceAll("[\\s]", "%20");
 }

Answer 10

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 11

これは正しく機能します。ただし、StringBufferオブジェクトを使用すると、スペースが複雑になります。

    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 12

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 13

これを行う別の方法。末尾のスペースを％20に変換する必要はなく、末尾のスペースには、％20を間に詰めるのに十分なスペースがあると想定しています。

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 14

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();
 }}

簡単なアプローチ：

1. 指定された文字列を逆にして、最初の文字が表示される場所を確認します。
2. 文字列ビルダーを使用してスペースに「02％」を追加します-文字列が逆になっているためです。
3. 最後にもう一度文字列を逆にします。

注：末尾のスペースに「％20」が追加されないように、文字列を逆にします。

お役に立てば幸いです。

Answer 15

この本の質問には、余分な配列を割り当てることができないように置換を行う必要があり、一定のスペースを使用する必要があると記載されています。また、多くのエッジケースを考慮する必要があります。これが私の解決策です。

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 16

'replace'メソッドを使用しない理由はありますか？

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

Answer 17

うーん...私もこの問題について疑問に思っています。私がここで見たものを考えると。ブックソリューションはインプレースを使用するため、Javaには適合しません

 char []

ここでのchar[]またはreturnvoidを使用する変更と解決策は、Javaがポインターを使用しないため、同様に適合しません。

だから私は考えていました、明白な解決策は

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

しかし、これはおそらくあなたのインタビュアーが見たいものではありません:)

// 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;
}

これは私が思ったようにうまく見えます、そしてあなたは文字列を1回通過するだけでよいので、複雑さはO（n）であるはずですよね？間違い！問題は

result += c;

これはと同じです

result = result + c;

これは実際に文字列をコピーし、そのコピーを作成します。Javaでは、文字列は次のように表されます。

private final char value[];

これにより、それらは不変になります（詳細については、 java.lang.Stringとその動作を確認します）。この事実は、このアルゴリズムの複雑さをO（N ^ 2）に押し上げ、卑劣なリクルーターはこの事実を使用して失敗する可能性があります：Pしたがって、実際には決して使用しない新しい低レベルのソリューションを思いつきました。しかし、これは理論的には良いことです:)

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

しかし、次のコードの何が問題になっているのでしょうか。

private static String urlify(String originalString) {

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

Answer 19

質問：スペースを％20でUrlify

解決策1：

public class Solution9 {
public static void main(String[] args) {
    String a = "Gini Gina Protijayi";


       System.out.println(   urlencode(a));
}//main

public static String urlencode(String str) {
      str = str.trim();
        System.out.println("trim =>" + str);

        if (!str.contains(" ")) {
            return str;
        }

    char[] ca = str.toCharArray();

    int spaces = 0;
    for (char c : ca) {
        if (c == ' ') {
            spaces++;
        }
    }

    char[] newca = new char[ca.length + 2 * spaces];
      //  a pointer x has been added
    for (int i = 0, x = 0; i < ca.length; i++) {
        char c = ca[i];
        if (c == ' ') {
            newca[x] = '%';
            newca[x + 1] = '2';
            newca[x + 2] = '0';
            x += 3;
        } else {
            newca[x] = c;
            x++;
        }
    }
    return new String(newca);
}

}//urlify

Answer 20

時間計算量O（n）のStringBuilderを使用した私のソリューション

public static String url(String string, int length) {
    char[] arrays = string.toCharArray();
    StringBuilder builder = new StringBuilder(length);

    for (int i = 0; i < length; i++) {
        if (arrays[i] == ' ') {
            builder.append("%20");
        } else {
            builder.append(arrays[i]);
        }
    }

    return builder.toString();
}

テストケース ：

@Test
public void testUrl() {
    assertEquals("Mr%20John%20Smith", URLify.url("Mr John Smith ", 13));
}

Answer 21

私も本の中でその質問を見ています。私たちはここでただ使うことができるString.trim()と信じていますString.replaceAll(" ", "%20)

Answer 22

ここでソリューションを更新しました。http://rextester.com/CWAPCV11970

インプレーストラクションではなく新しいアレイを作成している場合、なぜ後方に歩く必要があるのでしょうか。

実際のソリューションを少し変更して、ターゲットのUrlエンコード文字列を作成しました。

時間計算量：

  O(n) - Walking original string
  O(1) - Creating target string incrementally

  where 'n' is number of chars in original string

スペースの複雑さ： O（n + m）-エスケープされたスペースと文字列を格納するための重複スペース。ここで、「n」は元の文字列の文字数、「m」はエスケープされたスペースの長さです。

    public static string ReplaceAll(string originalString, char findWhat, string replaceWith)
    {
        var newString = string.Empty;
        foreach(var character in originalString)
            newString += findWhat == character? replaceWith : character + string.Empty;
        return newString;
    }

Answer 23

class Program
{
    static void Main(string[] args)
    {
        string name = "Stack Over Flow ";
        StringBuilder stringBuilder = new StringBuilder();

        char[] array = name.ToCharArray(); ;

        for(int i = 0; i < name.Length; i++)
        {
            if (array[i] == ' ')
            {
                stringBuilder.Append("%20");
            }
            else
                stringBuilder.Append(array[i]);
        }



        Console.WriteLine(stringBuilder);
        Console.ReadLine();

    }
}

Answer 24

パブリッククラスソル{

public static void main(String[] args) {
    String[] str = "Write a method to replace all spaces in a string with".split(" ");
    StringBuffer sb = new StringBuffer();
    int count = 0;

    for(String s : str){
        sb.append(s);
        if(str.length-1 != count)
        sb.append("%20");
        ++count;
    }

    System.out.println(sb.toString());
}

}

Answer 25

public class Test {
    public static void 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]);
        }
        sentence.append("%20");
        System.out.println(sentence.toString());
    }
    public static void main(String[] args) {
        replace("Hello   World "); **<- Hello<3spaces>World<1space>**
    }
}

O / P :: Hello％20％20％20World％20

Answer 26

後者が先頭または末尾のスペースでない場合にのみ、''を'％20'に置き換えたいことを覚えておいてください。上記のいくつかの答えはこれを説明していません。Laakmannのソリューション例を実行すると、「インデックスの範囲外エラー」が発生します。

これがO（n）を実行し、C＃で実装されている私自身のソリューションです。

        public static string URLreplace(string str, int n)
        {
            var len = str.Length;

            if (len == n)
                return str;

            var sb = new StringBuilder();
            var i = 0;

            while (i < len)
            {
                char c = str[i];

                if (c == ' ')
                {
                    while (i < len && str[i] == ' ')
                    {
                        i++; //skip ahead
                    }
                }
                else
                {
                    if (sb.Length > 0 && str[i - 1] == ' ')
                        sb.Append("%20" + c);
                    else
                        sb.Append(c);
                    i++;
                }
            }

            return sb.ToString();
        }

テスト：

        //Arrange
        private string _str = "                Mr  John  Smith   ";
        private string _result = "Mr%20John%20Smith";
        private int _int = 13;

        [TestMethod]
        public void URLified()
        {
            //Act
            var cleaned = URLify.URLreplace(_str, _int);

            //Assert
            Assert.IsTrue(cleaned == _result);
        }

Answer 27

1行のコードSystem.out.println（s.trim（）。replace（ ""、 "％20"））;

Answer 28

//入力を渡すときは、文字列が不変であるため、必ず.toCharArrayメソッドを使用してください

public static 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 = "Mr John Smith    ".toCharArray();
    int length = 13;
    replaceSpaces(ch, length);
}

Answer 29

`// Maximum length of string after modifications.

const int MAX = 1000;

// Replaces spaces with %20 in-place and returns
// new length of modified string. It returns -1

// if modified string cannot be stored in str[]

int replaceSpaces(char str[])

{
    // count spaces and find current length
    int space_count = 0, i;
    for (i = 0; str[i]; i++)
        if (str[i] == ' ')
            space_count++;

    // Remove trailing spaces
    while (str[i-1] == ' ')
    {
       space_count--;
       i--;
    }

    // Find new length.
    int new_length = i + space_count * 2 + 1;

    // New length must be smaller than length
    // of string provided.
    if (new_length > MAX)
        return -1;

    // Start filling character from end
    int index = new_length - 1;

    // Fill string termination.
    str[index--] = '\0';

    // Fill rest of the string from end
    for (int j=i-1; j>=0; j--)
    {
        // inserts %20 in place of space
        if (str[j] == ' ')
        {
            str[index] = '0';
            str[index - 1] = '2';
            str[index - 2] = '%';
            index = index - 3;
        }
        else
        {
            str[index] = str[j];
            index--;
        }
    }

    return new_length;
}

// Driver code
int main()
{
    char str[MAX] = "Mr John Smith   ";

    // Prints the replaced string
    int new_length = replaceSpaces(str);
    for (int i=0; i<new_length; i++)
        printf("%c", str[i]);
    return 0;
}`