空格替换

2017-09-15

From : www.LintCode.com

描述
设计一种方法，将一个字符串中的所有空格替换成 %20 。你可以假设该字符串有足够的空间来加入新的字符，且你得到的是“真实的”字符长度。
你的程序还需要返回被替换后的字符串的长度。

注意事项
如果使用 Java 或 Python, 程序中请用字符数组表示字符串。

样例

对于字符串Mr John Smith, 长度为 13

替换空格之后，参数中的字符串需要变为Mr%20John%20Smith，并且把新长度 17 作为结果返回。

解决方案一

注意：这是一个不能被系统接受的方案。下面的解决方案二才是可以被系统接受的。

本方案的思想：
创建一个新的字符串string，然后遍历字符数组。
若不是空格，则将该字符直接加在字符串string的后面。
若是空格，则将字符串“%20”加在字符串string的后面。
遍历结束后，字符串string就是想要的字符串。
然后返回string字符串的长度即可。

代码实现（JAVA）

public class Solution {
    /*
     * @param n: an integer
     * @return: an ineger f(n)
     */
    public int fibonacci(int n) {
        // write your code here
       //输出参数字符数组arr，查看原始的字符串
        //System.out.println(arr);
        //创建一个新的字符串
        String string = "";
        //遍历字符数组
        for (int i = 0; i <length; i++){
            if (arr[i] == ' ') {
                string = string + "%20";
            } else {
                string = string + arr[i];
            }
        }
        int len = arr.length;
        //输出新字符串，查看是否达到要求
        //System.out.println(string);
        return len;
    }
}

解决方案二

本方案的思想：
首先得到新字符串的长度。
遍历数组，每发现一个空格，就把原来字符数组的长度加2（用“%20”三个字符替换掉空格一个字符，所以长度要加2）。
得到新字符串的长度后，则从后向前遍历字符数组，遇到空格就用‘%’、‘2’、‘0’三个字符代替。

代码实现

public class Solution {
/**
 * @param string: An array of Char
 * @param length: The true length of the string
 * @return: The true length of new string
 */
public int replaceBlank(char[] string, int length) {
    // Write your code here
    int reallen = length;
    for (int i = 0; i < length; i++){
        if (string[i] == ' '){
            reallen += 2;
        }
    }
    int index = reallen;
    for (int i = length - 1; i >= 0; i--){
        if (string[i] == ' '){
            string[--index] = '0';
            string[--index] = '2';
            string[--index] = '%';
        } else {
            string[--index] = string[i];
        }
    }
    return reallen;
    }
 }

总结

为什么解决方案一不能通过系统测试，而解决方案二可以？
事实上，两个方案都完成了空格的替换，也都能返回正确的新字符串的长度。
不同的是，方案一将转换后的字符串存放在了一个新的字符串中，而方案二则是将新的字符串存放在了原来的字符数组中。

分析下题目意思：
题目认为，原来的字符数组是足够长的（可以理解为无限长）。而作为参数传递进来的length，则是字符串的真实长度。
例如：有一个字符数组，长度为1000，里面存放了五个字符’h’、’e’、’l’、’l’、’o’，那么作为参数传递进来的真实长度，就是5。
剩下的就如同解决方案二的思想了，不再赘述。

综上所述，本题目应该是希望在原有字符数组的基础上进行替换操作，最后的评判应该是拿参数中的字符数组与期望输出进行比较。
我试了一下将解决方案一中的字符串变为字符数组，并将参数中的字符数组引用指向该字符数组，结果仍不能通过。目测是因为前后的内存地址不同导致的。

其实对这一点我还是有些困惑的，如果你有不一样的见解，欢迎告诉我哈~