编程珠玑第二篇主要提出了三个思想:
1。 二分查找。(binary search)
2。 交换分区。(swap section)
3。 签名。 (signature)
二分查找比较耳熟能详,签名的话我觉得是个很好的思想,差不多相当于hashMap吧。这一节我主要关注的是交换分区的算法。
问题描述大概如下:旋转一个长度为n的字符串i个位置。比如,字符串"abcdefgh", n=8, i=3,旋转过后得到"defghabc"。
最容易想到的当然是把前i个字符保存起来,然后把后面的n-i个字符移到前面去,然后再把保存起来的i个字符串粘到n-i个字符后面。时间复杂度为O(n),空间复杂度为O(i),我们需要多余的i个空间来存放那些被剪切的字符。有什么办法可以使空间复杂度降为O(1)呢?
书里面提到了Gries and Mills的一篇总结报告,<swap section>。我去网上找了来。报告中提到了三种算法:
1. Dolphine swap.
Dolphine swap的基本思路是,把x[0]先保存起来,然后把x[i]放到x[0],把x[2i]放到x[i]...如果i和n互质的话,一个循环就能将所有的字符串都放好,最后把t填充到最后一个空位中。如果i和n不互质的话,则需要做gcd个循环。
void dolphine( char* s, int pos ){
int n=strlen(s);
int r = gcd( n, pos );
int i=0;
for( i=0; i<r; i++ ){
char t=s[i];
int j=i;
while(1){
int k = j+pos;
if( k >= n )
k -= n;
if( k == i )
break;
s[j] = s[k];
j =k ;
}
s[j] = t;
}
}
//顺便给出gcd的算法
int gcd( int a, int b ){
while( a != b ){
if( a>b )
a -= b;
else
b -= a;
}
return a;
}
2. Successive swap
假设i<n-i,最容易想到的是,前i个字符串最终一定要放在最后面i个位置。把这前后两个i位的字符串进行交换,则接下来的问题变成对前面长度为n-i的字符串进行同样的操作。如果i>n-i,则交换后变成对后面n-i个字符串进行操作。
void successiveSwap( char*s, int pos ){
if( pos == 0 || pos == strlen(s) )
return;
int i, p;
i = p = pos;
j = strlen(s)-i;
while( i!=j ){
if( i<j ){
//swap( char*s, int a, int b, int m)代表将字符串s[a...a+m-1]与s[b...b+m-1]进行交换
swap( s, p-i, p+j-i, i );
j -= i;
}else{
swap( s, p-i, p, j );
i -= j;
}
}
swap( p-i, p, i );
}
3. Reversal swap
Reversal swap是最简单的。把设a=s[0...i-1], b=s[i...n-1],设如下:设a="abcd", b="kgthe",
a = reverse(a) = "dcba",
b = reverse(b) = "ehtgk"
reserse(ab) = "kgheabcd", 不正是我们想要的结果了么?
void reversalSwap( char* s, int pos ){
reverse( s, 0, pos-1 );
reverse( s, pos, strlen(s)-1 );
reverse( s, 0, strlen(s)-1 );
}
Bentley在后面的习题中提出了对这三种算法进行比较的结果,考虑比较大的数组,这样的话,该数组将占用超过一页的内存,随着旋转距离的增加,dolphine算法导致页面的不断换入换出,因此算法的时间开销变大;而SuccessiveSwap由于有比较良好的locality,时间开销是三种算法中最稳定的。ReversalSwap也比较稳定,但是因为进行了两次交换,所以时间在SuccessiveSwap之上。
附件是Gries and Mills的<swap section>
这段日子重新开始看《编程珠玑》以及这篇总结,发现之前给出的代码有点问题,修改了一下。而且我觉得第二章提出的另外两个问题也很有趣,值得我记录下来。
所谓的二分查找并不是我们通常以为的那种给定一个排好序的数组,然后进行查找,虽然思想是一致的。比如说给出99个0到100的数,让你找出在该范围中不在这组数据中的一个数(只有99个数,如果没有重复,至少也有两个数不在该数组中)。使用二分查找的思想,对数据进行顺序处理,比方说大于50的数放到一边,小于的放到另一边;至少会有一边的数据小于50个,那么肯定可以在这边的数中找到不存在的那个数,依次类推下去。
找同位词,设计一种计算方法,可以使得同位词拥有相同的计算结果。书中给出的想法是对词的字母进行排序,得到一个对应的结果。然后将所有单词的计算结果进行排序,从而使得同位词将被排在一起。
分享到:
相关推荐
ASP.NET 2.0编程珠玑--来自MVP的权威开发指南
asp.net 2.0编程珠玑--来自mvp的权威开发指南asp.net 2.0编程珠玑--来自mvp的权威开发指南
编程珠玑-英文版+中文版+source code
编程珠玑-[美]乔恩美特利.mobi、kindle文档、第二版修订版
ASP.NET+2.0编程珠玑--来自MVP的权威开发指南(英文版+中文16章节)
ASP.NET 2.0编程珠玑--来自MVP的权威开发指南
编程中的一本关于算法的好书。
《编程珠玑(第 2版·修订版)》是计算机科学方面的经典名著。书的内容围绕程序设计人员面对的一系列实际问题展开。作者JonBentley以其独有的洞察力和创造力,引导读者理解这些问题并学会解决方法,而这些正是程序员...
无书签,
编程珠玑,第二版,高清版,带目录,对学习编程有一些帮助
英文,文字版,有目录,清晰
关于很多很优秀的算法,五路从时间复杂度和空间复杂度上都很优秀
作者虽然没有给出解决这些问题的具体代码,但始终非常富有洞察力和创造力地围绕着这些折磨程序员的实际问题展开讨论,从而引导读者理解问题并学会解决问题的技能,这些都是程序员实际编程生涯中的基本技能。...
ASP.NET+2.0编程珠玑,来自MVP的权威开发指南(无密码)
薄薄的一本书,丝毫无愧于珠玑两个字能把书写薄写精的人都是无比厉害的人物,相信看过K&R的的人都有类似的体会只要看了第一章,我相信你会对这本书佩服得五体投地。一个简洁的小例子,几个看似简单的算法,实际上...