关于程序员:算法题替换空格

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;
      }
    }
  }
};

小弟才浅，如果本篇文章有任何谬误和倡议，欢送大家留言

感激大家的点赞、珍藏

微信搜「三年游戏人」第一工夫浏览最新内容，获取一份收集多年的书籍包 以及 优质工作内推