问题A:给定一个最多包含40亿个随机排列的32位的顺序文件，找到一个不在文件的32位整数。在内存足够的情况下，如何解决该问题？如果有几个外部的临时文件可以用，但是仅有几百个字节可以用，又该如何解决问题 当内存够的情况下，C/C++可以用set集合来做，同样的Java可以用HashSet来做，或者使用第一章的位图法用1个int来存储32个数，0表示不存在，1表示存在。。具体就不说了 下面是不够的源码
#include <iostream> using namespace std; /* a, b, c,都是三个等长的数组， a数组用来保存要探测的所有的值 b数组用来保存当前bit位为1的数 c数组用来保存当前bit为为0的数 aLen表示a数组的其长度。 bit表示开始从哪一位测试，当然首先从最高位开始，然后递减。 比如32位。bit=32.(以测试数据中的最大数的最高位为准，如最大数为15（1111）则取4，若最大数为30（11110）则取5 */ int get_lost(int *a, int *b, int *c, int aLen, int bit) { int theLostNumber = 0, flag= 0, bLen = 0, cLen, i = 0; //flag用来与数值进行与操作，来对数值进行分类；bLen用来表示b数组长度，cLen用来表示c数组长度 while (bit--) { flag = (1 << bit); for (bLen = cLen = i = 0; i < aLen; ++i) { if (a[i] & (1 << bit)) b[bLen++] = a[i]; //当a[i]当前bit位为1时存入b数组 else c[cLen++] = a[i]; //当a[i]当前bit位为0时存入c数组 } if (bLen <= cLen) //找到分出来的更短的数组，此时表示b数组更短， { theLostNumber += flag; //当为b数组时加上对应的高位为1的换算值（1<<bit) a = b; aLen = bLen; } else { a=c; aLen = cLen; } } return theLostNumber; } int main(){ int originalArr[14]={1,2,3,4,5,6,7,8,9,10,11,12,13,15}; int category1[14]; int category0[14]; int theLostNumber=get_lost(originalArr,category1,category0,14,4); cout<<theLostNumber; }问题B:字符串循环移位 算法思想来源于书上 啊哈灵机一动：我们将问题看成是数组ab转换成为数组ba。 实现原理(或者说是数学原理) 先对a求逆，得到a’b;再对b求逆,得到a’b’;最后对a’b’求逆，得到ba
#include<iostream> #define Length 9 using namespace std; char array[Length]="abcdefgh"; void reverse(int start,int end){ int increment; char temp; int middle=(start+end)/2; for(increment=0;increment+start<=middle;increment++){ temp=array[increment+start]; array[increment+start]=array[end-increment]; array[end-increment]=temp; } } int main(){ cout<<"对前三个求逆\n"; reverse(0,2); for(int i=0;i<Length-1;i++){ cout<<array[i]; } cout<<endl; cout<<"对剩下的求逆\n"; reverse(3,Length-2); for(int i=0;i<Length-1;i++){ cout<<array[i]; } cout<<endl; cout<<"对所有的求逆\n"; reverse(0,Length-2); for(int i=0;i<Length-1;i++){ cout<<array[i]; } }**题C:给定一个英文字典，找到其中的所有变位词集合。列如，”pots”,”stop”,和”tops”互为变换词。因为 每一个单词都可以通过其他单词变换字母顺序得到，也就是每一个单词都由相同字母，且相应字母个数都相等的字母集构成。**
package chapter2; import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.TreeSet; class WordInfo{ public String word=""; public String flag=""; } public class tC { public static HashMap<String, TreeSet<String>> result=new HashMap<String, TreeSet<String>>(); public static void computeFlag(WordInfo wordInfo){ String word=wordInfo.word; char[] flag=word.toCharArray(); Arrays.sort(flag); System.out.print(wordInfo.word); // 方案一： for(int index=0;index<flag.length;index++){ // wordInfo.flag+=flag[index]; // } int count,index; for(index=0;index<flag.length;index++){ count=1; while( (index+1<flag.length) && ( flag[index]==flag[index+1] )){ count++; index++; } wordInfo.flag+=flag[index]; if(count>1){ wordInfo.flag+=count; } } System.out.println(" "+wordInfo.flag); TreeSet<String> sameSpellWord=result.get(wordInfo.flag); if(sameSpellWord==null){ sameSpellWord=new TreeSet<String>(); sameSpellWord.add(wordInfo.word); result.put(wordInfo.flag,sameSpellWord); } else{ sameSpellWord.add(wordInfo.word); // result.put(wordInfo.flag,sameSpellWord); } } public static void main(String args[]){ WordInfo wordsInfo[]=new WordInfo[10]; String words[]={"tops","stop","pots","posited","deposit","posited","topside","cholecystoduodenostomy","duodenocholecystostomy","rubber"}; for(int i=0;i<10;i++){ wordsInfo[i]=new WordInfo(); wordsInfo[i].word=words[i]; computeFlag(wordsInfo[i]); } // for(int i=0;i<10;i++){ // System.out.println(wordsInfo[i].word+" 的同位词有: "); // for(int j=0;j<10;j++){ // if(i!=j&&wordsInfo[i].flag.equalsIgnoreCase(wordsInfo[j].flag)){ // System.out.print(wordsInfo[j].word+"\t"); // } // } // System.out.println(); // } System.out.println(result); } }