《程式設計珠玑》--第二章 啊哈！算法

三個問題：

A題：給定一個最多包含40億個随機排列的32位整數的順序檔案，找出一個不在檔案中的32位整數。

           1、在檔案中至少存在這樣一個數？

           2、如果有足夠的記憶體，如何處理？

           3、如果記憶體不足，僅可以用檔案來進行處理，如何處理？

答案：

           1、32位整數，包括-2146473648~~2146473647，約42億個整數，而檔案中隻有40億個，必然有整數少了。

           2、如果采用位數思想來存放，則32位整數最多需要占用43億個位。約512MB的記憶體空間  (2`32/8=512MB)

                 可以采用前一章的位處理方法。然後判斷每個int是否等于-1。因為-1的二進制表示是全1的。如果不等于-1。那麼說明某一位沒有置位。需要進行處理。

          3、記憶體不足，可以采用如下思想：

                      按最高位分為兩段，沒有出現的那個數，肯定在比較小的段裡面。

                      如果比較少的段最高位為1，那麼缺少的那個數的最高位也為1.

                      如果比較少的段最高位為0，那麼少的那個數的最高位也是0.

                      依次按以上方法去處理每個位。

                 算法複雜度為O(n)。每次處理的部分都是上一次的一半。累加之後是O(n).

                 思想與找第K小數的思想是一樣的。隻不過在這裡是有一個自動分割的過程。而找第k小數的時候，是随機找一個數。

                 為了驗證思想這裡寫了段C代碼。

[html] view plaincopy

1. int get_lost(int *a, int *b, int *c, int alen, int bit)    
2. {    
3.     int re = 0, v = 0, biter = 0, *t, citer, i = 0;    
4.     if (!a || !b || alen ==(unsigned long)( (1<< bit))) return -1;  //哪個數與最多可能擁有個數相等的時候，直接傳回了。    
5.     while (bit--)    
6.     {    
7.         v = (1 << bit);    
8.         for (biter = citer = i = 0; i < alen; ++i)    
9.         {    
10.             if (a[i] & (1 << bit)) b[biter++] = a[i];    
11.             else c[citer++] = a[i];    
12.         }    
13.         if (biter <= citer)    
14.         {    
15.             re += v;    
16.             t = a; a = b; b = t;    
17.             alen = biter;    
18.         }    
19.         else    
20.         {    
21.             t = a; a = c; c = t;    
22.             alen = citer;    
23.         }    
24.     }    
25.     return re;    
26. }    

a, b, c,都是三個等長的數組，alen表示其長度。bit表示位數。比如32位。bit=32.

re表示最後缺少的那個數。

B題:字元串循環移位比如abcdef 左移三位,則變成defabc

_rev(0, i)

_rev(i, len)

_rev(0, len)

[html] view plaincopy

1. static void _res(char *a, int n)    
2. {    
3.     int i = 0, j = n - 1;    
4.     char t;    
5.     while (i < j)    
6.     {    
7.         t = a[i]; a[i] = a[j]; a[j] = t;    
8.         ++i; --j;    
9.     }    
10. }    
11. char *rever(char *a, int n, int len)    
12. {    
13.     int i, j;    
14.     if (!a || !n) return a;    
15.     _res(a, n);    
16.     _res(a + n, len - n);    
17.     _res(a, len);    
18.     return a;    
19. }    

C 題:給定一個單詞集合，找出可以互相轉換的集合。比如abc bca cba都可以互相轉換。(變位詞)

         算法如下：單詞按照字母進行排序，單詞間進行排序，這樣相同辨別的單詞聚集到一起

這裡用C++來寫了。 

[html] view plaincopy

1. void gen_label(vector<string> &dict, map<string, vector<string> >&rec)    
2. {    
3.     for (int i = 0; i < dict.size(); ++i)    
4.     {    
5.         string line = dict[i];    
6.         sort(line.begin(), line.end());    
7.         rec[line].push_back(dict[i]);    
8.     }    
9.     for (map<string, vector<string> >::iterator iter = rec.begin();iter != rec.end(); ++iter)    
10.     {    
11.         copy((iter->second).begin(), (iter->second).end(), ostream_iterator<string>(cout , " "));    
12.         cout << endl;    
13.     }    
14. }    

2.6習題

1 、如果沒有時間進行預處理，那麼可以找到這個單詞的辨別符，然後掃描這個字典，辨別符相同的輸出。

       如果可以預處理，那麼可以先預處理，用gen_label函數進行預處理則可。

2、[關鍵看清楚：順序檔案--->已經排好序的；  4300 000 000 大于2`32]

    按照二分法，按照最大值/2 分成兩部分，取較大的部分則可。實際上如果要形成嚴格地每次下降一半，那麼需要如下處理：

           1）如果最多有max個整數，比如對于有4個bit位的整形數。最多有16個數。

           2）如果給了32個數，實際上隻需要取前面17個數就可以了，後面的不要了。（這17個數中一定有重複的數，隻需要找出一個重複的就可以）

           3）把這17個數按首位分為兩堆，按理說一邊是8，一邊是9。如果發現分的一邊比9還要多出幾個。多出來的也不用看了。接下來處理9個的情況。

           4）這樣線上性時間内一定可以找到一個重複的數

    通過這種政策，可以保證最終可以找到那個重複的數。

5、如果是自己寫函數那麼就是前面所寫的_rev函數。

    如果是要調用rever()函數。那麼方法如下。

[html] view plaincopy

1. int main(void)    
2. {    
3.     int n, len;    
4.     char *c = NULL;    
5.     while (scanf("%s", a) != EOF)    
6.     {    
7.         len = strlen(a);     
8.         c = a;    
9.         ++len;    
10.         while (len--)    
11.         {    
12.             rever(c, len - 1, len);    
13.             ++c;    
14.         }    
15.         printf("%s\n", a);    
16.     }    
17.     return 0;    
18. }    

6、把名字對應的按鍵形成一個唯一的辨別符，可以先對名字進行預處理。

    用hash,

    hash_map<int, hash_set<string> > rec;

8、把最小的K個數找到O(nlogk),然後看這個K個數的和是否小于t.

9、搜尋次數C > nlgn/ (n - lgn)