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