字符串系列② -- 替换空格

举报
十八岁讨厌编程 发表于 2022/08/05 23:47:33 2022/08/05
【摘要】 目录 题目思路代码实现方法二的实现StringBuffer的实现方法 数组填充类算法问题的思考 题目 此题对应LeetCode中剑指offer05 请实现一个函数,把字符串 s...

题目

此题对应LeetCode剑指offer05

请实现一个函数,把字符串 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

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。