提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

替换空格（剑指offer 05）

2023-03-14 22:47:57 时间

一、题目描述 


请实现一个函数，把字符串 s 中的每个空格替换成"%20"。


示例 1：


输入：s = "We are happy."

输出："We%20are%20happy."


限制：

0 <= s 的长度 <= 10000


二、思路讲解

       

题目中的字符串在操作时长度发生变化，由于字符串是不可变类型，显然使用字符数组操作更加便捷。


三、算法描述

       

创建一个字符数组a，长度为s的三倍（考虑所有全部为空格的极端情况），然后遍历s：若不为空格，则直接复制到a中；若为空格，则在a中添加"%20"。


四、Java代码实现


class Solution {
    
    public String replaceSpace(String s) {
 
        char []a = new char[s.length()*3];
        int index = 0;  //字符数组中的索引，标记现在添加到了哪里
 
        for(int i=0;i<s.length();i++) {
            char temp = s.charAt(i);
            //如果是空格，在a中添加"%20"
            if(temp == ' ') {
                a[index++] = '%';
                a[index++] = '2';
                a[index++] = '0';
                
            } else {
                a[index++] = temp;
            }
        }
        
        return new String(a, 0, index);
    }
}



五、时空复杂度分析


时间复杂度：O(n)        遍历了字符串s

空间复杂度：O(n)        创建了一个字符数组a


执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：35.8 MB, 在所有 Java 提交中击败了99.53%的用户


六、其他代码实现


1、C++


class Solution {
public:
    string replaceSpace(string s) {     //字符数组
        string array;   //存储结果
        
        for(auto &c : s){   //遍历原字符串
            if(c == ' '){
                array.push_back('%');
                array.push_back('2');
                array.push_back('0');
            }
            else{
                array.push_back(c);
            }
        }
        return array;
    }
};


相关文章