`
up2pu
  • 浏览: 223128 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

面试题4:替换空格

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


分析:
转换的规则是在‘%’后面跟上ASCII码的两位十六进制的表示。比如空格的ASCII的码是32,即十六进制的0x20,因此空格被替换成“%20”。再比如‘#’的ASCII码为35,即十六进制的0x23,它在URL中被替换为“%23”。

有两种方式,一种是在原来的字符串上做替换,一种是创建新的字符串。这里我们假设是在原来的字符串上做替换。



解法一:从前往后替换
(a)Wearehappy.\0
(b)We%20arehappy.\0
(c)We%20are%20happy.\0

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


解法二:从后往前替换
(a)Wearehappy.\0
(b)Weare%20happy.\0
(c)We%20are%20happy.\0

所有字符都只复制一次,因此这个算法的时间效率是O(n)。

代码:
/*length 为字符数组string的总容量*/
void ReplaceBlank(char string[], int length)
{
    if(string == NULL || length <= 0)
        return;
    /*originalLength 为字符串string的实际长度*/
    int originalLength = 0;
    int numberOfBlank = 0;
    while(string[i] != '\0')
    {
        ++ originalLength;
        if(string[i] == ' ')
            ++ numberOfBlank;
        ++ i;
    }
    /*newLength 为把空格替换成‘%20’之后的长度*/
    int newLength = originalLength + numberOfBlank * 2;
    if(newLength > length)
        return;
    int indexOfOriginal = originalLength;
    int indexOfNew = newLength;
    while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal)
    {
        if(string[indexOfOriginal] == ' ')
        {
            string[indexOfNew --] = '0';
            string[indexOfNew --] = '2';
            string[indexOfNew --] = '%';
        }
        else
        {
            string[indexOfNew --] = string[indexOfOriginal];
        }
        -- indexOfOriginal;
    }
}


package net.ecoolsoft.question;

public class WhiteSpaceReplace {
	/**
	 * 将字符数组中的空格替换成“%20”
	 * 模拟C++,认为数组长度足够
	 * @param input
	 */
	public void replaceWhiteSpace(char[] input) {
		if(input == null || input.length == 0) {
			return;
		}
		//遍历数组,查找空格个数
		int num = 0;
		int i = 0;
		for(i=0; i<input.length && input[i] != '\u0000'; i++) {
			if(input[i] == ' ') {
				++num;
			}
		}
		//两个指针,分别指向原字符数组末尾和新字符数组末尾
		int indexEnd = i-1;
		int indexNewEnd = indexEnd + num * 2;
		if(input.length < indexNewEnd+1) {
			return;
		}
		for(int j=indexEnd; j>=0; j--) {
			if(input[j] != ' ') {
				input[indexNewEnd--] = input[j];
			} else {
				input[indexNewEnd--] = '0';
				input[indexNewEnd--] = '2';
				input[indexNewEnd--] = '%';
			}
		}
		output(input);
	}
	
	/**
	 * 输出字符数组
	 * @param input
	 */
	public void output(char[] input) {
		System.out.println(input);	
	}
}


package net.ecoolsoft.question;

import junit.framework.Assert;

import org.junit.Test;

public class WhiteSpaceReplaceTest {
	
	@Test
	public void replaceWhiteSpaceTest() {
		String str = "Hello World, OK!";
		char[] result = replace(str);
		char[] expected = "Hello%20World,%20OK!".toCharArray();
		Assert.assertEquals(String.valueOf(expected).trim(), String.valueOf(result).trim());
	}
	
	@Test
	public void eplaceWhiteSpaceStartTest() {
		String str = " Hello World, OK! ";
		char[] result = replace(str);
		char[] expected = "%20Hello%20World,%20OK!%20".toCharArray();
		Assert.assertEquals(String.valueOf(expected).trim(), String.valueOf(result).trim());
	}
	
	@Test
	public void eplaceWhiteSpaceAllSpaceTest() {
		String str = "     ";
		char[] result = replace(str);
		char[] expected = "%20%20%20%20%20".toCharArray();
		Assert.assertEquals(String.valueOf(expected).trim(), String.valueOf(result).trim());
	}
	
	@Test
	public void eplaceWhiteSpaceNotEnough() {
		String str = "Hello World, OK!";
		char[] input = str.toCharArray();
		WhiteSpaceReplace wsr = new WhiteSpaceReplace();
		wsr.replaceWhiteSpace(input);
		char[] expected = input;
		Assert.assertEquals(expected, input);
	}
	
	@Test
	public void eplaceWhiteSpaceNullTest() {
		String str = null;
		char[] result = replace(str);
		char[] expected = null;
		Assert.assertEquals(expected, result);
	}
	
	private char[] replace(String str) {
		char[] input = null;
		if(str != null) {
			input = new char[str.length()*3];
			for(int i=0; i<str.length(); i++) {
				input[i] = str.charAt(i);
			}
		}
		WhiteSpaceReplace wsr = new WhiteSpaceReplace();
		wsr.replaceWhiteSpace(input);
		return input;
	}
}


参考资料:《剑指Offer——名企面试官精讲典型编程题》
分享到:
评论

相关推荐

    面试高频算法题总结-剑指Offer题解

    面试题5:替换空格 面试题6:从尾到头打印链表 面试题7:重建二叉树 面试题8:二叉树的下一个节点 面试题9:用两个栈实现队列 面试题10:裴波那契数列 面试题11:旋转数组的最小数字 面试题12:矩阵中的路径 面试题...

    剑指offer(java版67题)

    面试题 2:替换空格(考点: 字符串) 2 面试题 3:从尾到头打印链表(考点: 链表) 2 面试题 4:重建二叉树(考点: 树) 4 面试题 5:用两个栈实现队列(考点: 栈和队列) 5 面试题 6:旋转数组的最小数字(考点:...

    剑指offer面试题5-替换空格C语言.cpp

    请实现一个函数,将一个字符串中的空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。输入:每个输入件仅包含一组测试样例。对于每组测试案例,输入一行代表要处理的字符...

    java基础面试题替换空格

    java基础面试题替换空格本资源系百度网盘分享地址

    vfmh#JAVA2020#面试题05. 替换空格1

    示例 1:输出:"We%20are%20happy."限制:0 的长度 题解public String replaceSpace(St

    剑指offer java编程

    #### 面试题4:替换空格 **题目概述**:将字符串中的每个空格替换为`"%20"`。 **解题思路**: 1. **创建字符数组**:首先创建一个字符数组`a`来存储原始字符串中的每个字符。 2. **构建新字符串**:使用一个新的`...

    【剑指offer】面试题5-替换空格-完整的可执行代码(Java)

    请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。 解题思路参考:...

    leetcode迷宫问题-LeetCode:LeetCode刷题之剑指offer系列

    面试题05:替换空格 +2 查找 面试题06:从尾到头打印链表 +2 栈+双数组 面试题07:重建二叉树 +2 递归 面试题09:用两个栈实现队列 +2 双栈 面试题10 - I:斐波那契数列 +2 动态规划+递归 面试题10 - II:青蛙跳台阶...

    Java正则表达式面试题解析:探索复杂匹配规则与高效字符串处理

    以下是一系列关于Java正则表达式的面试题及其详细解析,帮助你深入理解这一关键技能。 1. **什么是Java正则表达式?** Java正则表达式是用于文本匹配的模式,由特定的语法组成,如字符类、量词、分组和边界匹配。...

    《剑指Offer》刷题笔记——面试题05. 替换空格

    通过先统计字符串中空格数量对数组扩展,然后按照题目要求扫描赋值。 ###### 代码主体 ###### class Solution: def replaceSpace(self, s: str) -&gt; str: s = [str(s[i]) for i in range(len(s))] count =

    剑指offer之python实现

    面试题4 替换空格 面试题5 从尾到头打印单链表 面试题6 重建二叉树 面试题7 用两个栈实现队列 2.4 算法和数据操作 面试题8 旋转数组的最小数字 面试题9 斐波那契数列 面试题10 二进制中1的个数 第3章 高质量代码 3.3...

    面试题:Java String类常见操作和用法

    replace()方法用于替换字符串中的字符或子串,split()方法根据分隔符将字符串拆分为子字符串数组。 trim()方法可以去除字符串的前导和尾部空格。contains()方法用来检查字符串是否包含特定字符或子串。将其他数据...

    贪玩php面试题.docx

    4. **GET与POST传输容量**:理论上,GET方法的最大容量受限于URL长度,一般浏览器限制在2KB到8KB之间;POST方法无此限制,但受服务器接收数据量的限制,通常在几MB左右。 5. **HTML与PHP分离**:常用的PHP模板引擎...

    25道shell面试题

    根据给定的文件信息,我们将逐一解析并详细阐述每一题涉及的关键知识点。 ### 1. 使用 sed 修改文件特定行的内容 - **知识点**: `sed` 命令用于流编辑,能够实现对文本数据进行非交互式的处理。题目中通过 `-i` ...

    数组与字符串 python(csdn)————程序.pdf

    如"面试题 5:替换空格"所示,这个问题就利用了双指针技术,从字符串的末尾开始处理,有效地减少了空格并保持了字符串的正确顺序。 双指针技术是一种常见的算法技巧,它在处理数组和字符串问题时非常有用。在这道题...

    尚硅谷_前端_面试题

    ### 尚硅谷_前端_面试题 #### 一、HTML+CSS 1. **Doctype作用?标准模式与兼容模式各有什么区别?** - **Doctype**:文档类型声明,用于告诉浏览器文档使用哪种HTML或XHTML规范。正确地使用DOCTYPE很重要,因为它...

    Cobol面试题---同济论坛里粘贴下来的Word版本

    在COBOL编程语言中,面试题通常会涵盖语言的基本结构、数据类型、程序控制以及数组处理等核心概念。以下是对这些题目及其答案的详细解释: 1. COBOL程序由四个主要部分组成:识别部分(IDENTIFICATION DIVISION)、...

    ASP程序员面试题(比较基础)

    以下是对标题和描述中提到的ASP面试题的详细解释: 1. **默认的ASP脚本语言**:在IIS(Internet Information Services)中,ASP默认使用的脚本语言是VBScript(Visual Basic Script)。VBScript是一种轻量级的、...

Global site tag (gtag.js) - Google Analytics