编程珠玑 第二章 习题解答

这一章很奇葩啊。。书中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;
}
}

gaogao函数用到了一个辅助函数,rangeswap,就是将[start1,start1+n)和[start2,start2+n)的值进行交换。STL中附带了一个类似的函数swap_ranges.书上说有个同构的东东。。不知道他在说啥。。可能因为实现不一样吧。

void rangeswap( int *start1, int *start2, int n ){
for( int i = 0; i < n; i++ )
swap( *(start1+i), *(start2+i) );
}

void gaogao( int *start, int *end, int shift ){
int len = end - start;
shift = ( shift%len + shift )%len;
if( len <= 1 ) return;
if( shift <= len / 2 ){
rangeswap( start, end - shift, shift );
gaogao( start, end - shift, shift );
}
else{
rangeswap( start, start+shift, len - shift );
gaogao( end - shift, end, 2</em>shift - len );
}
}
const int n = 1000000;
int main(void){
int a[n];
for( int i = 0; i < n; i++ )
a[i] = i;
gao( a, a+n, 6);
for( int i = 0; i < n; i++ )
cout << a[i] << ' ';
cout << endl;
return 0;
}

STL中还有一种更bt的实现方法,algorithm中有个rotate,他用及其简单的代码就实现了循环位移。代码如下:

template <class ForwardIterator>
void rotate ( ForwardIterator first, ForwardIterator middle,
ForwardIterator last )
{
ForwardIterator next = middle;
while (first!=next)
{
swap (first++,next++);
if (next==last) next=middle;
else if (first == middle) middle=next;
}
}

除了Orz我已经无话可说了。。

4.连答案都看不懂的我是不是弱爆了。

5.对每一块儿进行翻转,然后对整体进行翻转即可。

6.计算出所有人名的按键信息(标识),然后按照标识进行排序,查询的时候二分即可。答案中提示更多使用的是hash和数据库。

7.没有理解题意。谁来解释下?

8.第一感觉想到的是排序,然后看前k个数的和是否不超过t,不超过的话肯定存在。更优的方法用O(N)的选择算法求出第k大的数,然后把数组扫描一遍,求出小于第k大数的数的和sum,加上第k大。这样看似没有什么错误,但是仔细想想,如果第k-1大,第k大,第k+1大的数一样,肿么办?。。。。。。。。 easy~扫描的时候顺便统计小于第k大数的数的个数a,和第k大的数的个数b,嗯,然后如果a<k-1,就从b中取出m个,直到a+m == k-1。

9.

10.这个不是教科书上的故事么。

关于 “编程珠玑 第二章 习题解答” 的 5 个意见

  1. 第四题,杂技算法只交换一次,貌似比求逆快,但是时间还与cache与内存的块交换有关,因为杂技算计访问的数据不连续,并且每次又只访问一个元素,频繁的换进换出,所以实际时间长

  2. 第7题其实就是把列作为标识,先按列排序,那么第一列的所有元素就排在最前面,接下来是第二列,第三列……然后再各列内按行排序,转置后,同一列的中第一行的元素在第二行的前面,接下来是第三行第四行,所以按列内按行号排序即可。

jasper进行回复 取消回复

电子邮件地址不会被公开。