题解 | #替换空格#

替换空格

http://www.nowcoder.com/practice/0e26e5551f2b489b9f58bc83aa4b6c68

算法思想一:辅助栈

解题思路:

借助栈存储字符,遇到空格是则入栈 '%20' ,直到字符串入栈结束
图解:

代码展示:

Python版本
class Solution:
    def replaceSpace(self , s ):
        # write code here
        stack = []
        for c in s:
            # 将空格替换 '%20' 并入栈
            if c == ' ':stack.append('%20')
            # 非空正常入栈
            else: stack.append(c)
        # 以字符串形式返回
        return ''.join(stack)

复杂度分析:

时间复杂度O(N):N表示字符串长度
空间复杂度O(N):辅助栈空间

算法思想二:遍历法

解题思想:

由于每次替换从 1 个字符变成 3 个字符,使用字符数组可方便地进行替换。建立字符数组地长度为 s 的长度的 3 倍,这样可保证字符数组可以容纳所有替换后的字符。
1、获得 s 的长度 length
2、创建字符数组 array,其长度为 length * 3
3、初始化 size 为 0,size 表示替换后的字符串的长度
4、从左到右遍历字符串 s
4.1、获得 s 的当前字符 c
4.2、如果字符 c 是空格,则令 array[size] = '%',array[size + 1] = '2',array[size + 2] = '0',并将 size 的值加 3
4.3、如果字符 c 不是空格,则令 array[size] = c,并将 size 的值加 1
5、遍历结束之后,size 的值等于替换后的字符串的长度,从 array 的前 size 个字符创建新字符串,并返回新字符串

代码展示:

JAVA版本
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
    public String replaceSpace (String s) {
        // write code here
        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; 
    } 
}

复杂度分析:

时间复杂度O(N):N表示字符串长度
空间复杂度O(N):辅助数组空间

算法思想三:函数法

解题思路:

简单暴力,直接调用Python中字符串函数 replace

代码展示:

Python版本
class Solution:
    def replaceSpace(self, s):
        return s.replace(' ', '%20')

复杂度分析:

时间复杂度O(1):Python内置算法时间
空间复杂度O(1):不需要额外空间





全部评论

相关推荐

叶扰云倾:进度更新,现在阿里云面完3面了,感觉3面答得还行,基本都答上了,自己熟悉的地方也说的比较细致,但感觉面试官有点心不在焉不知道是不是不想要我了,求阿里收留,我直接秒到岗当阿里孝子,学校那边的房子都退租了,下学期都不回学校,全职猛猛实习半年。这种条件还不诱人吗难道 然后现在约到了字节的一面和淘天的复活赛,外加猿辅导。华为笔试完没动静。 美团那边之前投了个base广州的,把我流程卡麻了,应该是不怎么招人,我直接简历挂了,现在进了一个正常的后端流程,还在筛选,不知道还有没有hc。
点赞 评论 收藏
分享
迟缓的斜杠青年巴比Q了:简历被投过的公司卖出去了,我前两天遇到过更离谱的,打电话来问我有没有意向报班学Java学习,服了,还拿我学校一个学长在他们那报班学了之后干了华为OD当招牌
点赞 评论 收藏
分享
评论
23
7
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务