【剑指offer】 2、替换空格

一时失言乱红尘 2022-12-07 01:15 121阅读 0赞

## 问题 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjExODcxNg_size_16_color_FFFFFF_t_70][]

## 解析 ##

对于这个题目，我们首先想到原来的一个空格替换为三个字符，字符串长度会增加，因此，存在以下两种不同的情况：（1）允许创建新的字符串来完成替换。（2）不允许创建新的字符串，在原地完成替换。

第一种情况比较简单。对于第二种情况，有以下两种解法：

*  **时间复杂度为O(n^2)的解法**。   从头到尾遍历字符串，当遇到空格时，后面所有的字符都后移2个。
 *  **时间复杂度为O(n)的解法。**   可以先遍历一次字符串，这样可以统计出字符串中空格的总数，由此计算出替换之后字符串的长度，**每替换一个空格，长度增加2**，即替换之后的字符串长度为原来的长度+2\*空格数目。接下来从**字符串的尾部开始复制和替换**，用两个指针P1和P2**分别指向原始字符串和新字符串的末尾**，然后向前移动P1，若指向的不是空格，则将其复制到P2位置，P2向前一步；若P1指向的是空格，则P1向前一步，P2之前插入%20，P2向前三步。这样，便可以完成替换，时间复杂度为O(n)。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjExODcxNg_size_16_color_FFFFFF_t_70 1][] 来自 [gzshan][]

## Java代码 ##

### 创建新的字符串实现： ###

public class Solution {
        public String replaceSpace(StringBuffer str) {
            String result = "";
            for(int i=0;i<str.length();i++){
                char c = str.charAt(i);
                if(c==' ')
                    result += "%20";
                else
                    result += c;
            }
            return result;
        }
    }

### 原地替换，O(n)的解法 ###

public String replaceSpace(StringBuffer str) {
            if(str==null)
                return null;
            int numOfblank = 0;//空格数量
            int len=str.length();
            for(int i=0;i<len;i++){  //计算空格数量
                if(str.charAt(i)==' ')
                    numOfblank++;
            }
            str.setLength(len+2*numOfblank); //设置长度
            int oldIndex=len-1;  //两个指针
            int newIndex=(len+2*numOfblank)-1;
            
            while(oldIndex>=0 && newIndex>oldIndex){
                char c=str.charAt(oldIndex);
                if(c==' '){
                    oldIndex--;
                    str.setCharAt(newIndex--,'0');
                    str.setCharAt(newIndex--,'2');
                    str.setCharAt(newIndex--,'%');
                }else{
                    str.setCharAt(newIndex,c);
                    oldIndex--;
                    newIndex--;
                }
            }
            return str.toString();
        }

> 在网络编程中，如果URL参数中含有特殊字符，则可能导致服务器端无法获得正确的参数值，因此可以通过替换的方法将其转换为可以识别的字符。转换规则就是%后面加上该字符ASCII码的16进制表示，如这里的空格，ASCII码是0x20（十进制的32），所以可以替换为%20。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjExODcxNg_size_16_color_FFFFFF_t_70]: /images/20221123/f7a6bdf636414b618c8486638eea8f9e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjExODcxNg_size_16_color_FFFFFF_t_70 1]: /images/20221123/b5e08b73a3754929b46230e39d47a780.png
[gzshan]: https://home.cnblogs.com/u/gzshan/