首页 / C++ / 剑指offer2:C++实现的替换空格
剑指offer2:C++实现的替换空格
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了剑指offer2:C++实现的替换空格,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2120字,纯文字阅读大概需要4分钟。
内容图文
![剑指offer2:C++实现的替换空格](/upload/InfoBanner/zyjiaocheng/715/ceb54434264340fead407e78e3bc0b7e.jpg)
1. 题目描述
请实现一个函数,将一个字符串中的空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
2. 思路和方法:
2.1 不建议的方法:
简单暴力解法,从头到尾遍历字符串,碰到空格,首先将后面的所有字符串往后移动2个字符,才能空出3个字符位子插入字符“%20”,对于一个长度为n的字符串,对每个空格,需要移动后面O(n)个字符,因此包含n个空格的字符串,总的时间复杂度为O(n*n)。
2.2 建议使用的方法:
中心思想:统计字符串中空格的个数,计算扩容字符串后的长度,然后执行复制和替换。我们从后往前开始替换,首先遍历一遍字符串,统计出空格的个数,并由此能够计算出替换之后的字符串的长度。接着再次从后往前遍历字符串,同时设置两个指针P1和P2,P1指向原始字符串末尾,P2指向替换之后的字符串末尾。我们向前移动P1,逐个把它指向的字符复制到P2指向的位置,直到碰到第一个空格为止。然后把P1向前移动一格,在P2之前插入字符串“%20”,同时P2向前移动3格。重复此过程,直到所有的空格都已替换完。这种做法的时间复杂度为O(n)。
3. C++实现
#include<iostream> /* 将字符串中的空格替换成%20 */ class Solution { public: void replaceSpace(char *str, int length) { if (str == NULL && length <= 0){ return; } /*original_length为字符串str的实际长度*/ int original_length = 0; //原始长度 int number_blank = 0; //空格数 int i=0; while (str[i++] != '\0'){ //遍历字符串 ++original_length; //长度+1 if (str[i] == ' '){ ++number_blank; //遇到空格+1 } } /*new_length为把空格替换成'%20'之后的长度*/ int new_length = original_length + 2 * number_blank; int index_original = original_length; //原始字符串末尾索引值 int index_new = new_length; //计算长度后的字符串末尾索引值 /*index_original指针开始向前移动,如果遇到空格,替换成'%20',否则进行复制操作*/ while (index_original >= 0 && index_new > index_original){ if (str[index_original] == ' '){ str[index_new--] = '0'; str[index_new--] = '2'; str[index_new--] = '%'; } else{ str[index_new--] = str[index_original]; } --index_original; } } }; int main(){ Solution a; char s[] = "hello world! "; printf("%s\n", s); a.replaceSpace(s, 13); printf("?%s? ", s); getchar(); return 0; }
参考资料
https://blog.csdn.net/YF_Li123/article/details/70332267
https://blog.csdn.net/yeqiang19910412/article/details/81567403
内容总结
以上是互联网集市为您收集整理的剑指offer2:C++实现的替换空格全部内容,希望文章能够帮你解决剑指offer2:C++实现的替换空格所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。