`
384444165
  • 浏览: 258860 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

[编程珠玑题目] 一维向量左旋转

阅读更多

最近太忙了买了编程珠玑之后就翻过2页,今天正好@neiddy 问我看里面的题目,就花了点时间看看做一下。自己思考后跟书上讲的第二种有效方法很想,考虑后就在想执行效率,所以写了代码来看一下,最后需要做 length/rotatelength⌉ or +1(就不写那么复杂了)此swap,每次swap做routateLength次交换,因此时间复杂度是O(n),空间复杂度O(1)。其实第一种实现思路较为直观,开始思考了这样的替换,觉着复杂没有深入思考,其实也是很好的方法,时间复杂度低。看到第三种方法的时候就觉着自己弱爆了,好吧,说题目吧,我实现了第二种。怀着羡慕嫉妒恨写了第三种漂亮的算法。

说明:

 

因为每个循环交换需要用到一次temp,后两个算法每个循环只有2个值,但是杂技算法那这个每个循环可能有很多,因此减少了对temp的赋值次数,带来一定的性能提升(这里说的如果每个部分都是大数据的话 (纠正这个错误,实际的实现中肯定只会做地址的赋值,即便是大数据不可能做关于内存块的移动,因此这部分虽然减少了交换次数,但是由于下面提到的取余指令问题依然造成了性能的衰减,但是不会很明显,也不是在算法分析中需要太关注的环节,但是如果必须做内存块交换或外存空间的话需要谨慎选择算法,并尽量考虑使用其他的方法解决这个限制),如果只是交换char的话取余数并赋值为四条指令,远比加减和赋值多,因此性能反而得不到提升,这都属于细节了,如果真的是用大数据的话就要考虑牺牲一定的可读性了)。

 

题目:(原书11页问题B)

将一个n元一维向量向左旋转i个为孩子。例如,当n=8且i=3时,向量abcdefgh左旋转为defghabc。简单的代码使用一个n元的中间向量在n步完成该工作。你能否使用数十个额外字节的存储空间,在正比于n的时间内完成向量的旋转?

 

 

by me,第二种实现方法

 

/*
 * vectorrotate.c
 *
 *  Created on: Dec 17, 2012
 *      Author: Jason_wbw
 */

#include <stdio.h>
#include <string.h>

/**
 * 交换vector中的两部分:
 * 交换前的四部分[firstBegin, firstBegin+swapLength-1],
 *              [firstBegin+swapLength, secondBegin-1],
 *              [secondBegin, secondBegin+swapLength-1],
 *              [secondBegin+swapLength, end]
 * 交换内容为第一和第三部分,交换后如下
 *              [secondBegin, secondBegin+swapLength-1],
 *              [firstBegin+swapLength, secondBegin-1],
 *              [firstBegin, firstBegin+swapLength-1],
 *              [secondBegin+swapLength, end]
 */
void swapVector(char* vector, int firstBegin, int secondBegin, int swapLength){
	char temp;
	int i;
	for(i=0; i<swapLength;i++){
		temp = vector[firstBegin+i];
		vector[firstBegin+i] = vector[secondBegin+i];
		vector[secondBegin+i] = temp;
	}
}

/**
 * 向量的左旋转
 * 算法如下:
 * 按照position将vector分成ab两部分,最终需要变成ba。
 * [1]若a长度小于b,将b分为b1b2,其中b2长度等于a。交换a和b2变为b2b1a,再递归返回到判断修改b2b1为b1b2。
 * [2]若a长度大于b,将a分为a1a2,其中a1长度等于b。交换a2和b变为ba2a1,再递归返回到判断修改a2a1为a1a2。
 * [3]若a长度等于b,交换a、b,算法结束。
 *
 * 'vector'   要旋转的字符串数组
 * 'position' 旋转几个位置
 *
 * return 0 表示position越界;1 表示成功左旋转
 */
int route(char* vector, int position){
	if(position<=0 || position>=strlen(vector)){
		return 0;
	}

	int firstPosition = 0;                          //算法判断情况[1]中a的首地址
	int headerLength = position;                    //算法判断情况[1]中a的长度
	int enderLength = strlen(vector)-position;      //算法判断情况[1]中b的长度

	while(headerLength!=enderLength){
		if(headerLength<enderLength){            //算法判断情况[1]
			swapVector(vector, firstPosition, firstPosition+enderLength, headerLength);
			enderLength -= headerLength;
		}else{                                   //算法判断情况[2]
			swapVector(vector, firstPosition, firstPosition+headerLength, enderLength);
			firstPosition = enderLength;
			headerLength -= enderLength;
		}
	}

	//算法判断情况[3]
	swapVector(vector, firstPosition, firstPosition+headerLength, headerLength);

	return 1;
}

/**
 * test
 */
int main(){

	char vector[8] = {'a','b','c','d','e','f','g','h'};
	printf("before rotate : %s\n",vector);
	int result = route(vector,3);
	if(result==1){
		printf("after rotate : %s",vector);
	}
	return 0;
}
 

羡慕嫉妒恨的漂亮算法:

 

 

/*
 * beautiful_rotate.c
 *
 *  Created on: Dec 18, 2012
 *      Author: Jason_wbw
 */

#include <stdio.h>

/**
 * 将vector逆序,比如vector为abcde,逆序后为edcba
 */
void reverse(char* vector, int begin, int end){
	while(begin < end){
		char temp = vector[begin];
		vector[begin] = vector[end];
		vector[end] = temp;
		begin++;
		end--;
	}
}

/**
 * test
 * 测试左旋转位数为3,先对0-2进行逆序,再对3-7逆序,最后整体逆序完成了从ab序列变成ba序列
 */
int main(){

	char vector[8] = {'a','b','c','d','e','f','g','h'};
	printf("before rotate : %s\n",vector);
	reverse(vector, 0, 3-1);
	reverse(vector, 3, 8-1);
	reverse(vector, 0, 8-1);
	printf("after rotate : %s",vector);
	return 0;
}

 

 

by @neiddy 实现的第一种书上叫做杂技的算法,很好理解。这种算法每次循环只需要给temp(代码中的buffer做一次赋值,可以减少赋值的次数)

 

 

#include <stdio.h>

void string_rotate( char* str, int len, int n )
{
	int i = 0;
	int cnt = 0;
	n %= len;
	for ( i = 0; i < n && cnt < len; i++ )
	{
		int index = i;
		char buf = str[i];
		while (1)
		{
			int temp = ( index + n ) % len;
			cnt++;
			if ( temp == i )
			{
				str[index] = buf;
				break;
			}
			else 
			{
				str[index] = str[temp];
			}
			index = temp;
		}
	}
}

int main ( void )
{
	char str[] = "12345678";
	string_rotate( str, 5, 2 );
	printf("%s\n",str);
}
分享到:
评论

相关推荐

    C++实现一维向量旋转算法

    例如,对于一个长度为8的向量abcdefgh,如果要向左旋转3个位置,结果应变为defghabc。理想的解决方案应该在时间复杂度O(n)和空间复杂度尽可能低的情况下完成这个操作。 **二、解决方案** 这里我们详细分析两种C++...

    编程珠玑 编程珠玑 编程珠玑 编程

    《编程珠玑》是一本经典的计算机科学与编程书籍,作者是Jon Bentley。这本书以其独特的视角深入探讨了程序设计的艺术和技巧,旨在提升程序员的问题解决能力,优化算法,并提高代码效率。书中涵盖了一系列实用的编程...

    编程珠玑 第2版(修订版)_编程珠玑修订_资料_

    《编程珠玑 第2版(修订版)》是一本深受程序员喜爱的经典著作,它不仅提供了丰富的编程实践经验,还深入探讨了程序设计的艺术与智慧。这本书的修订版更是在原版基础上进行了更新和完善,旨在帮助程序员提升编程技能,...

    编程珠玑源码下载编程珠玑书后源代码

    《编程珠玑》是计算机科学领域的一本经典之作,由Jon Bentley 编著,它以其深入浅出的方式探讨了程序设计的问题和解决方案,尤其在数据结构、算法优化以及问题解决策略方面有着独到的见解。这本书的源代码是作者为了...

    编程珠玑(续)

    《编程珠玑(续)》是计算机...书中涵盖了程序员操纵程序的技术、程序员取舍的技巧、输入和输出设计以及算法示例,这些内容组成一个有机的整体,如一串串珠玑展示给程序员。  《编程珠玑(续)》适合各级程序员阅读参考。

    编程珠玑 编程珠玑续

    《编程珠玑》和其续篇是两部深受程序员喜爱的经典著作,主要涵盖了程序设计、算法分析和数据结构等核心编程领域。这两本书以其深入浅出的讲解方式和丰富的实例,帮助读者提升编程技巧和解决问题的能力。 在《编程...

    编程珠玑续本

    编程珠玑续、编程珠玑续本、编程珠玑续本、编程珠玑续本

    编程珠玑(第二版)答案

    《编程珠玑》是一本经典的计算机科学书籍,作者为Jon Bentley。本书旨在通过一系列实际问题来探讨程序设计的艺术与科学,并提供了一些解决问题的方法和技巧。下面我们将根据这一主题,详细阐述一些重要的知识点。 #...

    编程珠玑习题集锦

    2. **一维向量的旋转** - **方法1:简单复制** 直接复制前i个元素到临时数组,然后将剩余元素前移,最后将临时数组的元素复制回去,但此方法需要大量额外空间。 - **方法2:逐次旋转** 实现每次旋转一位的函数,...

    编程珠玑.pdf

    第一部分 编 程 技 术 第1章 性能监视工具 3 1.1 计算素数 3 1.2 使用性能监视工具 7 1.3 一个专用的性能监视工具 8 1.4 开发性能监视工具 10 1.5 原理 11 1.6 习题 11 1.7 深入阅读 12 第2章 关联数组 13 2.1 Awk中...

    编程珠玑 Programming Pearls 第二版(中文版+源代码)

    《编程珠玑》是计算机科学领域的一本经典之作,作者是Jon Bentley,它以其独特的视角和深入浅出的讲解方式,向读者展示了编程艺术的精髓。这本书的第二版更是深受程序员和计算机科学家们的喜爱,因为它不仅涵盖了...

    《编程珠玑》源代码

    《编程珠玑》第一版是我早期职业生涯中阅读过的对我影响较大的书籍之一,在书中首次接触到的很多观点都让我长期受益。作者在这一版本中做了重要更新。新增加的很多例子让我耳目一新。 ——Steve McConnell,《代码...

    编程珠玑II(编程珠玑·续) 扫描版6.56M pdf格式

    编程珠玑II(编程珠玑·续) 扫描版6.56M pdf格式

    编程珠玑(PDF带目录)

    《编程珠玑》是一本享有盛誉的计算机科学与编程领域的经典著作,它以其深入浅出的讲解方式和丰富的实例,深受程序员和计算机科学爱好者的喜爱。这本书的主要内容围绕算法展开,旨在帮助读者掌握如何有效地解决编程...

    编程珠玑及其源码

    编程珠玑,编程珠玑续以及源码,本书针对程序设计人员探讨了一系列的实际问题,这些问题是对现实中常见问题的归纳总结。作者虽然没有给出解决这些问题的具体代码,但始终非常富有洞察力和创造力地围绕着这些折磨...

    编程珠玑总结笔记

    优化程序是编程珠玑中的一大主题,如何优化程序来提高效率是一个非常重要的问题。在这篇笔记中,我们讨论了如何优化程序来打印出小于 10000 的素数。首先,我们从 2 开始到 n-1 都不能整除则为素数,这是一个基本的...

    编程珠玑+续

    编程珠玑+续

    编程珠玑源代码

    通过研究《编程珠玑源代码》,不仅可以深化对C语言和C++的理解,还能学习到如何高效地解决实际问题,提升编程思维,从而成为一名更出色的程序员。无论是初学者还是经验丰富的开发者,都能从中受益匪浅。

Global site tag (gtag.js) - Google Analytics