【剑指offer之题目1510：替换空格】九度OJ-1510-替换空格

本文主要是介绍【剑指offer之题目1510：替换空格】九度OJ-1510-替换空格，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【链接】：九度OJ-1510-替换空格
【题目】：
题目1510：替换空格
时间限制：1 秒内存限制：128 兆特殊判题：否提交：11482解决：2934
题目描述：
请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
输入：
每个输入文件仅包含一组测试样例。
对于每组测试案例，输入一行代表要处理的字符串。
输出：
对应每个测试案例，出经过处理后的字符串。
样例输入：
We Are Happy
样例输出：
We%20Are%20Happy
【思路】：
这里写图片描述
时间复杂度伟O（n）的解法，搞定offer就靠它了
我们可以先遍历一次字符串，这样就能统计字符串中空格的总数，并可以由此
计算出替换之后字符串的总长度，每次替换一个空格，长度增加2，因此替换后总
长度为=原来长度+2*空格个数，我们还是以例子为例，“we are happy.”字符串总长度
14，包括结尾符号（’\0’）里面两个空格，因此替换之后长度为18
我们从字符串的后面开始复制和替换，首先准备两指针，P1和P2， P1指向原始字符串的末尾
，而P2指向替换之后的字符串的末尾（如图2.4 a）接下来我们向前移动指针P1，逐个把它指向的字符复制到P2
指向的位置，直到碰到第一个空格为止，此时字符串包含（如图2.4b）灰色背景的区域
是做了字符拷贝的区域。碰到第一个空格之后，把 P!向前移动1格，在P2之前插入字符串
“%20”，由于插入长度为3，同时把P2向前移动3格（如图2.4c）
接着向前复制，直到碰到第二个空格（如图2.4d）和上一次一样，我们把P1向前移动
1格，并把P2向前移动3格插入“20%”（如图2.4e），此时P1和P2指向同一位置
，表明所有空格都已经替换完毕。
从上面的分析我们可以知道，所有的字符都只复制一次，因此这个算法的时间效率为
O（n）。
在面试的过程中，我们也可以和前面的分析一样画一两个示意图解释自己的思路
，这样既能帮助我们理清思路，也能我们和面试官的交流更加高效，在面试官肯定了我们的思路之后，
我们便可以写出代码了。
【代码】：

#pragma comment(linker,"/STACK:102400000,102400000")
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <set>
#include <stack>
#include <math.h>
#include <map>
#include <queue>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 1e6+10;
const int maxm = 55;
const LL MOD = 999999997;
int dir4[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};
int dir8[8][2]= {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
inline LL read(){int  c=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}return c*f;
}
char str[maxn];
void replace_blank(char str[],int length)
{if(str == NULL && length <=0) return;int origin_len   = 0;int num_of_blank = 0;int i=0;///get the lengthwhile(str[i]!='\0'){++origin_len;if(str[i] == ' ') ++num_of_blank;++i;}int new_length = origin_len + 2*num_of_blank;// if(new_length > length) return ;int index_of_origin = origin_len;int index_of_new    = new_length;while(index_of_origin >=0 && index_of_origin<index_of_new){if(str[index_of_origin] == ' '){str[index_of_new--] ='0';str[index_of_new--] ='2';str[index_of_new--] ='%';}else {str[index_of_new--] = str[index_of_origin];}--index_of_origin;}printf("%s\n",str);
}
int main()
{//freopen("in.txt","r",stdin);while(gets(str)){replace_blank(str,strlen(str));}return 0;
}/**************************************************************Problem: 1510User: herongweiLanguage: C++Result: AcceptedTime:10 msMemory:2496 kb
****************************************************************/

牛客网版本：


class Solution {
public:void replaceSpace(char *str,int length) {if(str==NULL || length<0) return ;int num_of_blank=0;int old_of_len=length;int new_of_len=0;for(int i=0; i<old_of_len; ++i){if(str[i]==' ') ++num_of_blank;}new_of_len=old_of_len+(num_of_blank)*2;int index_of_old=old_of_len;int index_of_new=new_of_len;while(index_of_old>=0&&index_of_new>index_of_old){if(str[index_of_old]==' '){str[index_of_new--]='0';str[index_of_new--]='2';str[index_of_new--]='%';}else {str[index_of_new--]=str[index_of_old];}--index_of_old;}}
};