《编程珠玑题集锦》由会员分享，可在线阅读，更多相关《编程珠玑题集锦（8页珍藏版）》请在金锄头文库上搜索。
1、二1给定的最多包含40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数。在足够的内存空间情况下，如何解决问题？如果有几个外部的临时文件可用，但仅有几百字节的内存，又该如何解决？方法1：bitmap，条件是内存无限制，约500M对40亿整数进行位图映射，对应位为0的即为缺失的。方法2：二分法根据整数二进制位是0还是1将数分为两类，选择缺失数的那一泪在进行分类，最终可以找到一个缺失的数。注：若找重复的数，也可用位图，若每个数出现不多于10次，可以用4bit表示一个数。2 将一个n元一维向量向左旋转i个位置，例如当n=8，i=3时，向量abcdefgh旋转为defghabc。简单的
2、代码使用一个n元的中间向量在n步内完成该工作。你能否仅使用额外字节的存储空间，在正比于n的时间内完成向量的旋转。方法1：也是最简单的，把前i个元素复制到一个临时数组中，然后将余下的n-i个元素依次前移，再把临时数组中的i个元素复制到剩余的位置。但是这样用了大量的额外空间。方法2：实现一个可以每次旋转1个位置的函数，调用i次，但是时间又很消耗。方法3：首先，将x0移动到临时变量t中，然后移动xi到x0,x2i到xi,x3i移动到x2i.依次类推，直到取到x0时，结束。当2i,3i,4i,等大于n时，要对n取模。只用了一个临时变量的额外空间。方法4：旋转向量x其实就是把ab变成ba,可以把x分成a
3、 bl br，交换a跟br，那么就变成了br bl a,还剩下交换bl br,就变成了，bl br a,可以利用递归。方法5：求逆。先对a求逆，再对b求逆，在对整体求逆，(a的逆b的逆）的逆=ba。（翻手）3变位词集合/兄弟单词标识单词-根据标识排序-输出集合哈希的方法七粗略估算：72法则，用于指数过程的增长假设以年利率r%投资一笔钱y年，则当r*y=72时，钱差不多翻一倍。Little定律：队列中物体的平均数量为进入速率与平均停留时间的乘积；八给定一个向量，求和最大的子向量方法：用扫描法效率最高【算法设计中常用：分治法，保存状态，避免重复计算，将信息与处理至数据结构中】后缀数组后缀数组： 后
4、缀数组 SA 是一个一维数组，它保存 1.n 的某个排列 SA1 ，SA2 ， ， SAn ，并且保证 Suffix(SAi) Suffix(SAi+1) ， 1 in 。也就是将S的n个后缀从小到大进行排序之后把排好序的后缀的开头位置顺次放入SA中。名次数组：名次数组Ranki保存的是Suffix(i)在所有后缀中从小到大排列的“名次”。简单的说，后缀数组是“排第几的是谁？”，名次数组是“你排第几？”。后缀数组和名次数组为互逆运算。height 数组：定义heighti=suffix(SAi-1)和suffix(SAi)的最长公共前缀，也就是排名相邻的两个后缀的最长公共前缀。【排名i和排名i
5、-1的后缀最长公共子串长度】hi=heightranki ，也就是 suffix(i) 和在它前一名的后缀的最长公共前缀。【hi hi-1-1】倍增法可以在 O(nlogn)的时间内计算出后缀数组 SA和名次数组 Rank。DC3 算法的时间复杂度为 O(n)。倍增算法和 DC3 算法的空间复杂度都是 O(n) 。应用：最长回文子串问题，多模式串的模式匹配问题，公共子串，子串的个数 关于后缀数组还不是很清楚！统计每个字符串出现的个数的程序实现，利用Map容器：1. #include2. #include3. usingnamespacestd;4. intmain()5. 6. mapM;7.
6、 map:iteratorj;8. stringt5=abc,dd,abc,dd,dd;9. 10. for(inti=0;i5;+i)11. Mti+;12. 13. for(j=M.begin();j!=M.end();+j)14. coutfirst,second=0) f(j,0) = 0 (j=0)2.给出两个字符串后缀，标记每个后缀属于第一个字符串还是第二个字符串。从相邻的N个字符串找公关字符串，保证这N个字符串两个都有。堆1. #includestdio.h2. inlinevoidswap(int&a,int&b)3. inttemp=a;a=b;b=temp;4. voidH
7、eapAdjust(intarray,inti,intnLength)/自顶向下调整堆5. intnChild;intnTemp;/赋值为待调整的节点6. for(nTemp=arrayi;2*inLength;i=nChild)/2*inLength说明还有左孩子7. nChild=2*i;/左孩子8. /*一共两个子节点的话得到较大的一个*/9. if(nChildarraynChild)/nChildnLength-1判断到头没有10. +nChild;11. /*如果较大子节点大于父节点将子节点调整到父节点*/12. if(nTemp0;-i)/从最后一个非叶子节点调整（这里的i是下标
8、）22. HeapAdjust(a,i,length);23. for(inti=length;i1;-i)24. swap(a1,ai);/*第一个最大元素跟最后一个交换*/25. HeapAdjust(a,1,i);/调整堆(注意length=i由于堆是逐渐变小的)26. 27. 28. intmain()29. inta10=0,1,2,5,3,8,4,7,6;30. HeapSort(a,8);31. for(inti=1;i9;i+)32. printf(%dn,ai);33. return0;34. 问题描述：如何生成0n-1内的m个随机整数（不重复） 需求：按序输出，并且保证每个
9、子集被选中的可能性相等。 1）给出下面代码1. #includestdio.h2. #includestdlib.h3. #includetime.h4. voidgetRandNumber(intm,intn)/在0-n-1中挑选m个随机数5. 6. srand(time(NULL);/这个很关键7. inti,j;8. for(i=0;in;+i)9. 10. if(rand()%(n-i)m)11. 12. printf(%d,i);13. m-;14. 15. 16. 17. intmain()18. 19. getRandNumber(5,10);20. return0;21. 最长子串问题LCS(连续)#includeusing namespace std;#includeusing namespace std;char* commonStr(char *str1, char *str2)if(str1=NULL|str2=NULL)return
