牛客网-替换空格

本是古典何须时尚 2023-03-01 03:20 5阅读 0赞

# 题目描述 #

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

# 解题1，不考虑时间空间复杂度，暴力解题 #

暴力的解题思路很简单，你可能会想到：有空格的时候直接换成"%20"就行了呗。

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

# 解题2 #

看到解题1，可能会认为很简单，测试结果也对，但是并不是这样子的。

题目是替换空格，那就是在原来的基础上进行替换，`而不是重新组合`。

`来自比特蛋哥：`

//字符串操作问题
    //解决思路:
    //虽然是替换问题,但是生成的字符串整体变长了.
    //因替换内容比被替换内容长,所以,一定涉及到字符串中字符的移动问题
    //移动方向一定是向后移动,所以现在的问题无非是移动多少的问题
    //因为是 ' ' -> "%20",是1换3,所以可以先统计原字符串中空格的个数(设为n),然后可以计算出新字符串的长度
    //所以:new_length = old_length + 2*n
    //最后,定义新老索引(或者指针),各自指向新老空间的结尾,然后进行old->new的移动
    //如果是空格,就连续放入“%20”,其他平移即可。
    //当然,C++和Java都有很多容器,也可以从前往后通过开辟空间来进行解决。也就是使用空间来换取时间。
    //但是,我们最好不要在当前场景下这么做

public class Solution { 
        public String replaceSpace(StringBuffer str) { 
                  //统计出来有多少个空格
                int n = 0;
                for (int i = 0; i <str.length() ; i++) { 
                    if(str.charAt(i)==' ')
                        n++;
                }
    
                //设置新的字符串的长度
                int new_len = str.length()+(n*2); //计算出来新的字符串的长度
    
                int old_end = str.length()-1; //旧字符串索引最后一个有效位置
                int new_end = new_len-1; //新字符串索引最后一个有效位置
    
                str.setLength(new_len);//设置字符串新的长度大小，防止越界
    
                while (old_end>=0 && new_end>=0){ 
    
                    //如果当前位置是空格
                    if(str.charAt(old_end)==' '){ 
                        //就从当前空格的位置往后移动进行替换
                        str.setCharAt(new_end--,'0');
                        str.setCharAt(new_end--,'2');
                        str.setCharAt(new_end--,'%');
    
                        --old_end;
                    }else { 
    
                        //当前位置不是空格，就平移
    
                        str.setCharAt(new_end--,str.charAt(old_end--));
                    }
                }
    
    
    
    
            return str.toString();
        }
    }