(字符串 ) 剑指 Offer 05. 替换空格 ——【Leetcode每日一题】-Toy模板网

这篇具有很好参考价值的文章主要介绍了(字符串 ) 剑指 Offer 05. 替换空格 ——【Leetcode每日一题】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

❓剑指 Offer 05. 替换空格

难度：简单

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

示例 1：

输入：s = “We are happy.”
输出：“We%20are%20happy.”

限制：

0 <= s 的长度 <= 10000

💡思路：双指针法

如果想把这道题目做到极致，就不要只用额外的辅助空间了！

首先扩充数组到每个空格替换成" %20 "之后的大小；
i 指向新长度的末尾，j 指向旧长度的末尾；
然后从后向前替换空格，也就是双指针法。

过程如下：
(字符串 ) 剑指 Offer 05. 替换空格 ——【Leetcode每日一题】

🍁代码：(Java、C++)

Java

class Solution {
    public String replaceSpace(String s) {
        if(s.length() == 0 || s == null) return s;
        StringBuilder str = new StringBuilder();
        //扩充空间，空格数量2倍
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == ' '){
                str.append("  ");
            }
        }
        if(str.length() == 0) return s;
        
        int j = s.length() - 1;//左指针
        s += str.toString();
        int i = s.length() - 1;//右指针
        char[] ch = s.toCharArray();
        while(j < i){
            if(ch[j] != ' ') ch[i] = ch[j];
            else{
                ch[i--] = '0';
                ch[i--] = '2';
                ch[i] = '%';
            }
            j--;
            i--;
        }
        return new String(ch);
    }
}

C++

class Solution {
public:
    string replaceSpace(string s) {
        int count = 0; //统计空格的个数
        for(char c : s){
            if(c == ' ') count++;
        }
        if(count == 0) return s;
        int n = s.size();
        s.resize(n + count * 2);
        for(int j = n - 1, i = n + count * 2 - 1; j < i; i--, j--){//定义左右双指针
            if(s[j] != ' ') s[i] = s[j];
            else{
                s[i--] = '0';
                s[i--] = '2';
                s[i] = '%';
            }
        }
        return s;
    }
};

🚀 运行结果：

(字符串 ) 剑指 Offer 05. 替换空格 ——【Leetcode每日一题】

🕔 复杂度分析：

时间复杂度： $O (n)$ ，其中 n 为字符串 s 的长度。
空间复杂度： $O (1)$ 或 $O (n)$ ，取决于使用的语言中字符串类型的性质。如果字符串是可修改的（C++），那么我们可以直接在原字符串上修改，空间复杂度为 $O (1)$ ，（Java）否则需要使用 $O (n)$ 的空间将字符串临时转换为可以修改的数据结构（例如数组），空间复杂度为 $O (n)$ 。