字符串系列② -- 替换空格
【摘要】
目录
题目思路代码实现方法二的实现StringBuffer的实现方法
数组填充类算法问题的思考
题目
此题对应LeetCode中剑指offer05
请实现一个函数,把字符串 s...
题目
请实现一个函数,把字符串 s 中的每个空格替换成"%20"。
示例 1:
输入:s = “We are happy.”
输出:“We%20are%20happy.”
思路
在拿到字符串后,先计算空格数,再根据要替换的字符对数组进行扩容,使用双指针法,此后有两种处理方法:
方法一:创建一个新的扩容好的数组,一个指针(A指针)指着新数组的头部,另外一个指针(B指针)指着原数组的首部,然后依次添加,B指针依次向前,当指到空格时,A指针添加替换物。
方法二(更高效):只创建一个数组,两个指针同时对这个数组作用,在讲s添加到数组中去后,A指针指向原s的尾端,而B指针指向数组的尾端,采取从尾部向头部添加的方式。添加过程同方法一!
为什么从尾部开始添加?:你可以假设从头部开始添加,会发现添加指针可能会比原内容指针跑得快,这就导致了有的原内容还没有被添加就被覆盖了,导致这部分原数据丢失!而从尾部添加,添加指针永远比原内容指针跑得慢,最多同步,不可能出现超过的情况,这就保证了数据的安全性。
代码实现
方法二的实现
public String solution1(String s){
//先计算空格,创建计数器
int count = 0;
for(char kongge:s.toCharArray()){
if(kongge == ' '){
count++;
}
}
//根据空格计算新建数组的长度
char[] ss = new char[s.length()+count*2];
//将原数组放入
for(int i = 0;i < s.length();i++){
ss[i] = s.charAt(i);
}
//建立指针
int add = ss.length - 1;
//添加原内容指针与for循环合并
for(int content = s.length() - 1;content >= 0;content--){
if(ss[content] == ' '){
ss[add] = '0';
ss[add-1] = '2';
ss[add-2] = '%';
add-=3;
}else{
ss[add] = ss[content];
add--;
}
}
return new String(ss);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
StringBuffer的实现方法
public static String replaceSpace(StringBuffer str) {
if (str == null) {
return null;
}
//选用 StringBuilder 单线程使用,比较快,选不选都行
StringBuilder sb = new StringBuilder();
//使用 sb 逐个复制 str ,碰到空格则替换,否则直接复制
for (int i = 0; i < str.length(); i++) {
//str.charAt(i) 为 char 类型,为了比较需要将其转为和 " " 相同的字符串类型
//if (" ".equals(String.valueOf(str.charAt(i)))){
if (s.charAt(i) == ' ') {
sb.append("%20");
} else {
sb.append(str.charAt(i));
}
}
return sb.toString();
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
数组填充类算法问题的思考
其实很多数组填充类的问题,都可以先预先给数组扩容带填充后的大小,然后在从后向前进行操作。
原因如下:
- 不同再次创建新的数组,可以直接在扩容的数组上进行操作
- 若从前向后填充数组,会对原数组数据覆盖而丢失,而从后往前覆盖则完美的避免了这个问题(未添加部分永远不会被提前覆盖)!
文章来源: blog.csdn.net,作者:十八岁讨厌编程,版权归原作者所有,如需转载,请联系作者。
原文链接:blog.csdn.net/zyb18507175502/article/details/122278310
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)