编程珠玑 第二章 习题解答

这一章很奇葩啊。。书中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.这个不是教科书上的故事么。