java - 用%20替换空格时长度的值

Question

我正在解决用破解编码面试第 5 版中的 %20 替换空格的问题:

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)

我的算法是:

public static void replaceSpaces(String input, int length) {

    char[] str = input.toCharArray();

    int spaceCount = 0;
    for(int i = length - 1; i >= 0; i--){
        if(str[i] == ' ') {
            spaceCount++;
        }
    }

    int newLength = length + spaceCount * 2;

    str[newLength] = '\0';

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

打印出函数的每一步，这是我的输出:

Mr John Smith   h
Mr John Smith  th
Mr John Smith ith
Mr John Smithmith
Mr John SmitSmith
Mr John S%20Smith
Mr John n%20Smith
Mr Johnhn%20Smith
Mr Johohn%20Smith
Mr JoJohn%20Smith
Mr%20John%20Smith
Mr%20John%20Smith
Mr%20John%20Smith

我有两个问题:

1. 我们知道字符串的新长度是17。我不明白的是，为什么我们需要 [newLength - 1] 而不是 [newLength]。我们有兴趣替换当前索引，不是吗？还是因为新的长度是17，但是换算成索引，实际上是16(第0个索引)。

2. 目的是什么:str[newLength] = '\0';

Answer 1

我们并不都拥有那本书，但从待定的编辑中，我看到确切的问题是:

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)

来自 Cracking the Coding Interview 第 5 版

---

因此，它表示您的 input 参数应该是 char[]。

由于您要更改文本的长度，因此您的方法需要返回新的长度。

---

问题 1:

We know the new length of the string is 17. What I do not understand is, why we need to have [newLength - 1] instead of [newLength]. We are interested in replacing the current index, no? Or is it because the new length is 17, but when converted to indices, it's actually 16 (0th index).

你自己回答了。长度为 17，索引为 0 到 16。如果数组只有 17 长，则访问索引 17 并抛出 IndexOutOfBoundsException。

---

问题 2:

What is the purpose of: str[newLength] = '\0';

什么都没有。它是无效的，在 Java 中没有任何意义。将其删除。

Java 字符串有一个length()。在 C 中，字符串以零结尾，但在 Java 中不是。

---

要测试代码，请尝试运行它:

char[] buffer = { 'M','r',' ','J','o','h','n',' ','S','m','i','t','h','*','*','*','*' };
int inLen = 13;
System.out.println("buffer: '" + new String(buffer) + "'");
System.out.println("inLen : " + inLen);
System.out.println("input : '" + new String(buffer, 0, inLen) + "'");
int outLen = replaceSpaces(buffer, inLen);
System.out.println("outLen: " + outLen);
System.out.println("result: '" + new String(buffer, 0, outLen) + "'");

输出应该是:

buffer: 'Mr John Smith****'
inLen : 13
input : 'Mr John Smith'
outLen: 17
result: 'Mr%20John%20Smith'

在方法中访问 input[17] 会抛出 IndexOutOfBoundsException。

---

这是一种基于所示代码的可能实现，它跟在引用的文本之后，并在所有空格都被替换后停止处理。

public static int replaceSpaces(char[] str, int length) {
    int spaceCount = 0;
    for (int i = length - 1; i >= 0; i--)
        if (str[i] == ' ')
            spaceCount++;
    int shift = spaceCount * 2;
    int newLength = length + shift;
    for (int i = newLength - 1; shift > 0; i--) {
        char c = str[i - shift];
        if (c != ' ') {
            str[i] = c;
        } else {
            str[i] = '0';
            str[--i] = '2';
            str[--i] = '%';
            shift -= 2;
        }
    }
    return newLength;
}

这会从上面的测试代码中产生预期的输出。