剑指offer系列之二:字符串空格替换-阿里云开发者社区

开发者社区> rhwayfun> 正文

剑指offer系列之二:字符串空格替换

简介:
+关注继续查看

题目描述:
请实现一个函数,将一个字符串中的空格替换成”%20”。例如,当字符串为We Are Happy,则经过替换之后的字符串为We%20Are%20Happy。

看到这题,我的第一思路是这样的:一组单词不是有空格嘛,所以直接使用String类的split函数直接分割为char数组不就好了,不过在这之前需要判断一下第一个位置和最后一个位置是否有空格,然后针对空格的出现情况再进行替换。发现OJ的时候,如你所猜,自然是失败的。因为我忽略一个问题,就是如果一个句子中都是空格,调用split函数之后会发生什么,会是一组空串。那么根据题目要求,应该全部替换成%20才对。所以这种思路被毙掉了。

于是,我寻找下一种思路,联想到从尾部循环替换的思想(在冒泡排序算法之中也是从尾部往前进行比较然后交换的),于是形成如下的思路:首先统计出该字符串中所有的空格数量,并重新计算新串所需的char数组的长度,把旧串转化成的char数组拷贝到一个临时数组中,并同时创建一个新的char数组,该新数组的长度是计算之后的长度。从该新数组的尾部开始循环,依次往前比较,只要遇到了空格就替换为%20。如果没有遇到空格就直接复制过来就行。

OK,基于以上思路,我写出了如下的代码(已被牛客OJ平台AC了):

package com.rhwayfun.offer;

/**
 * 题目描述
 * 
 * 请实现一个函数,将一个字符串中的空格替换成“%20”。 例如,当字符串为We Are Happy.则经过替换之后的
 * 字符串为We%20Are%20Happy。
 * 
 * @author Administrator
 *
 */
public class ReplaceSpace {
    public String replaceSpace(StringBuffer str) {
        String s = str.toString();
        //统计空格数
        int count = getBlankNum(str.toString());
        //获取原来字符串的长度
        int originalStrLen = s.toCharArray().length;
        //计算替换空格之后需要的长度
        int newStrLen = count * 2 + originalStrLen;
        char[] tempArray = new char[newStrLen];
        //把原字符串复制到tempArray数组中
        System.arraycopy(s.toCharArray(), 0, tempArray, 0, originalStrLen);
        int originalStrIndex = originalStrLen - 1;
        int newStrIndex = newStrLen -1;
        //当originalStrIndex == newStrIndex的时候替换完毕
        while(originalStrIndex >= 0 && originalStrIndex != newStrIndex){
            if(tempArray[originalStrIndex] == ' '){
                tempArray[newStrIndex--] = '0';
                tempArray[newStrIndex--] = '2';
                tempArray[newStrIndex--] = '%';
            }else{
                tempArray[newStrIndex--] = tempArray[originalStrIndex];
            }
            originalStrIndex--;
        }
        return new String(tempArray);
    }

    /**
     * 计算空格数
     * @param string
     * @return
     */
    private int getBlankNum(String string) {
        int count = 0;
        for (int i = 0; i < string.length(); i++) {
            if(string.charAt(i) == ' '){
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        String s = new ReplaceSpace().replaceSpace(new StringBuffer(""));
        System.out.println(s);
    }
}

由于只有一层循环,加上统计空格的时间开销,就是两个循环的时间开销,其他的操作都是O(1)的时间复杂度。所以该算法综合起来的时间复杂度是O(n)

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
4056 0
剑指Offer_5_替换空格
题目描述 请实现一个函数,将一个字符串中的空格替换成“%20”。 例如,当字符串为We Are Happy.则经过替换之后的字符串为 We%20Are%20Happy。    在网络编程中,如果一个URL参数含有特殊字符,如空格,#等,可能导致服务端无法获得准确的参数值。
730 0
C# string格式的日期时间字符串转为DateTime类型
(1 )Convert.ToDateTime(string) string格式有要求,必须是yyyy-MM-dd hh:mm:ss   (2):Convert.ToDateTime(string, IFormatProvider) DateTime dt; DateTimeFormatInfo dtFormat = new System.Globali
865 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
4425 0
Access 2003 中 null 和 '' 空字符串的奇怪问题
最近系统运行中发现Access 2003 版本中对待 Null 和 ‘’ (空字符)奇怪问题,重现步骤: 1、创建表tabTest ; 2、使用设计视图添加两个字段 ID ,col1 名称 类型 长度 说明 ...
590 0
LeetCode 1422. 分割字符串的最大得分
给你一个由若干 0 和 1 组成的字符串 s ,请你计算并返回将该字符串分割成两个 非空 子字符串(即 左 子字符串和 右 子字符串)所能获得的最大得分。
112 0
+关注
111
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载