首页 > 编程语言 > 详细

【算法】字符串左移函数的O(n)解法

时间:2015-04-13 14:43:50      阅读:215      评论:0      收藏:0      [点我收藏+]


例如,字符串 abcdef ,若要让def翻转到abc的前头,只要按照下述3个步骤操作即可:

  1. 首先将原字符串分为两个部分,即X:abc,Y:def;
  2. 将X反转,X->X^T,即得:abc->cba;将Y反转,Y->Y^T,即得:def->fed。
  3. 反转上述步骤得到的结果字符串X^TY^T,即反转字符串cbafed的两部分(cba和fed)给予反转,cbafed得到defabc,形式化表示为(X^TY^T)^T=YX,这就实现了整个反转。 
这就是把字符串分为两个部分,先各自反转再整体反转的方法,时间复杂度为O(n),空间复杂度为O(1),达到了题目的要求。


代码:
#include <STDIO.H>

void reverse(char *str,int l,int r)    //对字符串的l-r实现翻转
{
	while(l<r)
	{
		char temp=str[l];
		str[l++]=str[r];
		str[r--]=temp;
	}
}

void LeftRotateString(char *str,int r,int x)   //三段翻转
{
	x%=r;  
	reverse(str,0,x-1);           //因为下标是从0开始,所以是x-1;
	reverse(str,x,r);
	reverse(str,0,r);
}


int main()
{
	char ar[]="abcdefg";
	LeftRotateString(ar,6,1);
	puts(ar);
	return 0;
}


技术分享

【算法】字符串左移函数的O(n)解法

原文:http://blog.csdn.net/a781558066/article/details/45024327

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!