字符串元素重排高效算法集合

         以下各题均有时间复杂度为O(n*n)或以空间换取时间使得时间空间复杂度为O(n)的算法，在此均不考虑。

问题一、字符串移动

      字符串为*号和26个字母的任意组合，把*号都移动到最左侧，把字母移到最右侧并保持相对顺序不变，要求时间和空间复杂度最小 。如“afdg**fa**hjfkdsl”变换成“****afdgfahjfkdsl”

         此题前后字符串的长度不变，由于最终一边只有‘*’，另一边为字母，可以设置两个指针fast和slow，当str[fast]不为‘*’时，赋值给str[slow]；否则直接移到下一个。不需额外空间，只需扫描一次字符串，时间复杂度为O(n)，空间复杂度为O(1)。

#include<iostream>
using namespace std;

const int MAXN=100;

void removeString(char *pStr)
{
	if(NULL==pStr)
		return ;
	int fast,slow;
	fast=slow=strlen(pStr)-1;
	while(fast>=0)
	{
		if(pStr[fast]!='*')
		{
			pStr[slow]=pStr[fast];
			--slow;
		}
		--fast;
	}

	while(slow>=0)
	{
		pStr[slow]='*';
		--slow;
	}
}

int main()
{
	char str[MAXN];
	while(scanf("%s",str)!=EOF)
	{
		printf("%s\n",str);
		removeString(str);
		printf("%s\n",str);
	}
	return 0;
}

问题二、字符串连续‘*’合并

       字符串为‘*‘和字母的任意组合，把多个连续‘*‘合成一个，要求时间复杂度O(n)和空间复杂度O(1) 。如“afh***hd**”变换成“afh*hd*”.

       这是2014阿里武汉二面写代码的题，当时我先扫描一遍统计变换后字符串的长度，然后从后往前依次处理，达到了题目要求，共两次扫描字符串，但面试官说有更好的做法，当时他也没让我再想，放我过了。

       后来之后感觉可以一次扫描字符串，将直接从前往后处理，同样设置两个指针fast和slow，当str[fast]为连续‘*’中的非第一个时，fast后移，slow不变；否则str[fast]赋值给str[slow],然后二者都后移一个位置。

#include<iostream>
#include<cstring>
using namespace std;

const int MAXN=100;

int removeBlack(char *pStr)
{
	if(NULL==pStr)
		return -1;
	int len=strlen(pStr);
	int fast,slow;
	for(fast=1,slow=1;fast<len;fast++)
	{
		if(pStr[fast]==pStr[fast-1]&&pStr[fast]=='*')
			continue;
		else if(fast!=slow)pStr[slow++]=pStr[fast];
		else slow++;
	}
	pStr[slow]='\0';
	return slow;
}

int main()
{
	char str[MAXN];
	while(scanf("%s",str)!=EOF)
	{
		printf("%s\n",str);
		removeBlack(str);
		printf("%s\n",str);
	}
	system("pause");
	return 0;
}

问题三、字符串‘*‘变’%20‘

        字符串为‘*‘和字母的任意组合，把‘*‘变换成‘%20‘，要求时间、空间复杂度尽可能小 。如“*hjaf**hjafj*”变换成“%20hjaf%20%20hjafj%20”.

       先扫描一遍统计’*‘个数得出变换后字符串的长度，然后从后往前依次处理，共两次扫描字符串，时间复杂度为O(n)，空间复杂度为O(1)。由于字符串长度增加了，从后往前处理是为了避免覆盖原来的字符串中的元素，这点很重要。

#include<iostream>
#include<cstring>
using namespace std;

const int MAXN=100;

int replace(char *pStr)
{
	if(NULL==pStr)
		return -1;
	int i=0,j,num=0,len=strlen(pStr);
	while(pStr[i]!='\0')
	{
		if(pStr[i]=='*')
			++num;
		++i;
	}

	i=len-1;
	j=len+2*num-1;
	while(i>=0)
	{
		if(pStr[i]=='*')
		{
			pStr[j]='0';
			--j;
			pStr[j]='2';
			--j;
			pStr[j]='%';
			--j;
		}
		else 
		{
			pStr[j]=pStr[i];
			--j;
		}
		--i;
	}
	pStr[len+2*num]='\0';
	return len+2*num-1;;
}

int main()
{
	char str[MAXN];
	while(scanf("%s",str)!=EOF)
	{
		printf("%s\n",str);
		replace(str);
		printf("%s\n",str);
	}
	system("pause");
	return 0;
}

总结

    此类问题都可以在时间复杂度为O(n)，空间复杂度为O(1)解决。但可以做到常量级的优化，减少扫描次数提高效率。注意字符串长度的变化，不变+变短可以直接从前往后处理，变长则需要从后往前处理避免覆盖原来的字符串中的元素。

字符串元素重排高效算法集合,布布扣,bubuko.com

字符串元素重排高效算法集合

原文：http://blog.csdn.net/xiaofengcanyuexj/article/details/28168225