做淘宝券推广的网站有哪些,国外网站开发技术现状,网站建设原码,微信制作企业网站参考链接
letcode官网题目地址
题目要求#xff1a;
请实现一个函数#xff0c;把字符串 s 中的每个空格替换成%20。示例 1#xff1a; 输入#xff1a;s We are happy. 输出#xff1a;We%20are%20happy. 来源#xff1a;力扣
请实现一个函数把字符串 s 中的每个空格替换成%20。示例 1 输入s We are happy. 输出We%20are%20happy. 来源力扣LeetCode 链接https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 解决思路
时间复杂度为O(n^2)
如果在先前的字符串上进行替换就很有可能会覆盖修改该字符串后面的内存。如果创建新的字符串并在新的字符串上进行替换需要分配足够多的内存时间复杂度为O(n^2)的解法不足以拿到offer最low的做法是从头开始扫描字符串遇到空格就进行替换将1个空格替换成%20那么会造成数据的多次移动时间复杂度很高但是占据的内存很小在原有的字符串上进行更改。
时间复杂度是O(n)
每次替换空格长度会增加2位因此替换之后的长度等于先前的长度加上2*空格的数目设置两个指针因为从0开始读取字符串old指针第一个指针指向先前旧的字符串的长度 - 1 的位置第二个指针new指向新的字符串 的长度减一的位置。如果old指针指向的位置是空格的话new指针移动三次添加”%20“然后old移动一次如果old指针指向的位置不是空格的话new和old指针分别移动一次实现数据的拷贝相对于第一种方式减少了对相同数据的拷贝次数
代码 std::string replaceSpace(std::string s) {int old_length s.length();if (old_length 0){return s;}int count 0;for (int i 0; i old_length; i) {if (s[i] ){count;}}int new_length old_length 2*count - 1;int original_index old_length - 1;int new_index new_length;s std::string(2*count, );while (original_index 0 new_index original_index){if (s[original_index] ){s[new_index--] 0;s[new_index--] 2;s[new_index--] %;} else{s[new_index--] s[original_index];}--original_index;}return s;}
