成都创新互联网站制作重庆分公司

字符串旋转的若干种算法(待续)-创新互联

题目描述:

对于一个字符串,和字符串中的某一位置,请设计一个算法,将包括i位置在内的左侧部分移动到右边,将右侧部分移动到左边。

站在用户的角度思考问题,与客户深入沟通,找到北海街道网站设计与北海街道网站推广的解决方案,凭借多年的经验,让设计与互联网技术结合,创造个性化、用户体验好的作品,建站类型包括:成都网站建设、网站制作、企业官网、英文网站、手机端网站、网站推广、国际域名空间、网站空间、企业邮箱。业务覆盖北海街道地区。

给定字符串A和它的长度n以及特定位置p,请返回旋转后的结果。

测试样例:

"AbcdeFgh",8,4  (为了方便起见我把两部分的起始元素用大写字母表示)
返回:"FghAbcde"

思路:

·方法一:将整个字符串左移或右移(p - 1)次

·方法二: 将要分成的前部分或后部分整体移动

·方法三:利用栈

如: 先将FGH放置到前面,变成"FghdeFGH" 。每次覆盖原有元素的时候将原来的元素存入队列中,上述步骤执行完毕后依次从队列中出队并放入对应的位置即可。

代码如下:

string rotateString(string A, int n, int p)
{
	queue que;
	int i = p;
	int tmp_i = 0;
	for (i = p; i < n; i++)
	{
		que.push(A[tmp_i]);
		A[tmp_i] = A[i];
		++tmp_i;
	}
	que.push(A[tmp_i]);
	while (!que.empty())
	{
		A[tmp_i] = que.front();
		que.pop();
		++tmp_i;
	}
	A[tmp_i] = '\0';
	return A;
}

·方法四: 三次交换

这是一种很巧妙的算法。下面举例说明:

还是用测试用例中的那段字符串 "AbcdeFgh"

根据p的位置,可以分为两部分 "Abcde" 和 "Fgh"

可以先对两个字符串分别逆序(第一次 和 第二次交换),得到  "edcbAhgF"

然后对整个字符串进行逆序(第三次) 得到 "FghAbcde"

我在方法三中用到了栈,其实是跟该方法类似的思想,

不过这个方法比我自己的方法三不知道高到哪里去了 (◎﹏◎)

·方法五: 合并、并读取

合并时,对于string对象 直接用库里已经重载好的 "+" 操作符即可

(如果要合并两个C风格的字符串,则需要用strcat函数)

例如测试用例的字符串 合并后为 "AbcdeFghAbcdeFgh"

然后再将这个合并后的字符串的第(p + 1)个元素到 (p + 1 + n)个元素按顺序放入原字符串中即可。

代码如下:

string rotateString(string A, int n, int p)
{
	queue que;
	int i = p;
	int tmp_i = 0;
	for (i = p; i < n; i++)
	{
		que.push(A[tmp_i]);
		A[tmp_i] = A[i];
		++tmp_i;
	}
	que.push(A[tmp_i]);
	while (!que.empty())
	{
		A[tmp_i] = que.front();
		que.pop();
		++tmp_i;
	}
	A[tmp_i] = '\0';
	return A;
}

创新互联www.cdcxhl.cn,专业提供香港、美国云服务器,动态BGP最优骨干路由自动选择,持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证, 机房独有T级流量清洗系统配攻击溯源,准确进行流量调度,确保服务器高可用性。佳节活动现已开启,新人活动云服务器买多久送多久。


网站名称:字符串旋转的若干种算法(待续)-创新互联
文章来源:http://cxhlcq.com/article/gjpie.html

其他资讯

在线咨询

微信咨询

电话咨询

028-86922220(工作日)

18980820575(7×24)

提交需求

返回顶部