最近太忙了买了编程珠玑之后就翻过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);
}
分享到:
相关推荐
编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码编程珠玑书后源代码
我觉得不错,和大家分享! 编程珠玑 编程珠玑 编程珠玑
编程珠玑编程珠玑
《编程珠玑(续)》是计算机...书中涵盖了程序员操纵程序的技术、程序员取舍的技巧、输入和输出设计以及算法示例,这些内容组成一个有机的整体,如一串串珠玑展示给程序员。 《编程珠玑(续)》适合各级程序员阅读参考。
编程珠玑和编程珠玑续两本,上传赚点分,填充填充填充
在《编程珠玑》一书的第二章提到了n元一维向量旋转算法(又称数组循环移位算法)的五种思路,并且比较了它们在时间和空间性能上的区别和优劣。本文将就这一算法做较为深入的分析。具体如下所示: 一、问题描述 将一...
编程珠玑续、编程珠玑续本、编程珠玑续本、编程珠玑续本
编程珠玑是一本提升coding能力不可多得的好书,看书时,可以结合这个笔记,突出重点。
《编程珠玑》第一版是我早期职业生涯中阅读过的对我影响较大的书籍之一,在书中首次接触到的很多观点都让我长期受益。作者在这一版本中做了重要更新。新增加的很多例子让我耳目一新。 ——Steve McConnell,《代码...
编程珠玑II(编程珠玑·续) 扫描版6.56M pdf格式
编程珠玑,编程珠玑续以及源码,本书针对程序设计人员探讨了一系列的实际问题,这些问题是对现实中常见问题的归纳总结。作者虽然没有给出解决这些问题的具体代码,但始终非常富有洞察力和创造力地围绕着这些折磨...
编程珠玑+续
这本书是《编程珠玑》高清pdf,如有侵权请告知。
编程珠玑(第二版)答案
《编程珠玑》读书笔记
编程珠玑高清pdf版.pdf
编程珠玑,适合于开发人员的一本基础教材,建议可以通读一遍,会有收获的。