《剑指offer》替换空格-ag真人游戏

题目描述：

  请实现一个函数，将一个字符串中的每个空格替换成“ ”。例如，当字符串为we are happy.则经过替换之后的字符串为we are happy。

解题思路：

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

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

时间复杂度为o(n^2)的解法。

  从头到尾遍历字符串，当遇到空格时，后面所有的字符都后移2个。

时间复杂度为o(n)的解法。

  可以先遍历一次字符串，这样可以统计出字符串中空格的总数，由此计算出替换之后字符串的长度，每替换一个空格，长度增加2，即替换之后的字符串长度为原来的长度 2*空格数目。接下来从字符串的尾部开始复制和替换，用两个指针p1和p2分别指向原始字符串和新字符串的末尾，然后向前移动p1，若指向的不是空格，则将其复制到p2位置，p2向前一步；若p1指向的是空格，则p1向前一步，p2之前插入 ，p2向前三步。这样，便可以完成替换，时间复杂度为o(n)。
  举例：

代码实现(c )

class solution {
public:
    void replacespace(char *str,int length) {
        int i = 0;
        int numspace =0;
        while(str[i] != '\0')
            {
            if(str[i]==' ')
                numspace  ;
              i;
        }
        int newlen = i numspace*2;
        for(int j=i;j>=0,newlen>=0;)
        {
            if(str[j]==' ')
                {
                str[newlen--] = '0';
                str[newlen--] = '2';
                str[newlen--] = '%';
            }
            else
                str[newlen--] = str[j];
            j--;
        }
    }
};

代码实现(java)

//第一种情况：创建新的字符串实现：
      public string replacespace(stringbuffer str) {
        string res="";
        for(int i=0;i=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();
    }

代码实现(python2.7)

# -*- coding:utf-8 -*-
class solution:
    # s 源字符串
    def replacespace(self, s):
        # write code here
        return s.replace(' ', ' ')

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