编程珠玑 第二章 习题解答

于 2012年06月2日 发布在 算法&&ACM 跳到评论

这一章很奇葩啊。。书中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. lalor说道:

    rotate没看懂……弱爆了

  2. jasper说道:

    第二题用一次二分,然后用两个等长位图表示,再将两个位图做位合并操作。这样也应该可以吧。

  3. 情有可原说道:

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

  4. Everal说道:

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

留下评论!

:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :arrow: :?: :-| :-x :-o :-P :-D :-? :) :( :!: 8-O 8)