数据结构与算法

替换空格

略

题目：请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

  替换空格在编程中很多时候会用到，例如在hexo博客的新建文章时，由于文件名不推荐存在空格，所以新建文章时候文章名的空格就会转换成“-”。网络编程中也一样，URL参数中的特殊字符很可能会导致服务器无法获得正确的参数，所以需要转换空格。

转换规则：’%’后面跟上ASCII码的两位十六进制的表示。比如空格的ASCII码为32，转换为十六进制为0x20，因此空格替换为”%20“。同理’#’的ASCII码为35，十六进制为0x23，则被替换为”%23“。

分析

耿直的实现方法

  最直观的方法就是从头开始扫描字符串，如果遇到空格，则把空格后面的所有字符全部向后移动两个字节，然后再把‘%‘、’2‘、’0‘这三个字符依次插入到空格和空格后两个位置中，再继续向后扫描字符串重复操作直到到达字符串结尾。

  但是这样做会有一个问题：每遇到一个空格，都要把空格后面的字符串全部向后移动。假设字符串长度为n，对于每个空格需要移动后面O(n)个字符，如果空格有n个，则总的时间效率会是O(n²)。

换一种方式来思考问题

  可以先遍历一次字符串，统计字符串的总长度和字符串中空格的个数。每有一个空格，字符串的长度增加2个字节，最后得到一个新字符串的长度。

  可以从 新字符串最后一个字节开始填充字符串，准备两个指针，P1和P2，P1位于原字符串最后一个字符，P2位于新字符串的最后一个字符，把P1位置的字符赋给P2位置，然后向前移动P1，P2，直到P1指向了一个空格为止，这时P1向前移动一格，P2向前移动3格，并把0、2、%插入到这三格中，再然后接着复制，移动，直到碰到第二个空格，依次类推，当P1与P2指向同个位置时候，表明所有空格已经替换完成。

  从上面可以看出：所有的字符都仅仅移动了一次，所以这个算法的时间复杂度为O(n)。

代码实现

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
    public String replaceSpace(StringBuffer str) {
        int spacenum = 0;//spacenum为计算空格数
        for(int i=0;i<str.length();i++){
            if(str.charAt(i)==' ')
                spacenum++;
        }
      	int newlength = str.length() + spacenum*2;//计算空格转换成%20之后的str长度
      
        int indexold = str.length()-1; //indexold为为替换前的str下标
        int indexnew = newlength-1;//indexold为为把空格替换为%20后的str下标
      
        str.setLength(newlength);//使str的长度扩大到转换成%20之后的长度,防止下标越界
      
        for(;indexold>=0 && indexold<newlength;--indexold){ 
                if(str.charAt(indexold) == ' '){  //遇到空格时
                str.setCharAt(indexnew--, '0');
                str.setCharAt(indexnew--, '2');
                str.setCharAt(indexnew--, '%');
                }else{
                    str.setCharAt(indexnew--, str.charAt(indexold));
                }
        }
        return str.toString();
    }
}

总结

  1. 换个角度看问题，从前向后与从后向前都要考虑到。
  2. 注意用StringBuffer的setLength(int long)方法，确保容器大小合适。
  3. 需要熟练掌握常用的方法，例如setCharAt()，charAt()，setLength()…等。