空格替换

• 题目
• 请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

方法1

• StringBuilder（可变字符串）, 时间O(n),空间O(n)
  1. 初始化一个 StringBuilder 实例 res
  2. 遍历字符串 s 的每个字符：
  3. 当遍历到非空字符的时候，直接将字符 append 到 res 中
  4. 如果遍历到的是空字符，那么将 %20 append 到 res 中
  5. 返回 res.toString
     
  • 补充介绍：
    JAVA中Stringbuffer有append( )方法： 而Stringbuffer是动态字符串数组，append( )是往动态字符串数组添加，跟“xxxx”+“yyyy”相当‘+’号。 跟String不同的是Stringbuffer是放一起的，String1+String2和Stringbuffer1.append("yyyy")虽然打印效果一样，但在内存中表示却不一样、 String1+String2 存在于不同的两个地址内存，Stringbuffer1.append(Stringbuffer2)放再一起。 StringBuffer是线程安全的，多用于多线程。

class Solution {
    public String replaceSpace(String s) {
        StringBuilder res = new StringBuilder();
        for(Character c : s.toCharArray()){
            if(c == ' ') res.append("%20");
            else res.append(c);
        }
        return res.toString();
    }
}

方法2

• 原地交换, 时间O(n),空间O(n)
  • 第一种是直接用‘最坏的打算’，生成最坏的情况需要的空间，然后遍历，插入，最后输出。消耗性能小，占空间大。

public String replaceSpace(String s) {
  int n = s.length();
  char[] newArr = new char[3 * n];
  int j = 0;
  for (int i = 0; i < n; i++) {
    char c = s.charAt(i);
    if (c == ' ') {
      newArr[j++] = '%';
      newArr[j++] = '2';
      newArr[j++] = '0';
    } else {
      newArr[j++] = c;
    }
  }
  return new String(newArr, 0, j);
}

• 第二种是耗性能，但占空间小。当遍历到空格时，重新计算数组长度，再插入。

public String replaceSpace(String s) {
    int n = s.length();
    int cnt = 0;
    for (char c : s.toCharArray()) {
        if (c == ' ') cnt++;
    }
    char[] newArr = new char[n + 2 * cnt];
    int j = 0;
    for (int i = 0; i < n; i++) {
        char c = s.charAt(i);
        if (c == ' ') {
            newArr[j++] = '%';
            newArr[j++] = '2';
            newArr[j++] = '0';
        } else {
            newArr[j++] = c;
        }
    }
    return new String(newArr);
}