[九度 1510 剑指offer]—替换空格 数组插入逆向移动

本文主要是介绍[九度 1510 剑指offer]—替换空格 数组插入逆向移动，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目1510：替换空格

题目：http://ac.jobdu.com/problem.php?pid=1510

题目描述：

请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

输入：

每个输入文件仅包含一组测试样例。
对于每组测试案例，输入一行代表要处理的字符串。

输出：

对应每个测试案例，出经过处理后的字符串。

样例输入：

We Are Happy

样例输出：

We%20Are%20Happy

    这个题和LeetCode上的一个题一样。关键在于向字符串数组插入时，需要移动后序元素的问题。如果从前往后插入，则每次后序元素都需要移动，开销O(N^2)，这种问题显然应该逆向插入，算好需要移动的位置，一次移动到位。为了计算正确的位置，显然需要先遍历一遍数组，查看有多少空格。

     

#include<iostream>
#include<string>
using namespace std;void replace(string &str)
{int i,j,count=0;int n=str.size();for(i=0;i<n;i++){if(str[i]==' ')count++;}//扩展str的长度str=str+string(count*2,' ');//逆向遍历j=n-1;for(i=n-1;i>=0;i--){if(str[i]==' '){//移动for(j;j>i;j--)str[j+count*2]=str[j];str[j]='%';str[j+1]='2';str[j+2]='0';j--;count--;}if(count==0)break;}  
}int main()
{string str;getline(cin,str);replace(str);cout<<str<<endl;   
}

这篇关于[九度 1510 剑指offer]—替换空格 数组插入逆向移动的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---