4

要求

时间限制:1秒 空间限制:32768K

题目描述

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

解题思路

拿到题目之后,一般会首先想到从头开始扫描这个字符串,遇到空格就将后面所有的字符都向后移动两格,再插入%20。虽然这个办法可行,但是时间复杂度为O(n^2),每一个字符都会有多次移动

现在希望每个字符只移动一次。我们要用两个指针P1和P2,P1指向字符串的最后一个字符’\0′,P2指向替换了空格后的字符串尾部。每一个空格都会导致字符串增长两个字符

具体过程如下图所示

代码

class Solution
{
public:
  void replaceSpace(char *str,int length)
  {
    if(str==NULL || length<=0)
      return;
    
    int endIndexOfOriStr = -1;
    int endIndexOfNewStr = -1;
    int curIndexOfOriStr = -1;
    do
    {
      ++curIndexOfOriStr;
      
      ++endIndexOfOriStr;
      ++endIndexOfNewStr;
      if(str[curIndexOfOriStr] == ' ')
        endIndexOfNewStr += 2;
        
    }while(str[curIndexOfOriStr] != '\0');
    
    if(endIndexOfNewStr>=length)
      return;
        
    while(endIndexOfOriStr >= 0 && endIndexOfOriStr < endIndexOfNewStr)
    {
      if(str[endIndexOfOriStr]==' ')
      {
        --endIndexOfOriStr;
        str[endIndexOfNewStr--] = '0';
        str[endIndexOfNewStr--] = '2';
        str[endIndexOfNewStr--] = '%';
      }
      else
      {
        str[endIndexOfNewStr] = str[endIndexOfOriStr];
        --endIndexOfOriStr;
        --endIndexOfNewStr;
      }
    }
  }
};

由于还要搬砖,没有办法一一回复私信把学习资料发给大家。我直接整理出来放在下面,觉得有帮助的话可以下载下来用于学习
链接:https://pan.baidu.com/s/1C-9TE9ES9xrySqW7PfpjyQ 提取码:cqmd

感谢各位人才的点赞收藏关注

微信搜「三年游戏人」收获一枚有情怀的游戏人,第一时间阅读最新内容,获取优质工作内推

原文地址:http://www.cnblogs.com/gamemanthree/p/16852897.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性