首页 > 其他分享 >【剑指Offer】2、替换空格

【剑指Offer】2、替换空格

时间:2023-06-28 23:24:04浏览次数:51  
标签:Offer -- 空格 str 字符串 替换 newIndex

【剑指Offer】2、替换空格

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

解题思路:
  对于这个题目,我们首先想到原来的一个空格替换为三个字符,字符串长度会增加,因此,存在以下两种不同的情况:(1)允许创建新的字符串来完成替换。(2)不允许创建新的字符串,在原地完成替换。

第一种情况比较简单。对于第二种情况,有以下两种解法:

  • 时间复杂度为O(n^2)的解法。
      从头到尾遍历字符串,当遇到空格时,后面所有的字符都后移2个。
  • 时间复杂度为O(n)的解法。
      可以先遍历一次字符串,这样可以统计出字符串中空格的总数,由此计算出替换之后字符串的长度,每替换一个空格,长度增加2,即替换之后的字符串长度为原来的长度+2*空格数目。接下来从字符串的尾部开始复制和替换,用两个指针P1和P2分别指向原始字符串和新字符串的末尾,然后向前移动P1,若指向的不是空格,则将其复制到P2位置,P2向前一步;若P1指向的是空格,则P1向前一步,P2之前插入%20,P2向前三步。这样,便可以完成替换,时间复杂度为O(n)。

举例:

编程实现(Java):

      //第一种情况:创建新的字符串实现:
      public String replaceSpace(StringBuffer str) {
    	String res="";
        for(int i=0;i<str.length();i++){
            char c=str.charAt(i);
            if(c==' ')
                res += "%20";
            else
                res += c;
        }
        return res;
     }

	//第二种情况:原地替换,O(n)的解法
      public String replaceSpace(StringBuffer str) {
        if(str==null)
            return null;
        int numOfblank = 0;//空格数量
        int len=str.length();
        for(int i=0;i<len;i++){  //计算空格数量
            if(str.charAt(i)==' ')
                numOfblank++;
        }
        str.setLength(len+2*numOfblank); //设置长度
        int oldIndex=len-1;  //两个指针
        int newIndex=(len+2*numOfblank)-1;
        
        while(oldIndex>=0 && newIndex>oldIndex){
            char c=str.charAt(oldIndex);
            if(c==' '){
                oldIndex--;
                str.setCharAt(newIndex--,'0');
                str.setCharAt(newIndex--,'2');
                str.setCharAt(newIndex--,'%');
            }else{
                str.setCharAt(newIndex,c);
                oldIndex--;
                newIndex--;
            }
        }
        return str.toString();
    }

本题有实际的现实意义,在网络编程中,如果URL参数中含有特殊字符,则可能导致服务器端无法获得正确的参数值,因此可以通过替换的方法将其转换为可以识别的字符。转换规则就是%后面加上该字符ASCII码的16进制表示,如这里的空格,ASCII码是0x20(十进制的32),所以可以替换为%20。

标签:Offer,--,空格,str,字符串,替换,newIndex
From: https://www.cnblogs.com/bujidao1128/p/17510279.html

相关文章

  • 剑指 Offer 58 - I. 翻转单词顺序
    输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。为简单起见,标点符号和普通字母一样处理。例如输入字符串"Iamastudent.",则输出"student.aamI"。示例1:输入:"theskyisblue"输出: "blueisskythe"示例2:输入:" helloworld! "输出: "worl......
  • 用CMake 替换 Makefile
    原文:https://blog.csdn.net/love131452098/article/details/116241448CMake实质上是用于生成Makefile的工具,现在越来越多开源的项目,在项目的编译框架上使用CMake替换Makefile.CMake相对于Makefile规则更加简单,重要的是CMake官方网站提供了较为友好的指南.CMake官方学习资......
  • 剑指 Offer 27. 二叉树的镜像
    请完成一个函数,输入一个二叉树,该函数输出它的镜像。例如输入:4  /  2  7 /\ /1 36 9镜像输出:4  /  7  2 /\ /9 63  1示例1:输入:root=[4,2,7,1,3,6,9]输出:[4,7,2,9,6,3,1]来源:力扣(LeetCode)链接:https://lee......
  • 【剑指Offer】51、构建乘积数组
    【剑指Offer】51、构建乘积数组题目描述:给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1]。  其中B中的元素B[i]=A[0]*A[1]...*A[i-1]*A[i+1]...*A[n-1]。不能使用除法。解题思路:首先,仔细理解题意,B[i]是A数组所有元素的乘积,但是没有A[i]项,如果没有不能使......
  • PHP 去除前后空格
    <metacharset="UTF-8"><?php$str="阅谁问群诵,水落清香浮。";echo"方括号中为原始字符串:[$str]\n";$str1=ltrim($str);echo"执行ltrim()之后的字符串:[$str1]\n";$str2=rtrim($str);echo"执行rtrim()之后的字符串:[$str2]\n"......
  • python版本的 playwright , 如何拦截请求,替换响应内容
         fromplaywright.sync_apiimportPlaywright,sync_playwrightdefrequest_interceptor(route,request):logger.info(request.url)if'api.js'inrequest.url:#替换响应内容route.fulfill(status=200,......
  • C#操作Word模板文件 替换并重新生成
    这里用到了一个操作Word的第三方开源库:DocX;这个库对于操作Word文件绝对是个好东西,更优于NPOI,而且也是不依赖于Office的;   核心代码///<summary>///Word模板替换///<para>当前适用的字段模板形如:[=Name],其中Name就是字段名</para>......
  • jeecg2-VUE-全局替换字体(鸿蒙、、、)
    html,body{font-family:-apple-system,BlinkMacSystemFont,'SegoeUI','PingFangSC',"HarmonyOSSansSC",'HiraginoSansGB','MicrosoftYaHei','HelveticaNeue',Helvetica,Arial,sans-serif......
  • 调试 Web 页面时如何替换请求响应结果
    开发jssdk项目的时候,经常会希望快速检查我们的改动在真实场景中的表现。我们不可能直接更新到生产环境,于是很多人会考虑配置代理,并替换响应内容。但代理配置起来并不方便,比如在ios/android真机上开关代理需要手动输入ip、端口。我们还有一些更便捷的方法:Chromelocalover......
  • 【pycharm】替换字符串的三种方法
    一、场景  工作中我们可能需要修改一些字符串为同一字符串,此时pycharm的一些替换功能就很好用 二、快捷键1、基于当前文件CTRL+R2、基于全局的替换 CTRL+SHIFT+R  三、替换的三种方法1、基于Cc的字符串 这种最简单,就是简单的替换某个字符串为另一个,可以......