编程珠玑 第二章 习题解答

这一章很奇葩啊。。书中B问题在一面的时候被问到,C在笔试的时候是第一大题(当时写了好多)。

1.在给定单词和字典的情况下,遍历字典,计算每个的标签,然后与给定的单词的标签比较。可以预处理的话就好说了,将所有单词按照标签排序,然后可以用equal_range求出区间,O(logN)。

2.可以类比如何找出没有出现的整数。43 0000 0000 大于int的表示范围。可以先扫面一遍,把第一位为0的和第一位为1的放到两个不同的文件中,看哪个文件里面的数多,就开始处理这个文件,把第二位的0和1的数字放到两个文件中,看哪个的数字多,依此类推,最后肯定得到一个数,他出现了不止一次。

3.我实现了两个算法。gao函数是那个杂技算法,gaogao是块交换算法。经过简单的测试还没有发现什么问题。n和len的最大公约数就是置换的次数。

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int gcd( int a, int b ){
return b==0?a:gcd(b, a%b);
}
int gao( int *start, int *end, int n ){
int len = end - start;
int d = gcd( n, len );
for( int i = 0; i < d; i++ ){
int t = *(start+i);
int next = i;
while( (next+n)%len != i ){
*(start+next) = *(start+(next+n)%len);
next = (next+n)%len;
}
*(start+next) = t;
}
}

(更多…)

继续阅读 →