字符串——剑指 Offer 05. 替换空格

简介: 本专栏按照数组—链表—哈希—字符串—栈与队列—二叉树—回溯—贪心—动态规划—单调栈的顺序刷题,采用代码随想录所给的刷题顺序,一个正确的刷题顺序对算法学习是非常重要的,希望对大家有帮助

1 题目描述

剑指 Offer 05. 替换空格

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

2 题目示例

示例 1:

输入:s = "We are happy."
输出:"We%20are%20happy."

3 题目提示

0 <= s 的长度 <= 10000

4 思路

这道题的解法非常多,利用很多原生 apiapi 就能轻松解决,例如:

repleace/replaceAll
encodeURIComponent
split/join
亦或者直接暴破求解等等...

但是我们清楚,这些肯定都不是被考察的目的,我们需要做的,就是如何在手动实现的过程中,尽量的减少复杂度!
值得注意的是:数组遍历,一定要从后往前遍历,避免从前往后,造成字符被修改,导致错误!

由于每次替换从1个字符变成3个字符,使用字符数组可方便地进行替换。建立字符数组地长度为s的长度的3倍,这样可保证字符数组可以容纳所有替换后的字符。

  • 获得s 的长度 1ength
  • 创建字符数组array,其长度为1ength * 3
  • 初始化size为0,size表示替换后的字符串的长度
  • 从左到右遍历字符串s

    • 获得s的当前字符c
    • 如果字符c是空格,则令array[size] = ‘%’,array[size + 1] = '2’, array[size + 2] ='0’,并将size的值加3
    • 如果字符C不是空格,则令array[size] = c,并将size的值加1
  • 遍历结束之后,size的值等于替换后的字符串的长度,从array 的前size个字符创建新字符串,并返回新字符串

复杂性分析

时间复杂度:O(n)O(n)。遍历字符串 s 一遍。
空间复杂度:O(n)O(n)。额外创建字符数组,长度为 s 的长度的 3 倍。

5 我的答案

class Solution {
    public String replaceSpace(String s) {
        int length = s.length();
        char[] array = new char[length * 3];
        int size = 0;
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            if (c == ' ') {
                array[size++] = '%';
                array[size++] = '2';
                array[size++] = '0';
            } else {
                array[size++] = c;
            }
        }
        String newStr = new String(array, 0, size);
        return newStr;
    }
}
相关文章
|
6月前
|
Java C++ Python
剑指 Offer 05:替换空格
剑指 Offer 05:替换空格
42 0
|
2月前
|
C语言 C++
剑指 Offer(第 2 版)刷题 | 05. 替换空格
本文是作者在刷《剑指 Offer(第 2 版)》时对 "替换空格" 问题的解法分享,包括正确处理字符串中空格替换为"%20"的解法以及未刷题小白可能会犯的错误,同时记录了在解决过程中遇到的运行时错误。
剑指 Offer(第 2 版)刷题 | 05. 替换空格
|
6月前
剑指 Offer 38:字符串的排列
剑指 Offer 38:字符串的排列
48 0
|
6月前
剑指 Offer 50:第一个只出现一次的字符
剑指 Offer 50:第一个只出现一次的字符
35 0
|
6月前
|
Java C++ Python
剑指 Offer 58 - II:左旋转字符串
剑指 Offer 58 - II:左旋转字符串
63 0
|
6月前
剑指Offre 面试题05. 替换空格
剑指Offre 面试题05. 替换空格
40 0
|
C++ 容器
剑指 Offer 58 - II. 左旋转字符串(3种方法)
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。 请定义一个函数实现字符串左旋转操作的功能。 比如,输入字符串"abcdefg"和数字2,该函数将返回左旋转两位得到的结果"cdefgab"。
70 0