题目描述

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

示例 1： 输入：s = “We are happy.” 输出：”We%20are%20happy.”

Java解题思路

方法一：利用字符串中现有的方法replaceAll

  1. public static String replaceSpace1(String s)
  2.     {
  3.         return s.replaceAll(" ","%20");
  4.     }

方法二：StringBuilder

如果在原字符串中进行直接替换，是不行的。因为java的字符串是不变的。
然后，我们知道java中的StringBuilder是表达可变字符串的。所以，我们可以用StringBuilder来替换空格。
实现步骤 ：
1、初始化StringBuilder sb；
2、遍历字符串s
1、若遍历到的不是空格，则直接将字符append到sb上，
2、若遍历到的是空格，则将”%20”append到sb上；
3、返回sb.toString

  1. public static String replaceSpace1(String s)
  2.     {
  3.         StringBuilder sb=new StringBuilder();
  4.         for(char c:s.toCharArray())
  5.         {
  6.             if(c==' ')sb.append("%20");
  7.             else sb.append(c);
  8.         }
  9.         return sb.toString();
  10.     }

:::info Tips：
1、增强型for循环：for(ElementType elment:arrayName){}
例如：for（int i:numArray){} for(char c:s.toCharArray()){} for(Object obj:arrayList){}
注意：
1、在使用增强型for循环不支持遍历时删除元素
2、使用增强型for循环时，对遍历的集合需要做null判断，否则可能引发空指针异常。
3、增强型for循环底层是使用了迭代器iterator获取的，不过获取迭代器由Java虚拟机完成，不需要我们获取迭代器，所以使用增强型for循环变量元素的过程中，不准使用集合对象对集合元素个数进行修改。
4、迭代器iterator遍历元素与增强型for变量元素区别：使用迭代器iterator遍历集合元素时可以删除集合的元素，但是增强型for循环遍历集合元素时，不能调用迭代器的remove()方法删除对应下标元素。
5、普通for循环和加强型for循环差别：普通for循环可以没有遍历目标，但加强型for循环必须要有遍历目标。

2、StringBuilder方法详解
StringBuffer 和 StringBuilder 类的对象能够被多次的修改，并且不产生新的未使用对象,本质上是一个 char 类型的动态数组。如果可能，建议优先采用该类，因为在大多数实现中，它比 StringBuffer 要快。然而在应用程序要求线程安全的情况下，则必须使用 StringBuffer 类。 在 StringBuilder 上的主要操作是 append 和 insert 方法。

  • 构造StringBuilder： StringBuilder sb=new StringBuilder(); StringBuilder sb=new StringBuilder(int capacity); StringBuilder sb=new StringBuilder(String str);
  • append 方法始终将这些字符添加到生成器的末端；sb.append(char c);sb.append(String str);
  • 而 insert 方法则在指定的点添加字符。insert(int offset, String str)/insert(int offset, Char c)[offset指偏移量]
  • setCharAt(int i, char c)：将第 i 个代码单元设置为 c（可以理解为替换）

  • delete(int startIndex,int endIndex)：删除起始位置（含）到结尾位置（不含）之间的字符串 :::

    方法三：数组

    当初始化StringBuilder时，会初始化一个固定长度的char类型的数组。当追加的数据个数超过数组的大小时，就需要对char类型的数据进行扩容，会有性能损耗。我们可以通过使用静态数组来解决这个问题。
    方法一实现步骤：
    1、直接创建一个比原字符串长度大三倍的字符数组。
    2、遍历字符串，若是空格，则替换为%20，若不是空格，则直接写入新的字符数组。

    1. class Solution {
    2.   public String replaceSpace(String s) {
    3.       int length=s.length();
    4.       char[] array=new char[length*3];
    5.       int size=0;
    6.       for(int i=0;i<length;++i)
    7.       {
    8.           char c=s.charAt(i);
    9.           if(c==' ')
    10.           {
    11.               array[size++]='%';
    12.               array[size++]='2';
    13.               array[size++]='0';
    14.           }
    15.           else {
    16.               array[size++]=c;
    17.           }
    18.       }
    19.       String newStr=new String(array,0,size);
    20.       return newStr;
    21.   }
    22. }

    方法二实现步骤：
    1、先遍历字符串，确定有几个空格，从而确定新的字符数组的长度。
    2、再次遍历字符串，若是空格，则替换为%20，若不是空格，则直接写入新的字符数组。

    1. public String replaceSpace(String s) {
    2.   int n = s.length();
    3.   int cnt = 0;
    4.   for (char c : s.toCharArray()) {
    5.       if (c == ' ') cnt++;
    6.   }
    8.   char[] newArr = new char[n + 2 * cnt];
    9.   int j = 0;
    10.   for (int i = 0; i < n; i++) {
    11.       char c = s.charAt(i);
    12.       if (c == ' ') {
    13.           newArr[j++] = '%';
    14.           newArr[j++] = '2';
    15.           newArr[j++] = '0';
    16.       } else {
    17.           newArr[j++] = c;
    18.       }
    19.   }
    20.   return new String(newArr);
    21. }

    以上代码的复杂度分析如下：

  • 空间复杂度都是 O(n)

  • 时间复杂度都是 O(n) :::warning 注意：

  • String newStr = new String(array,0,index);的含义：就是将数组array中 索引值从0开始 长度为index 的部分截取出来然后建立一个新的字符串newStr。 :::

C++解题思路