文档章节

剑指Offer(Java)-替换空格

一贱书生
 一贱书生
发布于 2016/07/15 16:30
字数 2173
阅读 10
收藏 0

题目:请实现一个函数,把字符串中的每个空格替换成“%20”。例如输入“We are happy",则输出”We%20are%20happy".

原因:在网络编程中,如果URL参数中含有特殊字符,如:空格、“#”等,可能导致服务器端无法获得正确的参数值。我们需要将这些特殊符号转换成服务器识别的字符。转换规则是在“%”后面跟上ASCII码的两位十六进制的表。比如:空格的ASCII玛是32,即十六进制的0x20,因此空格被替换成“%20”。

时间复杂度为O(n^2)不足以拿到Offer

现在我们考虑怎么做替换操作。最直观的做法是从头到尾扫描字符串,每一次碰到空格字符的时候做替换。由于是把1个字符替换称3个字符,我们必须把空格后面的所有的字符都后移两个字节,否则就有两个字符被覆盖了。

举个例子,我们从头到尾把“We are happy"中的每一个空格替换成”%20“。为了形象期间,我们可以用一个表格来表示字符串,表格中的每个格子表示一个字符。如下图所示:

我们替换了第一个空格,这个字符串编程图b中的内容,表格中灰色背景表示需要移动的字符。接着我们替换第二个空格,替换之后的内容如图c所示。同时我们注意到用深灰色的北京标注”happy“部分被移动了两次。

假设字符的长度是n。对每个空格字符,需要移动后面O(n)个字符,因此对含有O(n)个空格字符串而言总的时间效率是O(n^2).

如下代码:

package cglib;

public class SingletonClass {

    public static void main(String args[]){
        String s="We are happy.";
        System.out.println(replaceBlank(s));
        }
        public static String replaceBlank(String input){
        if(input==null)
        return null;
        StringBuffer outputBuffer=new StringBuffer();
        for(int i=0;i<input.length();i++){
        if(input.charAt(i)==' '){
        outputBuffer.append("%");
        outputBuffer.append("2");
        outputBuffer.append("0");
        }else {
        outputBuffer.append(String.valueOf(input.charAt(i)));
        }
        }
        return new String(outputBuffer);
        }
}


输出为:

We%20are%20happy.

当我们把这种思路和代码阐述给面试官后,他不会就此满意,他将让我们寻找更快的方法。在前面的分析中,我们发现数组中的很多字符都移动了很多次,能不能减少移动的次数呢?我们换一种思路,把从前向后替换成从后向前替换。

考虑时间复杂度为O(n)的解法,搞定Offer就靠它了

 

我们先遍历一次字符串,这样就能够统计出字符串中空格的综述,并可以计算出替换之后字符串的总的长度。每替换一个空格,长度增加2,因此替换以后的 字符串的长度等于原来的长度加上2乘以空格的数目,我们还是以前面的字符串”We are happy"为例,“We are happy"这个字符串的长度是14,里面有两个空格,因此替换之后的字符串的长度为18

我们从字符串的后面开始复制和替换。首先准备两个指针,P1和P2.   P1指向原始字符串的末尾,而P2指向替换之后的字符串的末尾。接下来我们向前移动指针P1,逐个把它指向的字符复制到P2指向的位置,直到碰到第一个空 格为止。此时字符串包含如下图b所示,灰色阴影的区域是做了字符拷贝的区域。碰到第一个空格之后,把P1向前移动一格,在P2之前插入字符串”%20“, 由于”%20“的长度为3,同时也要把P2向前移动3格如图所示。

我们接着向前复制,直到碰到第二个空格(d)所示。和上一次一样,我们再把P1向前移动1格,并把P2向前移动3格插入”%20“(如图e),此时P1,P2指向同一个位置,表明所有的空格都已经替换完毕。

从上面的分析我们可以看出,所有的字符都只复制一次,因此这个算法的时间效率是O(n),比第一个思路要快。

实现如下:

package cglib;

public class SingletonClass {

     //计算字符串中包含的空格个数  
    public static int getBlankNum(String testString){  
        int count = 0 ;  
        for(int i = 0;i<testString.length();i++){  
            String tempString = String.valueOf(testString.charAt(i));  
            if(tempString.equals(" ")){  
                count++;  
            }  
        }  
        return count;  
    }  
    //打印char[] 数组  
    public static void printArray(char[] testArray){
        System.out.println("开始打印数组");
        for(char i :testArray){  
            System.out.print(i);  
        }  
        System.out.println();  
    }  
    //将字符串空格转化为20%  
    public static void replaceAllBlank(String testString){  
        if(testString == null || testString.length() <= 0){  
            return;  
        }  
        //字符数组初始长度  
        int length = testString.length();
        System.out.println("字符串原始长度:"+length);
        //字符数组增加长度后  
        int newLength = testString.length()+ getBlankNum(testString)*2;  
        System.out.println("字符串增加后的长度:"+newLength);
        char[] tempArray = new char[newLength];
        System.out.println("数组:"+tempArray);
        System.arraycopy(testString.toCharArray(), 0, tempArray, 0, testString.toCharArray().length);  
        System.out.println("字符:"+testString.toCharArray());
        System.out.println("长度:"+testString.toCharArray().length);
        int indexofOriginal = length - 1;  
        int indexofNew = newLength -1;  
        System.out.println("未替换空格时的字符串:");  
        printArray(testString.toCharArray());
    
        while(indexofOriginal >=0 && indexofOriginal != indexofNew){
            System.out.println("indexofOriginal:"+indexofOriginal);//原始数组最后一位
            System.out.println("indexofNew:"+indexofNew);//替换数组最后一位
            System.out.println("tempArray[indexofOriginal]:"+tempArray[indexofOriginal]);
            if(tempArray[indexofOriginal]==' '){
                System.out.println("出现空格,替换");
                tempArray[indexofNew--]='0';
                System.out.println("替换第一个字符后:tempArray[indexofNew]="+tempArray[indexofNew]);
                System.out.println("替换第一个字符后:indexofNew="+indexofNew);
                tempArray[indexofNew--]='2';
                System.out.println("替换第二个字符后:tempArray[indexofNew]="+tempArray[indexofNew]);
                System.out.println("替换第二个字符后:indexofNew="+indexofNew);
                tempArray[indexofNew--]='%';
                System.out.println("替换第三个字符后:tempArray[indexofNew]="+tempArray[indexofNew]);
                System.out.println("替换第三个字符后:indexofNew="+indexofNew);
                
            }else{
                System.out.println("没有空格数组里面自减前:indexofNew="+indexofNew);
                tempArray[indexofNew--]= tempArray[indexofOriginal];
                System.out.println("没有空格:tempArray[indexofOriginal]="+tempArray[indexofOriginal]);
                System.out.println("没有空格赋值后:tempArray[indexofNew]="+tempArray[indexofNew]);
                System.out.println("没有空格数组里面自减后:indexofNew="+indexofNew);
            }  
            System.out.println("indexofOriginal自减前:"+indexofOriginal);
            indexofOriginal--;
            System.out.println("indexofOriginal自减后:"+indexofOriginal);
        }  
        System.out.println("替换空格后的字符串:");  
        printArray(tempArray);  
    }  
    public static void main(String[] args){  
        String str = "We are happy";  
        replaceAllBlank(str);  
    }  
}


输出:

字符串原始长度:12
字符串增加后的长度:16
数组:[C@139a55
字符:[C@1db9742
长度:12
未替换空格时的字符串:
开始打印数组
We are happy
indexofOriginal:11
indexofNew:15
tempArray[indexofOriginal]:y
没有空格数组里面自减前:indexofNew=15
没有空格:tempArray[indexofOriginal]=y
没有空格赋值后:tempArray[indexofNew]=

没有空格数组里面自减后:indexofNew=14
indexofOriginal自减前:11
indexofOriginal自减后:10
indexofOriginal:10
indexofNew:14
tempArray[indexofOriginal]:p
 

没有空格数组里面自减前:indexofNew=14
没有空格:tempArray[indexofOriginal]=p
没有空格赋值后:tempArray[indexofNew]=
indexofNew:13
tempArray[indexofOriginal]:p
没有空格数组里面自减前:indexofNew=13
没有空格:tempArray[indexofOriginal]=p
没有空格赋值后:tempArray[indexofNew]=

没有空格数组里面自减后:indexofNew=12
indexofOriginal自减前:9
indexofOriginal自减后:8
indexofOriginal:8

indexofNew:12
tempArray[indexofOriginal]:a
没有空格数组里面自减前:indexofNew=12
没有空格:tempArray[indexofOriginal]=a
没有空格赋值后:tempArray[indexofNew]=y

没有空格数组里面自减后:indexofNew=11
indexofOriginal自减前:8
indexofOriginal自减后:7
indexofOriginal:7
indexofNew:11
tempArray[indexofOriginal]:h
没有空格数组里面自减前:indexofNew=11
没有空格:tempArray[indexofOriginal]=h
没有空格赋值后:tempArray[indexofNew]=p
没有空格数组里面自减后:indexofNew=10
indexofOriginal自减前:7
indexofOriginal自减后:6
indexofOriginal:6
indexofNew:10
tempArray[indexofOriginal]:

出现空格,替换
替换第一个字符后:tempArray[indexofNew]=p
替换第一个字符后:indexofNew=9
替换第二个字符后:tempArray[indexofNew]=a
替换第二个字符后:indexofNew=8
替换第三个字符后:tempArray[indexofNew]=h
替换第三个字符后:indexofNew=7
indexofOriginal自减前:6
indexofOriginal自减后:5
indexofOriginal:5
indexofNew:7
tempArray[indexofOriginal]:e
没有空格数组里面自减前:indexofNew=7
没有空格:tempArray[indexofOriginal]=e
没有空格赋值后:tempArray[indexofNew]=
没有空格数组里面自减后:indexofNew=6
indexofOriginal自减前:5
indexofOriginal自减后:4
indexofOriginal:4
indexofNew:6
tempArray[indexofOriginal]:r
没有空格数组里面自减前:indexofNew=6
没有空格:tempArray[indexofOriginal]=r
没有空格赋值后:tempArray[indexofNew]=e

没有空格数组里面自减后:indexofNew=5
indexofOriginal自减前:4
indexofOriginal自减后:3
indexofOriginal:3
indexofNew:5
tempArray[indexofOriginal]:a
没有空格数组里面自减前:indexofNew=5
没有空格:tempArray[indexofOriginal]=a
没有空格赋值后:tempArray[indexofNew]=r
没有空格数组里面自减后:indexofNew=4
indexofOriginal自减前:3
indexofOriginal自减后:2
indexofOriginal:2
indexofNew:4
tempArray[indexofOriginal]:
出现空格,替换
替换第一个字符后:tempArray[indexofNew]=a
替换第一个字符后:indexofNew=3
替换第二个字符后:tempArray[indexofNew]=
替换第二个字符后:indexofNew=2
替换第三个字符后:tempArray[indexofNew]=e
替换第三个字符后:indexofNew=1
indexofOriginal自减前:2
indexofOriginal自减后:1
替换空格后的字符串:
开始打印数组
We%20are%20happy

 

 

 

 

© 著作权归作者所有

一贱书生
粉丝 20
博文 724
码字总数 600123
作品 0
私信 提问
[算法总结] 3 道题搞定 BAT 面试——堆栈和队列

本文首发于我的个人博客:尾尾部落 0. 基础概念 栈:后进先出(LIFO) 队列:先进先出(FIFO) 1. 栈的 java 实现 2. 队列的 java 实现 3. 用两个栈实现队列 剑指offer:用两个栈实现队列 Le...

繁著
2018/09/04
0
0
面试:用 Java 实现一个 Singleton 模式

面试系列更新后,终于迎来了我们的第一期,我们也将贴近《剑指 Offer》的题目给大家带来 Java 的讲解,个人bogo还是非常推荐《剑指 Offer》作为面试必刷的书籍的,这不,再一次把这本书分享给...

nanchen2251
2018/07/03
0
0
面试:用 Java 逆序打印链表

面试:用 Java 逆序打印链表 昨天的 Java 实现单例模式 中,我们的双重检验锁机制因为指令重排序问题而引入了 关键字,不少朋友问我,到底为啥要加 这个关键字呀,而它,到底又有什么神奇的作...

nanchen2251
2018/07/03
0
0
tomcat 环境变量路径中有空格该怎么办

本机 JAVAHOME=C:Program FilesJavajdk1.6.043 通常在服务器会引用 %JAVA_HOME%binjava 环境变量可以用特殊的字符PROGRA~1代替从而达到替换空格方便使用的目的 对带空格的路径在bat代码中用双...

追梦的南瓜
2014/08/18
0
0
飞龙的程序员书单 – 数据结构、算法

入门向 啊哈!算法 这本书真心简洁易懂,dijkstra我是看课本怎么看也看不懂,最后看这本书才懂的。真心推荐。 大话数据结构 工程向 算法 Java实现 C实现 C++实现 普林斯顿的算法课程教材,Cou...

apachecn_飞龙
2016/01/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

nproc systemd on CentOS 7

Increasing nproc for processes launched by systemd on CentOS 7 Ask Question I have successfully increased the nofile and nproc value for the local users, but I couldn't find a p......

MtrS
24分钟前
1
0
了解微信小程序下拉刷新功能

小程序提供了这个事件。 onPullDownRefresh() 监听用户下拉刷新事件。 如果要开启下拉刷新功能,要先到json配置: "enablePullDownRefresh":true 配置后下拉有反应了但是没有加载效果,在onP...

oixan__
50分钟前
2
0
springmvc java对象转json,上传下载(未完)拦截器Interceptor以及源码解析(未完待续)

package com.atguigu.my.controller;import java.util.Collection;import org.springframework.beans.factory.annotation.Autowired;import org.springframework.stereotype.Contr......

architect刘源源
今天
29
0
[日更-2019.5.24、25、26] Android系统中的Binder通信机制分析(一)--servicemanager

声明 其实对于Android系统Binder通信的机制早就有分析的想法,记得去年6、7月份Mr.Deng离职期间约定一起对其进行研究的,但因为我个人问题没能实施这个计划,留下些许遗憾... 最近,刚好在做...

Captain_小馬佩德罗
昨天
24
0
聊聊dubbo的DataStore

序 本文主要研究一下dubbo的DataStore DataStore dubbo-2.7.2/dubbo-common/src/main/java/org/apache/dubbo/common/store/DataStore.java @SPI("simple")public interface DataStore { ......

go4it
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部