黑马程序员技术交流社区

标题: 数组中元素替换问题（要求在原来字符串上进行替换）？ [打印本页]
作者: 小菜_一碟    时间: 2016-11-22 13:49
标题: 数组中元素替换问题（要求在原来字符串上进行替换）？
请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
解析：
最笨的方法就是从前往后遍历，当遇到一个空格时就做替换，由于替换后1个字符就会变成3个字符，那么必须将空格后面的所有字符都后移两个字节，否则就有两个字符被覆盖。如此操作的时间复杂度为O（n^2）。这里就不给出该过程的代码了。

最好的方法应该是从后遍历实现，这样就可以在O(n)时间内完成替换工作了。下面给出代码：
  1. class Solution {
  2. public:
  3.     //length为给字符串分配的空间长度
  4.         void replaceSpace(char* str,int length) {
  5.         if(str == NULL|| length <= 0){
  6.             return;
  7.         }
  8.         
  9.         //统计字符串长度和空格数
  10.         int originalLen = 0;
  11.         int spaceNum = 0;
  12.         int i = 0;
  13.         while(str[i] != '\0'){
  14.             ++originalLen;
  15.             if(str[i] == ' '){
  16.                 ++spaceNum;
  17.             }
  18.             i++;
  19.         }
  20.         
  21.         //计算替换后字符串长度
  22.         int newLen = originalLen + 2 * spaceNum;
  23.         if(newLen > length){
  24.             return;
  25.         }
  26.         
  27.         //从后往前替换空格操作
  28.         int indexOfOriginal = originalLen;
  29.         int indexOfNew = newLen;
  30.         while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal){
  31.             if(str[indexOfOriginal] == ' '){
  32.                 str[indexOfNew--] = '0';
  33.                 str[indexOfNew--] = '2';
  34.                 str[indexOfNew--] = '%';
  35.             }else{
  36.                 str[indexOfNew--] = str[indexOfOriginal];
  37.             }
  38.             --indexOfOriginal;
  39.         }
  40.         }
  41. };
复制代码
作者: 小菜_一碟    时间: 2016-11-22 13:54
以上给出了C代码的过程，因为在Java中已经已经为字符串提供了对应的方法，但是我们也应该对其进行实现过程进行了解。下面给出String源码中两个replace方法的源码实现：
public String replace(char oldChar, char newChar) {
        if (oldChar != newChar) {
            int len = value.length;
            int i = -1;
            char[] val = value; /* avoid getfield opcode */

            while (++i < len) {
                if (val[i] == oldChar) {
                    break;
                }
            }
            if (i < len) {
                char buf[] = new char[len];
                for (int j = 0; j < i; j++) {
                    buf[j] = val[j];
                }
                while (i < len) {
                    char c = val[i];
                    buf[i] = (c == oldChar) ? newChar : c;
                    i++;
                }
                return new String(buf, true);
            }
        }
        return this;
    }


public String replace(CharSequence target, CharSequence replacement) {
        return Pattern.compile(target.toString(), Pattern.LITERAL).matcher(
                this).replaceAll(Matcher.quoteReplacement(replacement.toString()));
}




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2