共计 991 个字符,预计需要花费 3 分钟才能阅读完成。
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;
}
}
}
};
小弟才浅,如果本篇文章有任何谬误和倡议,欢送大家留言
感激大家的点赞、珍藏
微信搜「三年游戏人」第一工夫浏览最新内容,获取一份收集多年的书籍包 以及 优质工作内推
正文完