首页 > 其他分享 >力扣 剑指offer05 替换空格

力扣 剑指offer05 替换空格

时间:2022-12-13 21:34:08浏览次数:46  
标签:offer05 right String chars 力扣 length str 空格

题目:

请实现一个函数,把字符串 s 中的每个空格替换成"%20"。

示例:

输入:s = "We are happy."
输出:"We%20are%20happy."

思路:

直接的思路就是:使用一个新的对象,复制 str,复制的过程对其判断,是空格则替换,否则直接复制。

JAVA中Stringbuffer有append( )方法:
而Stringbuffer是动态字符串数组,append( )是往动态字符串数组添加,跟“xxxx”+“yyyy”相当‘+’号。

 

//方式一:直接思路
class Solution { public String replaceSpace(String s) { if (s == null) { return null; } char[] ch=s.toCharArray(); StringBuilder sb = new StringBuilder(); for(int i=0;i<ch.length;i++){ if(ch[i]==(' ')){ sb.append("%20"); }else{ sb.append(ch[i]); } } return sb.toString(); } }

 

双指针法:

首先扩充数组到每个空格替换成"%20"之后的大小。

然后从后向前替换空格,过程如下:

i指向新长度的末尾,j指向旧长度的末尾。

为什么要从后向前填充,从前向后填充不行么?
  从前向后填充就是O(n^2)的算法了,因为每次添加元素都要将添加元素之后的所有元素向后移动。

  这么做有两个好处:

  1. 不用申请新数组。
  2. 从后向前填充元素,避免了从前向后填充元素时,每次添加元素都要将添加元素之后的所有元素向后移动的问题。
//方式二:双指针法
 class Solution {
  public String replaceSpace(String s) {
      if(s == null || s.length() == 0){
          return s;
      }
      //扩充空间,空格数量2倍//追加了空格的三倍空间
      StringBuilder str = new StringBuilder();
      for (int i = 0; i < s.length(); i++) {
          if(s.charAt(i) == ' '){
              str.append("  ");
          }
      }
      //若是没有空格直接返回
      if(str.length() == 0){
          return s;
      }
      //有空格情况 定义两个指针
      int left = s.length() - 1;//左指针:指向原始字符串最后一个位置
      s += str.toString();
      int right = s.length()-1;//右指针:指向扩展字符串的最后一个位置
      char[] chars = s.toCharArray();
      while(left>=0){
          if(chars[left] == ' '){
              chars[right--] = '0';
              chars[right--] = '2';
              chars[right] = '%';
          }else{
              chars[right] = chars[left];
          }
          left--;
          right--;
      }
    return new String(chars);
  }
}

 

标签:offer05,right,String,chars,力扣,length,str,空格
From: https://www.cnblogs.com/cjhtxdy/p/16980651.html

相关文章

  • 力扣541 反转字符串2
    题目:给定一个字符串s和一个整数k,从字符串开头算起,每计数至2k个字符,就反转这2k字符中的前k个字符。如果剩余字符少于k个,则将剩余字符全部反转。如果剩余字符......
  • 力扣-31-下一个排列
    很明显,对于一个排列而言,最后一个位置是动不了的那么就从倒数第二个位置开始用递归一点点分析错了几次之后终于自己写出来了(叉腰骄傲)voidnextPermutation(vector<int>&......
  • 力扣-49-字母异位词分组
    字母异位词就是:组成单词的字母相同,只是字母位置不同的单词没什么思路,朴素思路,先全部放到set里,然后不空就取一个出来,回溯构造所有的异位词和set中匹配public:vector<......
  • 力扣每日一题2022.12.12---1832. 判断句子是否为全字母句
    全字母句指包含英语字母表中每个字母至少一次的句子。给你一个仅由小写英文字母组成的字符串sentence,请你判断 sentence是否为全字母句。如果是,返回true;否则,返回......
  • 力扣---746. 使用最小花费爬楼梯
    给你一个整数数组cost,其中cost[i]是从楼梯第i个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。你可以选择从下标为0或下标为1的......
  • 力扣---15. 三数之和
    给你一个整数数组nums,判断是否存在三元组[nums[i],nums[j],nums[k]]满足i!=j、i!=k且j!=k,同时还满足nums[i]+nums[j]+nums[k]==0。请你返回所有和......
  • 力扣刷题(1)---两数相加
    题目:输入:nums=[2,7,11,15],target=9输出:[0,1]解释:因为nums[0]+nums[1]==9,返回[0,1]。暴力枚举publicstaticint[]twoSum(int[]nums,inttarget)......
  • 力扣182(MySQL)-查找重复的电子邮箱(简单)
    题目:编写一个SQL查询,查找 Person 表中所有重复的电子邮箱。示例: 解题思路:方法一:使用groupby按Email来分组,然后使用having选择count(id)>1的就可以得到重复的Em......
  • 力扣每日一题2022.12.12---1781. 所有子字符串美丽值之和
    一个字符串的美丽值 定义为:出现频率最高字符与出现频率最低字符的出现次数之差。   比方说,"abaacc" 的美丽值为 3-1=2 。给你一个字符串 s ,请你返回它所有......
  • 力扣852(java&python3)-山脉数组的峰顶索引(中等)
    题目:符合下列属性的数组arr称为山脉数组:arr.length>=3存在i(0<i <arr.length-1)使得:arr[0]<arr[1]<...arr[i-1]<arr[i]arr[i]>arr[i+1]>...>......