【题5替换空格】
【题5替换空格】
【题目】
请实现一个函数,把字符串中的每个空格替换成“%20”
例如输入“we are happy”,则输出“we%20are%20happy”
【解法】
1.时间复杂度为O(n^2)
从头到尾扫描字符串,每次碰到空格字符时进行替换。由于把1个字符替换成了3个字符,要把字符后移2个字节。
2.时间复杂度为O(n)
(1)先遍历一次字符串,统计字符串中空格总数,计算替换后的总长度。
(2)从字符串后开始复制和替换
【实现】
package ti5;
//题目:请实现一个函数,把字符串中的每个空格替换成"%20"。例如输入“We are happy.”,
//则输出“We%20are%20happy.”。
public class ReplaceSpaces {
public String replaceSpace(StringBuffer str){
if(str == null){
System.out.println("输入错误");
return null;
}
int length = str.length();
int indexOfOriginal = length-1;
for(int i = 0;i < str.length();i++){
if(str.charAt(i)==' ')//char charAt(int index) 返回此序列中指定索引处的 char 值。
length += 2;
}
str.setLength(length);//void setLength(int newLength)设置字符序列的长度。
int indexOfNew = length - 1;
while(indexOfNew > indexOfOriginal){
if(str.charAt(indexOfOriginal) != ' '){
str.setCharAt(indexOfNew--, str.charAt(indexOfOriginal));
}else{
str.setCharAt(indexOfNew--, '0');// void setCharAt(int index, char ch)将给定索引处的字符设置为 ch。
str.setCharAt(indexOfNew--,'2' );
str.setCharAt(indexOfNew--, '%');
}
indexOfOriginal--;
}
return str.toString();
}
//测试代码
//输入为null
public void test1(){
System.out.println("Test1");
StringBuffer sBuffer = null;
String s = replaceSpace(sBuffer);
System.out.println(s);
}
//输入为空字符串
public void test2(){
System.out.println("Test2");
StringBuffer sBuffer = new StringBuffer(" ");
String s = replaceSpace(sBuffer);
System.out.println(s);
}
//输入字符串无空格
public void test3(){
System.out.println("Test3");
StringBuffer sBuffer = new StringBuffer("abc");
String s = replaceSpace(sBuffer);
System.out.println(s);
}
//输入字符串为首尾空格中间连续空格
public void test4(){
System.out.println("Test4");
StringBuffer sBuffer = new StringBuffer(" a b c ");
String s = replaceSpace(sBuffer);
System.out.println(s);
}
public static void main(String[] args) {
ReplaceSpaces rs = new ReplaceSpaces();
rs.test1();
rs.test2();
rs.test3();
rs.test4();
}
}
注:Java StringBuffer 和 StringBuilder 类
当对字符串进行修改的时候,需要使用 StringBuffer 和 StringBuilder 类。
和 String 类不同的是,StringBuffer 和 StringBuilder 类的对象能够被多次的修改,并且不产生新的未使用对象。
StringBuilder 类在 Java 5 中被提出,它和 StringBuffer 之间的最大不同在于 StringBuilder 的方法不是线程安全的(不能同步访问)。
由于 StringBuilder 相较于 StringBuffer 有速度优势,所以多数情况下建议使用 StringBuilder 类。然而在应用程序要求线程安全的情况下,则必须使用 StringBuffer 类。
Test.java 文件代码:
public class Test{
public static void main(String args[]){
StringBuffer sBuffer = new StringBuffer("菜鸟教程官网:");
sBuffer.append("www");
sBuffer.append(".runoob");
sBuffer.append(".com");
System.out.println(sBuffer);
}
}
结果:
菜鸟教程官网:www.runoob.com
方法:
public StringBuffer append(String s)将指定的字符串追加到此字符序列。
public StringBuffer reverse()将此字符序列用其反转形式取代。
public delete(int start, int end)移除此序列的子字符串中的字符。
public insert(int offset, int i)将 int 参数的字符串表示形式插入此序列中。
replace(int start, int end, String str)使用给定 String 中的字符替换此序列的子字符串中的字符。
参考:
1.《剑指offer》
2.https://www.cnblogs.com/yongh/p/9328270.html
3.http://www.runoob.com/java/java-stringbuffer.html