编程珠玑题集锦

《编程珠玑题集锦》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、二1．给定的最多包含40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数。在足够的内存空间情况下，如何解决问题？如果有几个外部的临时文件可用，但仅有几百字节的内存，又该如何解决？ 方法1：bitmap，条件是内存无限制，约500M对40亿整数进行位图映射，对应位为0的即为缺失的。方法2：二分法根据整数二进制位是0还是1将数分为两类，选择缺失数的那一泪在进行分类，最终可以找到一个缺失的数。 注：若找重复的数，也可用位图，若每个数出现不多于10次，可以用4bit表示一个数。 2．将一个n元一

2、维向量向左旋转i个位置，例如当n=8，i=3时，向量abcdefgh旋转为defghabc。简单的代码使用一个n元的中间向量在n步内完成该工作。你能否仅使用额外字节的存储空间，在正比于n的时间内完成向量的旋转。方法1：也是最简单的，把前i个元素复制到一个临时数组中，然后将余下的n-i个元素依次前移，再把临时数组中的i个元素复制到剩余的位置。但是这样用了大量的额外空间。方法2：实现一个可以每次旋转1个位置的函数，调用i次，但是时间又很消耗。方法3：首先，将x[0]移动到临时变量t中，然后移动x[i]到x[0

3、],x[2i]到x[i],x[3i]移动到[x2i]....依次类推，直到取到x[0]时，结束。当2i,3i,4i,等大于n时，要对n取模。只用了一个临时变量的额外空间。方法4：旋转向量x其实就是把ab变成ba,可以把x分成ablbr，交换a跟br，那么就变成了brbla,还剩下交换blbr,就变成了，blbra,可以利用递归。方法5：求逆。先对a求逆，再对b求逆，在对整体求逆，(a的逆b的逆）的逆=ba。（翻手）3．变位词集合/兄弟单词标识单词-根据标识排序-输出集合哈希的方法七粗略估算：72法则，用于

4、指数过程的增长假设以年利率r%投资一笔钱y年，则当r*y=72时，钱差不多翻一倍。Little定律：队列中物体的平均数量为进入速率与平均停留时间的乘积；八给定一个向量，求和最大的子向量方法：用扫描法效率最高【算法设计中常用：分治法，保存状态，避免重复计算，将信息与处理至数据结构中】后缀数组后缀数组：后缀数组SA是一个一维数组，它保存1..n的某个排列SA[1]，SA[2]，……，SA[n]，并且保证Suffix(SA[i])

5、之后把排好序的后缀的开头位置顺次放入SA中。名次数组：名次数组Rank[i]保存的是Suffix(i)在所有后缀中从小到大排列的“名次”。简单的说，后缀数组是“排第几的是谁？”，名次数组是“你排第几？”。后缀数组和名次数组为互逆运算。height数组：定义height[i]=suffix(SA[i-1])和suffix(SA[i])的最长公共前缀，也就是排名相邻的两个后缀的最长公共前缀。【排名i和排名i-1的后缀最长公共子串长度】h[i]=height[rank[i]]，也就是suffix(i)和在它前一

6、名的后缀的最长公共前缀。【h[i]≥h[i-1]-1】倍增法可以在O(nlogn)的时间内计算出后缀数组SA和名次数组Rank。DC3算法的时间复杂度为O(n)。倍增算法和DC3算法的空间复杂度都是O(n)。应用：最长回文子串问题，多模式串的模式匹配问题，公共子串，子串的个数关于后缀数组还不是很清楚！@统计每个字符串出现的个数的程序实现，利用Map容器：1.#include   2.#include 

7、  5.{  6.    map  M;  7.    map ::iterator j;  8.    string t[5]={"abc","dd","abc","dd","dd"};  9.      10.    for(int i=0;i<5;++i)  11.        M[t[i]]++;  12.      13.    for(j=M.begin();j!=M.end();++j)  14.        cout<<"<"<

8、>first<<" ,"<second<<">"<