算法题--替换空格
2022/11/4 3:25:01
本文主要是介绍算法题--替换空格,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
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; } } } };
这篇关于算法题--替换空格的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署