题目:
请实现一个函数,把字符串中的每个空格替换成“%20”。例如输入“We are happy.”,则输出“We%20are%20happy.”。
分析:
转换的规则是在‘%’后面跟上ASCII码的两位十六进制的表示。比如空格的ASCII的码是32,即十六进制的0x20,因此空格被替换成“%20”。再比如‘#’的ASCII码为35,即十六进制的0x23,它在URL中被替换为“%23”。
有两种方式,一种是在原来的字符串上做替换,一种是创建新的字符串。这里我们假设是在原来的字符串上做替换。
解法一:从前往后替换
(a) | W | e | | a | r | e | | h | a | p | p | y | . | \0 | | | | | |
(b) | W | e | % | 2 | 0 | a | r | e | | h | a | p | p | y | . | \0 | | | |
(c) | W | e | % | 2 | 0 | a | r | e | % | 2 | 0 | h | a | p | p | y | . | \0 | |
假设字符串的长度是n。对每个空格字符,需要移动后面O(n)个字符,因此对含有O(n)个空格字符的字符串而言总的时间效率是O(n2)。
解法二:从后往前替换
(a) | W | e | | a | r | e | | h | a | p | p | y | . | \0 | | | | | |
(b) | W | e | | a | r | e | | | % | 2 | 0 | h | a | p | p | y | . | \0 | |
(c) | W | e | % | 2 | 0 | a | r | e | % | 2 | 0 | h | a | p | p | y | . | \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——名企面试官精讲典型编程题》
分享到:
相关推荐
面试题5:替换空格 面试题6:从尾到头打印链表 面试题7:重建二叉树 面试题8:二叉树的下一个节点 面试题9:用两个栈实现队列 面试题10:裴波那契数列 面试题11:旋转数组的最小数字 面试题12:矩阵中的路径 面试题...
面试题 2:替换空格(考点: 字符串) 2 面试题 3:从尾到头打印链表(考点: 链表) 2 面试题 4:重建二叉树(考点: 树) 4 面试题 5:用两个栈实现队列(考点: 栈和队列) 5 面试题 6:旋转数组的最小数字(考点:...
请实现一个函数,将一个字符串中的空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。输入:每个输入件仅包含一组测试样例。对于每组测试案例,输入一行代表要处理的字符...
java基础面试题替换空格本资源系百度网盘分享地址
示例 1:输出:"We%20are%20happy."限制:0 的长度 题解public String replaceSpace(St
#### 面试题4:替换空格 **题目概述**:将字符串中的每个空格替换为`"%20"`。 **解题思路**: 1. **创建字符数组**:首先创建一个字符数组`a`来存储原始字符串中的每个字符。 2. **构建新字符串**:使用一个新的`...
请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。 解题思路参考:...
面试题05:替换空格 +2 查找 面试题06:从尾到头打印链表 +2 栈+双数组 面试题07:重建二叉树 +2 递归 面试题09:用两个栈实现队列 +2 双栈 面试题10 - I:斐波那契数列 +2 动态规划+递归 面试题10 - II:青蛙跳台阶...
以下是一系列关于Java正则表达式的面试题及其详细解析,帮助你深入理解这一关键技能。 1. **什么是Java正则表达式?** Java正则表达式是用于文本匹配的模式,由特定的语法组成,如字符类、量词、分组和边界匹配。...
通过先统计字符串中空格数量对数组扩展,然后按照题目要求扫描赋值。 ###### 代码主体 ###### class Solution: def replaceSpace(self, s: str) -> str: s = [str(s[i]) for i in range(len(s))] count =
面试题4 替换空格 面试题5 从尾到头打印单链表 面试题6 重建二叉树 面试题7 用两个栈实现队列 2.4 算法和数据操作 面试题8 旋转数组的最小数字 面试题9 斐波那契数列 面试题10 二进制中1的个数 第3章 高质量代码 3.3...
replace()方法用于替换字符串中的字符或子串,split()方法根据分隔符将字符串拆分为子字符串数组。 trim()方法可以去除字符串的前导和尾部空格。contains()方法用来检查字符串是否包含特定字符或子串。将其他数据...
4. **GET与POST传输容量**:理论上,GET方法的最大容量受限于URL长度,一般浏览器限制在2KB到8KB之间;POST方法无此限制,但受服务器接收数据量的限制,通常在几MB左右。 5. **HTML与PHP分离**:常用的PHP模板引擎...
根据给定的文件信息,我们将逐一解析并详细阐述每一题涉及的关键知识点。 ### 1. 使用 sed 修改文件特定行的内容 - **知识点**: `sed` 命令用于流编辑,能够实现对文本数据进行非交互式的处理。题目中通过 `-i` ...
如"面试题 5:替换空格"所示,这个问题就利用了双指针技术,从字符串的末尾开始处理,有效地减少了空格并保持了字符串的正确顺序。 双指针技术是一种常见的算法技巧,它在处理数组和字符串问题时非常有用。在这道题...
### 尚硅谷_前端_面试题 #### 一、HTML+CSS 1. **Doctype作用?标准模式与兼容模式各有什么区别?** - **Doctype**:文档类型声明,用于告诉浏览器文档使用哪种HTML或XHTML规范。正确地使用DOCTYPE很重要,因为它...
在COBOL编程语言中,面试题通常会涵盖语言的基本结构、数据类型、程序控制以及数组处理等核心概念。以下是对这些题目及其答案的详细解释: 1. COBOL程序由四个主要部分组成:识别部分(IDENTIFICATION DIVISION)、...
以下是对标题和描述中提到的ASP面试题的详细解释: 1. **默认的ASP脚本语言**:在IIS(Internet Information Services)中,ASP默认使用的脚本语言是VBScript(Visual Basic Script)。VBScript是一种轻量级的、...