A： 給定一個最多包含40億個隨機排列的32位整數(shù)的順序文件，找出一個不在文件中的3位為整數(shù)（在文件中至少缺失一個這樣的數(shù)-為什么？）。在具有足夠內存的情況下，如何解決該問題？如果有幾個外部的“臨時”文件可用，但是僅僅幾百字節(jié)的內存，又該如何解決該問題？
至少缺失一個整數(shù)，因為一共有$2^32$也就是4294967296個這樣的整數(shù)。
在不考慮內存的情況下可以使用第一章的位圖技術。使用536870912個8位字節(jié)形成位圖來表示已經(jīng)看到的整數(shù)。
使用臨時文件的話，就可以使用分趟來找出來缺失的整數(shù)。
代碼如下：
//輸入數(shù)據(jù)集合、集合長度、字節(jié)范圍
int lostNumber(int numbers[],int numberLength,int localBits){
int oneArray[numberLength];
int zeroArray[numberLength];
int oneCount = 0;
int zeroCount = 0;
int lostNumber = 0 ;
int selectNumber = 0;
for (int bit = localBits - 1; bit >= 0; bit --) {
selectNumber = 1 << bit;
oneCount = 0;
zeroCount = 0;
for (int i = 0; i < numberLength; i ++) {
if (numbers[i] & selectNumber) {
oneArray[oneCount ++] = numbers[i];
}else{
zeroArray[zeroCount ++] = numbers[i];
}
}
if (oneCount > zeroCount) {
numbers = zeroArray;
numberLength = zeroCount;
}else{
lostNumber += selectNumber;
numbers = oneArray;
numberLength = oneCount;
}
}
return lostNumber;
}
實現(xiàn)：
//這里只是一個假設
int len = 13;
int maxBits = 4;
int arr[13] = {0,3,4,5,6,7,8,9,10,11,13,14,15};
int lostNum = lostNumber(arr,len,maxBits);
printf("lostNum=%d\n",lostNum);
B： 將一個n元一維向量向左旋轉i個位置。例如，當n=8且i=3時，向量abcdefgh旋轉為defghadc。簡單的代碼使用一個n元的中間向量在n步內完成該工作。你能否僅使用十個額外字節(jié)的存儲空間，在正比于n的時間內完成向量的旋轉。
雖然說可以想象出來這么做的原因，但是真想不起來要這么做。所以直接上代碼：
int greatestCommonDivisor(int m,int n){
while (m != n) {
if (m > n) {
m -= n;
}else{
n -= m;
}
}
return m;
}
void rotatingVector(int array[],int rotate,int vector){
int gcd = greatestCommonDivisor(rotate, vector);
for (int i = 0; i < gcd; i ++) {
int temp = array[i];
int first = i;
int next = (i + rotate)%vector;
while (next != i) {
array[first] = array[next];
first = next;
next = (first + rotate)%vector;
}
array[first] = temp;
}
}
驗證：
int array[10] = {1,2,3,4,5,6,7,8,9,10};
rotatingVector(array, 4, 10);
for (int i = 0; i < 10; i ++) {
printf("number=%d\n",array[i]);
}
C： 給定一個英語字典，找出其中所有變位詞集合。例如：“pots”、“stop”和“tops”互為變位詞。
為了找出給定單詞的所有變位詞，我們首先計算它的標識。如果不允許進行預處理，我們只能順序讀取整個字典，計算每個單詞的標識并比較兩個標識。如果允許進行與處理，我們可以在一個預先計算好的結構中執(zhí)行二分搜索，該結構中包括按表示排序的對（標識、單詞）。
下邊是別人的實現(xiàn)分成兩部分：
宏定義
#define WORDMAX 100
#define error( str ) fatal_error( str )
#define fatal_error( str ) fprintf( stderr, "%s\n", str ), exit( 1 )
獲取單詞到文件中：
//比較
int charcomp(const void* x, const void* y) { return *(char*)x - *(char*)y; }
//字符串大小寫轉換
char* mytolower(char* lword, char* word)
{
while ( *word != '\0' ){
if (isalpha(*word) && isupper(*word)){ *lword++ = tolower(*word++); }
else { *lword++ = *word++; }
}
*lword = '\0'; // 末尾加結束字符
return lword;
}
//獲取單詞標識并添加到文件中
void add_sign(FILE* rfile, FILE* wfile)
{
assert(rfile != NULL && wfile != NULL);
char word[WORDMAX], lword[WORDMAX], sign[WORDMAX];
while(fscanf(rfile, "%s", word) != EOF){
mytolower(lword, word);
strcpy(sign, lword);
qsort(sign, strlen(sign), sizeof(char), charcomp);
fprintf(wfile, "%s\t%s\r\n", sign, word);
}
return;
}
代碼測試：
FILE* rfile = fopen("/Users/zhangguanqing/Downloads/Calculator/Calculator/dictionary.txt", "r");
if (NULL == rfile){ fatal_error("不能打開dictionary.txt文件！\n"); }
FILE* wfile = fopen("/Users/zhangguanqing/Downloads/Calculator/Calculator/sign_dictionary.txt", "w");
if (NULL == wfile){ fatal_error("不能打開sign_dictionary.txt文件！\n"); }
add_sign(rfile, wfile);
fclose(rfile);
fclose(wfile);
printf("生成完畢！！");
第二部分輸出所有變位詞：
void print_anagrams(FILE* rfile)
{
char word[WORDMAX], sign[WORDMAX];
multimap<string,string> angrams;
std::set<string> myset;
while(fscanf(rfile, "%s\t%s", sign, word) != EOF){
myset.insert(sign);
angrams.insert(std::make_pair(sign, word));
}
for (set<string>::iterator iter = myset.begin(); iter != myset.end(); ++iter) {
multimap<string, string>::iterator it = angrams.equal_range(*iter).first;
for (; it != angrams.equal_range(*iter).second; ++it){
std::cout << ' ' << (*it).second;
}
cout << endl;
}
return;
}
代碼測試：
FILE* rfile = fopen("/Users/zhangguanqing/Downloads/CalculatorHelp/CalculatorHelp/sign_dictionary.txt", "r");
if (NULL == rfile){ fatal_error("不能打開sign_dictionary.txt文件！\n"); }
print_anagrams(rfile);
fclose(rfile);
printf("執(zhí)行完畢??！");
- 考慮查找給定輸入單詞的所有變位詞問題。僅給定單詞和字典的情況下，如何解決問題？如果有一些時間可以在相應任何查詢之前預先處理字典，又會如何？
見C。 - 給定包含4300000000個32位整數(shù)的順序文件，如何找出一個出現(xiàn)至少出現(xiàn)兩次的整數(shù)？
二分搜索通過遞歸搜索包含半數(shù)以上整數(shù)的子區(qū)間來查找至少出現(xiàn)兩次的單詞。我最初的解決方案不能保證每次迭代都將整數(shù)數(shù)目減半，所以log2n趟的最壞情況運行時間正比于nlogn。jim saxe經(jīng)過觀察發(fā)現(xiàn)，該搜索用不著考慮過多重復元素，從而可以把運行時間縮短為線性時間。如果他的搜索程序知道當前范圍內m個整數(shù)中一定有重復元素，那么程序智慧在當前工作磁帶上存儲m+1個整數(shù)，此后過來的整數(shù)將會被丟棄。雖然他的方法經(jīng)常會忽略輸入變量，但其策略卻足以保證至少找到一個重復元素。 - 前面設計了兩個需要精巧代碼來實現(xiàn)的向量旋轉算法。將其分別作為獨立的程序實現(xiàn)。在每個過程中，i和n的最大公約數(shù)如何實現(xiàn)？
方法一（雜耍算法）：
見B。
方法二（求逆）：
先局部翻轉在整體翻轉（例如abcdef：n=6，i=3。先翻轉abc，再翻轉def，最后翻轉cbafed）
void Reverse(char* str,int start,int end)
{
char tmp;
int mid = (start + end)/2;
for (int i = start,j = end;i <= mid;i++,j--)
{
tmp = str[i];
str[i] = str[j];
str[j] = tmp;
}
}
//把字符串循環(huán)左移k位
void LeftRotateString(char* str,int k,int strLen)
{
Reverse(str,0,k-1);
Reverse(str,k,strLen-1);
Reverse(str,0,strLen-1);
}
測試：
char str[5] = "abcde";
LeftRotateString(str,3,5);
printf("%s\n",str);
方法三（塊變換）：
我們將旋轉的向量x分成向量a和向量b，那么旋轉向量x就相當于將向量ab兩個部分旋轉成向量ba。
假設a比b短（哪個長哪個分割）
1）將b分割成bl和br兩個部分，使得br和a的長度一致。
2）交換a和br，即ablbr轉換成了brbla。通過每次轉換序列a就位于它最終的位置了。
3）然后類推我們再交換b的兩個部分，可以使用遞歸來處理b部分。
代碼實現(xiàn)：
/*
函數(shù)作用：把兩塊數(shù)據(jù)互換
arr:待翻轉的字符串
aStart：第一塊內容的起始位置
bStart：第二塊內容的起始位置
len：交換的長度
*/
void swap(char* arr,int aStart,int bStart,int len)
{
assert(arr != NULL && aStart >= 0 && bStart >= 0 && len > 0);
char tmp;
while(len-- > 0)
{
tmp = arr[aStart];
arr[aStart] = arr[bStart];
arr[bStart] = tmp;
aStart++;
bStart++;
}
}
//待旋轉字符串的起始位置start，長度len，向左移動的位數(shù)bits
void Rotate(char* str,int Start,int len,int bits)
{
//根據(jù)移動的位數(shù)，把待旋轉字符串分成兩部分
//左半部分
int leftStart = Start;
int leftLen = bits;
//右半部分
int rightLen = len - bits;
//待旋轉字符串長度為1時，直接結束
if (1 == len)
{
return;
}
//旋轉字符串
if (leftLen > rightLen)
{
swap(str,leftStart,leftStart + leftLen,rightLen);
Rotate(str,leftStart + rightLen,len - rightLen,len - 2 * rightLen);
}
else
{
swap(str,leftStart,leftStart + len - leftLen,leftLen);
Rotate(str,leftStart,len - leftLen,leftLen);
}
}
void LeftRotateString(char* str,int k,int strLen)
{
Rotate(str,0,strLen,k);
}
測試：
char str[10] = "abcdefghij";
LeftRotateString(str,3,10);
printf("%s",str);
- 幾位讀者指出，既然所有的三個旋轉算法需要的運行時間都正比于n，雜技算法的運行速度顯然市求逆算法的兩杯。雜技算法對數(shù)組中的每個元素僅存儲和讀取一次，而求逆算法需要兩次。在實際的計算機上進行試驗以比較兩者的速度差異，特別注意內存引用位置附近的變化。
image
這里直接附上作者的答案吧（很大一部分都直接照抄的答案，畢竟答案不錯）。
我在400MHz的pentium Ⅱ 機器上運行了三種所有算法，運行時把n固定為1000000，并使旋轉距離從1變化到50。上圖繪制了在每個數(shù)據(jù)集上50次運行的平均時間。求逆代碼的運行時間比較一致，約為每個元素的58納秒，僅當旋轉距離模8余4時跳到需要66納秒（這可能和32字節(jié)的緩存大小有關）。塊交換的算法開始時開銷最高（可能是由交換單位素塊函數(shù)調用引起的），但是良好的高速緩存性能使得旋轉距離大于2時該算法是最快的算法。雜技算法開始開銷最低，但是由于其高速緩存性能很差（從每一個32字節(jié)的高速緩存線中訪問單個元素），當旋轉距離為8時所需要的時間接近200納秒雜技算法的時間再190納秒左右浮動，偶爾會有所下降（當旋轉距離為1000時，它的運行時間會降到105納秒，然后又恢復到190）。20世紀80年代中期，當旋轉距離設置為頁面大小時，這一代碼使得頁面的性能不穩(wěn)定。 - 向量旋轉函數(shù)將向量ab變?yōu)閎a。如何將向量abc變?yōu)閏ba？（這對交換非相鄰內存塊的問題進行了建模）。
類似求逆，三個部分分別翻轉，然后整體翻轉。 - 20世紀70年代末期，貝爾實驗室開發(fā)出了“用戶操作的電話號碼薄輔助程序”，該程序允許雇員使用標準的按鍵電話在公司電話號碼薄中查找號碼。要查找該系統(tǒng)設計者的名字Mike Lesk，可以按“Lesk* M * ”（也就是5375* M ），隨后，系統(tǒng)會輸出他的電話號碼。這樣的服務現(xiàn)在隨處可見。該系統(tǒng)出現(xiàn)的一個問題是，不同名字可能具有相同的案件編碼。在Lesk的系統(tǒng)中發(fā)生這種情況時，系統(tǒng)會詢問用戶更多的信息。給定一個大的名字文件（例如標準的大城市電話號碼簿），如何定位這些“錯誤匹配”呢？（當Lesk在這種規(guī)模的電話簿上做實驗時，他發(fā)現(xiàn)錯誤的匹配發(fā)生的概率僅僅是0.2%）。如何實現(xiàn)一個以名字的按鍵編碼為參數(shù)，并返回所有可能的匹配名字的函數(shù)？
名字的標識是其按鍵編碼，所以Lesk M * 的標識是“5375 * 6 *”。為了在字典中找出錯誤的匹配我們用按鍵編碼來標識每個名字，并根據(jù)標識排序（當標識相同時根據(jù)名字排序），然后順序讀取排序后的文件并輸出具有不同名字的順序標識。為了檢索給定按鈕編碼的名字，我們可以使用一種包含標識和其他數(shù)據(jù)的結構。盡管我們對該結構排序，然后使用二分法搜索查詢按鍵編碼；實際系統(tǒng)往往使用散列技術或數(shù)據(jù)庫系統(tǒng)。 - 在20世紀60年代早期，Vic Vyssotsky與一個程序員一起工作，該程序員需要轉置一個存儲在才帶上的4000*4000的矩陣（每條記錄的格式相同，為數(shù)十字節(jié)）。他的同事基礎提出的程序需要運行50個小時。Vyssotsky如何將運行時間減少到半個小時呢？
對對應的問題不理解，再遇到的時候再說吧。
為了轉置行矩陣，Vyssotsky為每條記錄插入列號和行號，然后調用系統(tǒng)的磁盤排序程序再按行排序，最后使用另一個程序刪除列號和行號。 - 給定一個n元實數(shù)集合、一個實數(shù)t和一個整數(shù)k如何快速確定是否存在一個k元子集，其元素zhi he之和不超過t。
暫時擱置吧。。
