替换空格

基础知识

C/C++中每个字符串都以字符'\0'作为结尾，这样我们就能很方便地找到字符串的最后尾部。但由于这个特点，每个字符串中都有一个额外字符的幵销，稍不留神就会造成字符串的越界

 

Java里面一切都是對象，是對象的話，字符串肯定就有长度，即然有长度，编译器就可以確定要輸出的字符个数，当然也就沒有必要去浪費那1字节的空间用以表面字符串的結束了。

 

在网络编程中，如果URL参数中含有特殊字符，如空格、’#'等，则可能导致服务器端无法获得正确的参数值。我们需要将这些特殊符号转换成服务器可以识别的字符。转换的规则是在'％’后面跟上ASCII码的两位十六进制的表示。比如空格的ASCII码是32，即十六进制的0x20,因此空格被替换成"％20"。再比如'#'的 ASCII码为35，即十六进制的0x23,它在URL中被替换为"％23"。

 

原来一个空格字符，替换之后变成’％’、’2'和’0’这 3 个字符，因此字符串会变长。如果是在原来的字符串上进行替换，就有可能覆盖修改在该字符串后面的内存。如果是创建新的字符串并在新的字符串上进行替换，那么我们可以自己分配足够多的内存。由于有两种不同的解决方案，我们应该向面试官问清楚，让他明确告诉我们他的需求。假设面试官让我们在原来的字符串上进行替换，并且保证输入的字符串后面有足够多的空余内存。

问题

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

1、思路

最简单的方法就是从头到尾遍历，但是时间复杂度为O(n^2)。

本文采用一种时间复杂度为O(n)的方法。

我们可以先遍历一次字符串，这样就可以统计出字符串空格的总数，并可以由此计算出替换之后的字符串的总长度。每替换一个空格，长度增加2，因此替换以后字符串的长度等于原来的长度加上2乘以空格数目。以"We are happy"为例，"We are happy"这个字符串的长度为14（包括结尾符号"\n"），里面有两个空格，因此替换之后字符串的长度是18。

我们从字符串的尾部开始复制和替换。首先准备两个指针，P1和P2，P1指向原始字符串的末尾，而P2指向替换之后的字符串的末尾。接下来我们向前移动指针P1，逐个把它指向的字符复制到P2指向的位置，直到碰到第一个空格为止。碰到第一个空格之后，把P1向前移动1格，在P2之前插入字符串"%20"。由于"%20"的长度为3，同时也要把P2向前移动3格。

移动示意图：

import java.util.Arrays;
import java.util.Scanner;
/**
 * @Auther: liuhaidong
 * Data: 2019/10/10 0010、9:22
 * Description:
 * @version: 1.0
 */
public class InsteadOfSpace {
    public static void main(String[] args) {
        System.out.println("请输入一个字符串");
        Scanner sc = new Scanner(System.in);
        System.out.println(insteadOf(sc.nextLine()));
    }

    private static String insteadOf(String s) {
        if(s == null){
            return "";
        }
        int count =0;
         for(int i =0;i<s.length();i++){
             if(s.charAt(i) == ' '){
                 count ++;
             }
         }
         //计算出长度
         char[] newString = new char[s.length()+count*2];
         for(int i =0;i<s.length();i++){
             newString[i] = s.charAt(i);
         }
         //对新的字符串赋值
         int a = s.length()-1;
         //指针p1的位置
        int b = newString.length-1;
        //指针p2的位置
        while (a != b){
            while(' ' != newString[a]){
                  newString[b] = newString[a];
                a--;
                b--;
            }
            newString[b] = '0';
            newString[--b] = '2';
            newString[--b] = '%';
            a--;
            b--;
        }
         return Arrays.toString(newString);
    }

}

2、思路

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。


思路：新定义一个往后追加。
public class Solution {
    public String replaceSpace(StringBuffer str) {
    	StringBuffer newstr = new StringBuffer();
        for(int i = 0;i<str.length();i++)
        {
            if(str.charAt(i) != ' ')
            {
                newstr.append(str.charAt(i));
                
            }
            else
            {
                newstr.append("%20");
            }
        }
        return newstr.toString();
    }
}

3 大神的代码

import java.util.Scanner;

/**
 * @author FengTianHao
 * @version 1.0
 * @since 2018/11/30 11:07
 *
 */
public class Test {
    public String replaceSpace(StringBuffer str) {

        if(str==null||str.length()==0)
        {
            return str.toString();
        }
        int numberOfBlank=0;//空格的数量
        for(int i=0;i<str.length();i++)
        {
            if(str.charAt(i)==' ')
            {
                numberOfBlank++;
            }
        }
        int indexOfOriginal=str.length()-1;//指向旧字符串的最后一个字符
        int newlength=str.length()+numberOfBlank*2;//计算新字符串的长度
        str.setLength(newlength);//将旧字符串的空间扩大
        int indexOfNew=str.length()-1;//指向新字符换的最后一个字符
        for(;indexOfOriginal>=0&&indexOfNew>indexOfOriginal;--indexOfOriginal)
        {
            if(str.charAt(indexOfOriginal)==' ')//当前字符为空格时
            {
                str.setCharAt(indexOfNew--,'0');
                str.setCharAt(indexOfNew--,'2');
                str.setCharAt(indexOfNew--,'%');
            }
            else//当前字符不为空格时
            {
                str.setCharAt(indexOfNew--,str.charAt(indexOfOriginal));
            }
        }

        return str.toString();
    }

    public static void main(String[]args) {
        StringBuffer str=new StringBuffer(" We are happy.");
        System.out.println(new Test().replaceSpace(str));
    }
}