程式設計之美----擴充問題

程式設計之美之擴充問題

原帖位址：http://blog.csdn.net/jerryzcx/article/details/20663249

參考連結:

http://blog.csdn.net/wuyuegb2312/article/details/9896831

http://www.cnblogs.com/wuyuegb2312/p/3185083.html

http://www.cppblog.com/flyinghearts/archive/2010/09/01/125550.html

1.1 讓CPU占用率曲線聽你指揮

參考:

http://blog.csdn.net/wesweeky/article/details/6402564

http://www.cnblogs.com/chenyuming507950417/archive/2012/09/14/2685097.html

1.2 中國象棋将帥問題

解法二用進制的方法好了解一些,但以下參考中有人用多重循環轉換的方式解釋也可以了解

參考:

http://book.douban.com/annotation/13753057/

http://blog.csdn.net/kabini/article/details/2256421

http://blog.csdn.net/silenceburn/article/details/6133222

1.3 一摞烙餅的排序

遞歸周遊+上界下界剪枝+狀态記錄

http://blog.csdn.net/zuiaituantuan/article/details/6056601

擴充問題:

1多了一個腦袋可以放餅,速度肯定會加快,基本思路是将餅堆分為兩部分,第一部分中最大值小于第二部分(或第一部分最小值大于第二部分,或者這樣說,第一部分是大小是123,第二部分是456,隻是都亂序),然後兩部分分别排序,最後再合并

參考:http://www.cnblogs.com/avenxia/archive/2012/09/13/2683094.html

2

A  先按照“烙餅排序實作”對烙餅進行大小排序 

B  然後對有金黃色不朝上的烙餅做如下操作，以cakeArray[k]為例 

翻轉cakeArray[0:k],将cakeArray[k]翻到頂層，翻轉cakeArray[k],然後将cakeArray[0:k]翻轉，将cake[k]翻回原來位置 

3機率是2/3

4可以猜測出将會優先把最上面的部分有序,逐漸到下面形成有序,具體的規則沒有想到,代碼仍然是周遊,隻是将次數作界限改為翻轉餅個數

仍然參考:http://www.cnblogs.com/avenxia/archive/2012/09/13/2683094.html

5最大下辦15N/14,最小上界(5N+5)/3

第14個烙餅數P14=?

1.4 買書問題

參考:

http://blog.csdn.net/kabini/article/details/2296943 // 注意評論 第6樓舉的例子

貪心算法與動态規劃的了解

此問題貪心算法不适用(或者暫時未找到合适的貪心算法)

動态規劃時間複雜度為O(Y1*Y2*Y3*Y4*Y5)// by zjerry 如何了解這個?

1.5 快速找出故障機器

利用O(1)空間解決唯一ID值不同的問題,需要用到異或的特性,連續異或可以了解為位的連續求異存同(其實是求奇棄偶),最終得到的值就是唯一ID值(沒有相同的ID與他相同得到0)

兩個不同值根據異或結果某一位上的1,将原ID集合分為兩類,該位上有1和無1,再分别連續異或

另解法:構造方程,求一個值,利用原正常ID構造和,然後減去現有,剩下值即為所求;求兩個值,可以構造x+y,x^2+y^2

擴充問題:

3個值或3個以上的情況下可以考慮構造方程,

也可以考慮用hashMap儲存ID,然後過濾正常ID

撲克問題:用原和減去剩下的和

1.6 飲料供貨

動态規劃

貪心

參考:http://blog.csdn.net/lichaoyin/article/details/9983883

動态規劃思路基本上是背包問題

貪心算法利用到了進制分解,将容量以二進制看待,設計資料結構:每一位後有一條最大值連結清單,算法:從低位到高位,該位需要容量填充時就從每一位後的有序連結清單中得到滿意度最大的若幹容量相加,計算之前先将上一個低位的最大值合并到新的連結清單中(有些類似哈夫曼樹的構造過程?)

1.7 光影切割問題

解法一:分析出每增加一直線,如果增加m個交點,那麼該直線被新增加的m個交戰分成m+1段,每一段又會将原區域劃成兩塊,于是新增加了m+1塊

如果有n條直線,m個交點,那麼區域數為n+m+1,求解過程是1+求和(m0+1)=1+n條直接的全部交點和+n=1+m+n  // 因為每次增加m0+1,n個點求和

切割塊數先将所有點的交點求出來,然後排序,鎖定AB之間的點(二分查找),再利用1+n+m計算出塊數

解法二:

區域内的交戰數目等于一個邊界上交點順序相對另一個邊界交點順序的逆序總數,求逆序數利用分治法可以優化到O(n*logn)

// by zjerry 這個轉換過程沒完全了解,為什麼逆序數會=交點數?

1.8 小飛的電梯調試算法

如何從O(N^2)優化到O(N)的關鍵是找到周遊過程相鄰之間的增減關系

擴充問題

1仍然用書中的解法二,O(N)時間内解決,

2// by zjerry 還要再想想

1.9 高效率地安排見面會

http://blog.csdn.net/chdhust/article/details/8333567

http://www.cppblog.com/flyinghearts/archive/2010/08/15/123536.html

原問題是NP的經典問題 地圖着色

擴充問題:

1.基于時間軸的活動地點選擇問題,由于可以向一維時間軸投影,是以可以使用貪心算法

書中O(N^2)解法沒仔細了解(應該是類似着色判斷是否合理的算法),

主要了解第二個解法:直接計算某區間最大重疊次數,如果利用計數排序+一次MAX值掃描,可以優化到O(N)  // by zjerry

2.問題的前提還是在優化總的時間基礎上,是以隻能原問題的基礎上擴張結構以實作集中

我的想法是,同學對見面會的興趣度可以了解為圖中的邊的權重,讓每個都集中也就是總體集中

頂點着色數量設計好後,頂點起始時間排序,起始時間相同則按照上一頂點與欲選擇頂點的興趣度排序,最後得到結果

1.10 雙線程高效下載下傳

// by zjerry 信号量,互斥鎖

1.11 NIM(1)一排石頭的遊戲

注明A先取,B後取

擴充

1.N=3K+1(K=0，1，2，……）時先取者A輸，其餘情況N=3K,N=3K+2時先取者A赢

http://blog.csdn.net/dreamvyps/article/details/22264903

http://hi.baidu.com/hehehehello/item/4115b9151a2f29fd756a8487

2.N%(K+1)=0時，玩家B有必勝政策，N%(K+1)!=0時，玩家A有必勝政策。

當d=0時，無論A取多少個石頭，B取相應的石頭，使得A和B一起取(K+1)個石頭，這樣最後取到石頭的肯定是玩家B。

1.12 NIM(2)"拈"遊戲分析

注明A先配置設定,B先取,A後取

http://www.cnblogs.com/yintingru/archive/2012/08/27/2658483.html

取石頭的過程與上一次他人取的數目始終保持一個"安全的狀态",即可以確定完勝,這裡安全的狀态是XOR為0

擴充問題

1如果取光者輸,當N=2,B先取,A必輸,N>2,A必勝,隻要確定堆數為奇,個數也為奇即可,N為奇數,則配置設定(1,1,1,...),N為偶數,則配置設定(N/2,N/2)

2若是先取光者勝,則A保持安全狀态為每次取走和為K+1(與1.11擴充問題類似),且每堆的個數為>=2(關鍵是取到隻剩下K+1,K+2...K+K-1堆時的抉擇問題上)

// by zjerry 未仔細認證,先到這裡

1.13 NIM(3)兩堆石頭的遊戲

注意A先取, B後取,AB可以兩堆中各拿相等數量的石頭或從一堆中取走任意

http://www.cnblogs.com/flyinghearts/archive/2011/03/22/1991972.html

擴充

1.A先取始終構造不安全局面給B,即可確定必勝(前提是初始狀态為安全)

2.NIM(4)

http://blog.sina.com.cn/s/blog_7689f89d01017u6y.html

http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/index.html // by  zjerry 台大數學系網站,希望兩岸統一,網站可以持久通路

1.14 連連看遊戲設計

擴充問題:

1.維護任意兩個格子的最短路徑的優點是,每次重新整理最短路徑資料後都能迅速判斷,但重新整理資料的過程會比較麻煩,因為連連看消去後牽扯的格子并不能立即确定出來,很大可能要維護重新整理所有格子,則N*O(N)複雜度,效率不一定高,

遊戲中是否用點選觸發的範圍修改還是全局維護資料修改,這類問題類似于動态查找樹如紅黑樹,二叉堆,能否在O(logn)可接受的時間範圍内解決問題

2.每執行完一步下棋操作後,用某種資料結構儲存目前棋局,如壓縮矩陣,鄰接矩陣,位圖等

1.15 構造數獨

http://blog.csdn.net/kabini/article/details/2598524

擴充問題:

如何表示桌面程式中的視窗/按鈕/控件?// by zjerry 我一般想到的是制定合理的坐标系,如右x下y外z,然後每個視窗的屬性有左上角坐标xy,長length,寬width,z軸z-order,能否點選clickable,性質(window,button,widget,etc)

1.16 24點遊戲

http://blog.csdn.net/jcwkyl/article/details/3931586

http://blog.csdn.net/linyunzju/article/details/7680913

http://www.cppblog.com/flyinghearts/archive/2010/08/01/121907.html

http://www.cppblog.com/flyinghearts/archive/2010/08/15/123531.html

解法一:窮舉遞歸   優化:剪枝,加法和乘法滿足交換律,swap使A>B或A<B來進行加乘法的計算

解法二:集合的分治求解  優化:最後一次兩個子集合并直接計算判斷是否24點,不用再進行集合合并後再判斷;依照解法一,每次取兩個數計算然後合并集合(按書中每次按1,n-1來分解集合,分解集合的過程太多)

1.17 俄羅斯方塊遊戲

擴充問題

1.需要DFS記錄移動路徑

2.OFFSETY增加2格,則OFFSETX的判斷範圍減少3

3.俄羅斯廣場是消除類遊戲,優先考慮消除(使遊戲更輕松),如添加子彈方塊,添加爆炸方塊,添加消除方塊;再考慮增長(使遊戲更困難),如添加變形方塊,添加移動加速,添加下落後的方塊會自動向上增長,且帶小洞,自動左右循環,初始帶有小洞的層次,

非遊戲功能上的擴充可以有:積分社交排行功能,二人PK,線上PK,且PK帶有戰鬥模式,A方消除造成B方增長

掃雷遊戲是判斷類遊戲,優先考慮降低難度,如增加提示,減少雷數,再考慮增加難度,如可改變格子數目,可調整雷數,時間縮短,雷有輕重緩急的等級,

非遊戲功能上的擴充積分社交排行,二人PK,互相設定對方的雷區等

1.18 挖雷遊戲

參考：

http://blog.csdn.net/wuyuegb2312/article/details/9302915

問題1

需要先解決問題2

問題2

1.根據已有數字将确定有雷和無雷的地區标記出來，然後将确定有雷的8鄰區計數-1,清除該塊，将确定無雷的8鄰區計數+1,清除該塊，依次解決出已點出區域的鄰區

2.步驟1解決後，可确定雷數已知，然後利用已知區域相交的結合點來劃分子雷區，再根據古典機率計算子雷區的每個點的機率

參考4.11 掃雷遊戲的機率

2.1求二進制中1的個數

解法:

1,v模2的值是1則++;

2,v右移(相當于除2),然後與0x1與運算(與上一解法思路一緻);

3,v與v-1進行與運算,将消去最右邊的1,循環進行下去,時間複雜度隻有O(n) n=1的個數;

4,查表的複雜度為O(1),不過要考慮建表的時間

針對該問題,有規律進行快速建表:

5,根據奇偶性來分析，對于任意一個正整數n

1.如果它是偶數，那麼n的二進制中1的個數與n/2中1的個數是相同的，比如4和2的二進制中都有一個1，6和3的二進制中都有兩個1。為啥？因為n是由n/2左移一位而來，而移位并不會增加1的個數。

2.如果n是奇數，那麼n的二進制中1的個數是n/2中1的個數+1，比如7的二進制中有三個1，7/2 = 3的二進制中有兩個1。為啥？因為當n是奇數時，n相當于n/2左移一位再加1。

http://blog.csdn.net/justpub/article/details/2292823

http://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html 

6.二分法,或三個一組的位操作方法

SSE4.2:POPCNT指令算法

http://en.wikipedia.org/wiki/Hamming_weight

HAKMEM算法

   1:  int Count(unsigned x) {

   2:     unsigned n;    

   3:      

   4:     n = (x >> 1) & 033333333333;    

   5:     x = x - n;   

   6:     n = (n >> 1) & 033333333333;   

   7:     x = x - n;    

   8:     x = (x + (x >> 3)) & 030707070707;   

   9:     x = modu(x, 63);  

   10:     return x;   

   11:  } 

或寫成

[html]  view plain copy

1. int BitCount5(unsigned int n)   
2. {  
3.     unsigned int tmp = n - ((n >>1) &033333333333) - ((n >>2) &011111111111);  
4.     return ((tmp + (tmp >>3)) &030707070707) %63;  
5. }  

擴充

問題一是問32位整型如何處理，用HAKMEM算法,建表,或相與的方法都合适。

問題二是給定兩個整數A和B，問A和B有多少位是不同的。

隻要先算出A和B的異或結果，然後求這個值中1的個數就行了。

這個問題其實就是數1問題多了一個步驟，隻要先算出A和B的異或結果，然後求這個值中1的個數就行了。

2.2不要被階乘吓倒

1.求N!末尾有多少個0

解法：

求質因數5的個數

其中有公式N!階乘中含有K的質因數個數 Z=[N/K]+[N/K^2]+[N/K^3]+...

2.求N!二進制最低位1的位置

解法：同上

求質因數2的個數+1（末尾有多少個0再+1位就是最低位1的位置）

同樣使用公式Z

解法2：公式Z轉化二進制後可以換算＝N減去N的二進制中1的個數

相關題目:

給定整數,判斷是否是2的方幂

即n>0&&(n&(n-1)==0)  // 該數二進制表示法隻有一個1

2.3尋找發帖水王

尋找可重複資料中出現次數超過一半的項

http://www.cnblogs.com/sooner/archive/2013/04/02/2996589.html

解法一：先排序，然後N/2的項即為所求

解法二：每次去除兩個不同ID項，最後得到的即為所求，O(N)

[cpp]  view plain copy

1. int find(int ID[], int n)  
2. {  
3.     int nTimes = 0, i, candidate;  
4.     for(i = 0; i < n;i++)  
5.     {  
6.           if(nTimes == 0)  
7.           {  
8.               candidate = ID[i];  
9.               nTimes = 1;  
10.           }  
11.           else  
12.           {  
13.               if(candidate == ID[i])  
14.               {  
15.                   nTimes++;  
16.               }  
17.               else  
18.               {  
19.                   nTimes--;  
20.               }  
21.           }  
22.     }  
23.     return candidate;  
24. }  

缺點是無法同時得到該項次數

解法三：HASH統計，空間複雜度O(N)，解法二是O(1)

擴充問題

已知有M個發帖量在1/(M+1)個以上的ID

例子：

擴充題，題目如下：

随着Tango的發展，管理者發現，“超級水王”沒有了。統計結果表明，有3個發帖很多的ID，他們的發帖數目都超過了文章總數目N的1/4。你能從發帖ID清單中快速找出他們的ID嗎？

同時删除4個不同的ID後，剩餘資料中3個多數id仍然是多數ID。

上題隻需要一個結果，而現在需要3個結果，上題用到的nTimes，也應改為3個計數器。現在我們需要3個變量來記錄目前周遊過的3個不同的ID，而nTimes的3個元素分别對應目前周遊過的3個ID出現的個數。如果周遊中有某個ID不同于這3個目前ID，我們就判斷目前3個ID是否有某個的nTimes為0，如果有，那這個新周遊的ID就取而代之，并賦1為它的周遊數（即nTimes減1），如果目前3個ID的nTimes皆不為0，則3個ID的nTimes皆減去1。

[cpp]  view plain copy

1. #include <iostream>  
2. using namespace std;  
3. int candidate[3];  
4. int count[3] = {0};  
5. int input[100];  
6. int num = 0;  
7. int main()  
8. {  
9.     cout<<"please input"<<endl;  
10.     int t;  
11.     while(cin>>t)  
12.     {  
13.         if (t == -1)  
14.             break;  
15.         input[num++] = t;  
16.     }  
17.     bool flag = false;  
18.     for (int i = 0;i < num;i++)  
19.     {  
20.         flag = false;  
21.         for (int j = 0;j < 3;j++)  
22.         {  
23.             if (count[j] == 0)  
24.             {  
25.                 continue;  
26.             }  
27.             if (candidate[j] == input[i])  
28.             {  
29.                 count[j]++;  
30.                 flag = true;  
31.             }  
32.         }  
33.         if (flag == true)  
34.         {  
35.             continue;  
36.         }  
37.         for (int j = 0;j < 3;j++)  
38.         {  
39.             if (count[j] == 0)  
40.             {  
41.                 candidate[j] = input[i];  
42.                 count[j]++;  
43.                 flag = true;  
44.                 break;  
45.             }  
46.         }  
47.         if (flag == true)  
48.         {  
49.             continue;  
50.         }  
51.         for (int j = 0;j < 3;j++)  
52.         {  
53.             count[j]--;  
54.         }  
55.     }  
56.     cout<<count[0]<<" "<<count[1]<<" "<<count[2]<<endl;  
57.     cout<<candidate[0]<<" "<<candidate[1]<<" "<<candidate[2]<<endl;  
58. }  
59. 或  
60. void Find(Type* ID, int N,Type candidate[3])  
61. {  
62.     Type ID_NULL;//定義一個不存在的ID  
63.     int nTimes[3], i;  
64.     nTimes[0]=nTimes[1]=nTimes[2]=0;  
65.     candidate[0]=candidate[1]=candidate[2]=ID_NULL;  
66.     for(i = 0; i < N; i++)  
67.     {  
68.         if(ID[i]==candidate[0])  
69.         {  
70.              nTimes[0]++;  
71.         }  
72.         else if(ID[i]==candidate[1])  
73.         {  
74.              nTimes[1]++;  
75.         }  
76.         else if(ID[i]==candidate[2])  
77.         {  
78.              nTimes[2]++;  
79.         }  
80.         else if(nTimes[0]==0)  
81.         {  
82.              nTimes[0]=1;  
83.              candidate[0]=ID[i];  
84.         }  
85.         else if(nTimes[1]==0)  
86.         {  
87.              nTimes[1]=1;  
88.              candidate[1]=ID[i];  
89.         }  
90.         else if(nTimes[2]==0)  
91.         {  
92.              nTimes[2]=1;  
93.              candidate[2]=ID[i];  
94.         }  
95.         else  
96.         {  
97.              nTimes[0]--;  
98.              nTimes[1]--;  
99.              nTimes[2]--;  
100.          }  
101.     }  
102.     return;  
103. }  

2.4 1的數目

問題一

1目前位=0,則目前位上出現1的數目=高位*R

2目前位=1,則數目=高位*R+(低位數字+1)

3目前位>1,則數目=(高位+1)*R

[cpp]  view plain copy

1. unsigned long Sumls(unsigned long n)  
2. {  
3.    unsigned long iCount=0;  
4.    unsigned long iFactor=1;  
5.    unsigned long iLowerNum=0;  
6.    unsigned long iCurrNum=0;  
7.    unsigned long iHigherNum=0;  
8.    while(n/iFactor!=0)  
9.    {  
10.       iLowerNum=n-(n/iFactor)*iFactor;  
11.       iCurrNum=(n/iFactor)%10;  
12.       iHigherNum=n/(iFactor*10);  
13.       switch(iCurrNum)  
14.       {  
15.       case 0:  
16.           iCount+=iHigherNum*iFactor;  
17.           break;  
18.       case 1:  
19.           iCount+=iHigherNum*iFactor+iLowerNum+1;  
20.           break;  
21.       default:  
22.           iCount+=(iHigherNum+1)*iFactor;  
23.           break;  
24.       }  
25.       iFactor*=10;  
26.    }  
27.    return iCount;  
28. }  

問題二

總結規律,然後估算出上界N=10^11,再從上界開始調用上述算法,求得答案

擴充

參考:(// by zj 暫時未思考這問題)

給定二進制數N，寫下從1開始到N的所有二進制數，數一下其中出現的所有“1”的個數：

　　　　　f(1)=1                f(10)=10 (因為01,10，有兩個1)                f(11)=100 (因01,10,11，有四個1) 解答：考慮f（1011）：1,10,11,100,101,110,111,1000,1001,1010,1011          第一位上：高位數為101，每兩個數就出現一個1，則出現101個1；且current位為1，低位數為0，是以5+1=6          第二位上：高位數為10，每四個數出現一個1，則出現（10）*2=4個1；且current位為1，低位數為1，是以4+1+1=6          第三位：高位數為1，出現（1）*2^2=4個1；且current位為0，低位數為11；是以4+0=4          第四位：高位數為0,，current位為1，低位數為011；是以為 低位數+1=4           通過觀察發現在 current==1 時，第n位上出現1的次數 = 高位數*2^n-1 +低位數+1

                         current==0 時，第n位上出現1的次數 =  高位數*2^n-1

2.5 尋找最大的K個數

利用簡單排序算法：冒泡排序，選擇排序，O(N*K)

利用快速排序的遞歸方法,判斷每次快排後的K左右兩邊數組大小

尋找最大的K個＝尋找第K大，進而可以根據數的本質大小順序進行二分查找（整數的話可以從二進制角度了解）

部分載入的算法可以考慮每次将最大的K個數維持一個小根堆 O(N*logK)

數的範圍已知的情況下可以考慮計數排序,桶排序

擴充問題

1感覺上述方法都行

2個人覺得可以用小根堆來先求出m個最大的，然後從中輸出k到m個

3網上答案：可以采用小頂堆來實作，使用映射二分堆，可以使更新的操作達到O(logn)。// HASH,紅黑樹之類的

// 需要将全部網頁資料加入到堆中

4網上答案：答：正如提示中所說，可以讓每台機器傳回最相關的K'個文檔，然後利用歸并

排序的思想，得到所有文檔中最相關的K個。 最好的情況是這K個文檔在所有機器中平均

分布，這時每台機器隻要K' = K / n （n為所有機器總數）；最壞情況，所有最相關的K

個文檔隻出現在其中的某一台機器上，這時K'需近似等于K了。我覺得比較好的做法可以

在每台機器上維護一個堆，然後對堆頂元素實行歸并排序。

5網上答案：答：肯定是有幫助的。 qi最相關的K個文檔可能就是qj的最相關的K個文檔，可以先假

設這K個就是，然後根據問題四的解法獲得K'，分别和這K個比較，可以用堆進行比較，從

而獲得qj最相關的K個文檔。由于最開始的K個文檔極有可能是最終的K個文檔，是以K'和K

比較的次數可能并不多。

2.6 精确表達浮點數

分情況讨論，推導通用公式

2.7 最大公約數

輾轉相除法

輾轉相減法

奇偶判斷的輾轉相減法

2.8 找符合條件的整數

參考: http://blog.csdn.net/jcwKyl/article/details/3859155

擴充問題一

題目：任意給定一個正整數N，求一個最小的正整數M(M>1)，使得N*M的十進制表示形式裡隻含有1和0.

解決這個問題首先考慮對于任意的N，是否這樣的M一定存在。可以證明，M是一定存在的，而且不唯一。

簡單證明：因為

這是一個無窮數列，但是數列中的每一項取值範圍都在[0, N-1]之間。是以這個無窮數列中間必定存在循環節。即假設有s,t均是正整數，且s<t，有 。于是循環節長度為t-s。于是10^s = 10^t。是以有：

，是以

例如，取N＝3，因為10的任何非負次方模3都為1，是以循環節周期為1.有：

給定N，求M的方法：

方法一：給定N，令M從2開始，枚舉M的值直到遇到一個M使得N*M的十進制表示中隻有1和0.

方法二：求出10的次方序列模N的餘數序列并找出循環節。然後搜尋這個餘數序列，搜尋的目的就是要在這個餘數序列中找到一些數出來讓它們的和是N的倍數。例如N=13，這個序列就是1,10,9,12,3,4然後不斷循環。很明顯有1+12=13，而1是10的0次方，12是10的3次方，是以這個數就是1000+1=1001，M就是1001/13=77。

方法三：因為N*M的取值就是1,10,11,100,101,110,111,......是以直接在這個空間搜尋，這是對方法一的改進。搜尋這個序列直到找到一個能被N整除的數，它就是N*M，然後可計算出M。例如N=3時，搜尋樹如下：

上圖中括号内表示模3的餘數。括号外表示被搜尋的數。左子樹表示0，右子樹表示1.上圖中搜尋到第二層（根是第0層）時遇到111，它模3餘數為0.是以N*M=111, M=111/3=37。

方法四：對方法三的改進。将方法三的搜尋空間按模N餘數分類，使得搜尋時間和空間都由原來的指數級降到了O(N)。改進的原理：假設目前正在搜尋由0，1組成的K位十進制數，這樣的K位十進制數共有2^k個。假設其中有兩個數X、Y，它們模N同餘，那麼在搜尋由0、1組成的K+1位十進制數時，X和Y會被擴充出四個數：10X, 10X+1, 10Y, 10Y+1。因為X和Y同餘（同餘完全可以看作相等），是以10X與10Y同餘，10X+1與10Y+1同餘。也就是說由Y擴充出來的子樹和由X擴充産生出來的子樹産生完全相同的餘數，如果X比Y小，那麼Y肯定不是滿足要求的最小的數，是以Y這棵子樹可以被剪掉。這樣，2^K個數按照模N餘數分類，每類中隻保留最小的那個數以供擴充。原來在這一層需要搜尋2^K個數，現在隻需要搜尋O(N)個數。例如，當N=9時，第0層是1(1)，

如上圖所示，第2層的110，第三層的1010、1110都因為同一層有和它同餘且更小的數而被剪掉。如果按照方法三搜尋，第三層本來應該有8個結點，但現在隻有4個結點。

另程式設計之美思路與上面一緻,都是同餘剪枝,構造1,0的數周遊,将該數z分解為z=a+b,然後利用餘數資訊數組中a%N+b%N的值再%N,計算z%N的值;

思路用到的數學公式是 (a+b)%c=(a%c+b%c)%c

例如:

計算110時,100模N的值已經得到為1,110%N=(100%N(1)+10%N(1))%N=2

擴充問題二

找出滿足題目要求的N和M,使得N*M<2^16,且N+M最大

如果N已知則求M,然後求MAX(N+M),  2^16=65536,隻有5位

如果N未知,根據數學公式可以有N*M一定,N+M最小則,N==M,N+M最大一定是N很小或M很小的情況(具體推導過程不好編輯,先扔一邊)

給定N=1,然後M=N*M,即為所求// by zj 看了下題目,N為正整數,M>1,求一個最小的正整數,這個題意真不好了解了....

2.9斐波那契(Fibonacci)數列

思路

1遞歸,問題有很多重複

2帶記錄的向後計算

3特征方程求解,但會産生無理數問題

4矩陣計算,其中可以用到二分求幂法,時間複雜度進化為O(LOGN)

擴充問題

構造方幂型矩陣,當N很大時,可以計算出MOD的結果,每一次計算都求MOD

2.10 尋找數組中的最大值和最小值

從2N減少到1.5N,主要是兩兩為一機關進行MAX 和MIN的比較

擴充問題

求次大值

思路1是MAX SECOND,

如果X比MAX大,則SECOND=MAX,MAX=X;

如果X比MAX小,則X與SECOND比較再交換

比較次數在N到2N之間

思路2仿照求最大值最小值

MAX SECOND

每兩個為一組,A[I]小于A[I+1]

如果MAX<A[I+1],則SECOND=MAX,MAX=X;

如果MAX>A[I+1],則再比較A[I+1]與SECOND;// 注意這點 走到這裡,下句要跳過,因為A[I+1]比A[I]大,SECOND不用再和A[I]比較

如果A[I]>SECOND,則再交換;

// 例子如   5 10 8 9 11 15

比較次數為0.5N+0.5N+0.5N=1.5N

2.11尋找最近點對

分治思想的利用,O(N*LOGN)

擴充問題1

類似桶排序,關鍵是相鄰兩個數的意義

簡單方法是排序,然後計算相鄰數的內插補點,然後再求MAX,O(N*LOGN)

書中的方法是桶排序或者說是抽屜原理的使用,然後在兩個桶間的最大值 與最小值得差求MAX,空間O(N)時間O(N)

擴充問題2

參考:

http://blog.csdn.net/hackbuteer1/article/details/7484746

兩個方法

1幾何思想,求凸包直徑O(N*LOGN)

2凸包邊與其最遠點距離的掃描O(N)

2.12 快速尋找滿足條件的兩個數

擴充問題// by zjerry 先放一放,找到解決3的方法就解決了1,2,關鍵了解NP,NPC問題

1

2

3

2.13 子數組的最大乘積

思路

不許用乘除法,計算N-1個乘積最大的一組

方法1 空間換時間,O(N),利用兩個數組來進行"-1"的操作

方法2     判斷N個數的乘積P的正負性,來推理出應該"-1"減去什麼樣的數,O(N)

2.14 求數組的子數組之和的最大值

這裡的子數組指連續子數組

思路DP,方法O(N),判斷目前值+之前的和,是否小于0,小于0,則将和歸為0,重新開始尋找子數組的最大值

擴充1

分為兩個子問題

擴充2

傳回子數組位置,注意算法中何時更改了和值,則上一個數就為上一輪的END,目前數為新一輪的BEGIN;在最大值比較時,儲存相應的BEGIN和END

2.15 子數組之和的最大值(二維)

擴充// by zjerry 基本思路就是向低維轉化,有一點注意,遊泳圈那種,如何進行上下,左右都像一維一樣的分兩種情況讨論(有可能最大值在上下左右交結的位置)

1

2

3

4

2.16 求數組中最長遞增子序列

方法一:用一個數組儲存到目前位時的最大子序列個數,DP思想求解,O(N^2)

方法二:用一個MAX數組儲存長度為I的遞增子序列最大元素的最小值,例如1 -1 2 -3 4 -5 6 -7 中長度為2的MAX[2]=2,

周遊這個MAX值來進行判斷子序列個數是否要加1,

利用貪心思想,每周遊的一個數如果大于則追加,同時更新這個新子序列的MAX值,

複雜度仍為O(N^2)

方法三:将周遊MAX數組改進為二分查找,進而使内層循環變為LOGN,總的複雜度降為O(N*LOGN)

2.17 數組循環移位

三次REVERSE

時間複雜度O(N)

2.18 數組分割

// by zjerry

沒完全了解,要結合DP,背包等内容看

擴充問題

針對負數,可以先将所有數+最小負數的絕對值,使所有數變為正數,然後再解(因為分割隻是為了分成內插補點小的兩組數)

2.19 區間重合判斷

解法一是将所給的區間向源區間上投影,标記未被覆寫的區間,時間複雜度是O(N^2)(外層循環是N個所給區間O(N),内層循環是每次更新未被覆寫的區間數組O(N))

解法二是容易想到的辦法,

先按區間左邊值排序O(NLOGN)

合并區間O(N)

二分查找源區間在合并後的範圍O(LOGN)

單次查找就是第三部O(LOGN)

擴充問題

參考:http://blog.csdn.net/linyunzju/article/details/7737060

// by zjerry

2.20 程式了解和時間分析

問題

了解這個程式就是從輸出的地方往前追溯就可以。這個程式輸出的條件是hit==2&&(hit1+1==hit2)，再往前追溯看hit,hit1,hit2三個變量分别代表什麼，hit表示滿足i%r[j]!=0的條件的次數，hit==2表示這個條件隻能被滿足兩次，也就是說對于一個i，在rg數組的30個數中，這個i能被其它28個數整除，而不能被其中兩個數整除。而hit1表示第一個不能整除i的數的下标，hit2表示第二個不能整除i的下标，這兩個下标被要求相差隻有1。于是，程式所要尋找的是這樣的數：這個數i不能被2-31這30個數中的兩個相鄰的數整除，但能被其它28個數整除。是以，這個i肯定是其它28個數的最小公倍數的整數倍。然而i不能被兩個相鄰的數整除，是以必然是分解質因子後要麼i的質因子中不包括這兩個數的質因子，要麼是i的質因子的次數小于這兩個數中相同質因子的次數。

那麼，隻需要給2-31這30個數分解質因數，找一下是否有這樣的相鄰的兩個數，要麼它們的質因子中有其它數沒有的質因子，要麼對于相同的一個質因子，這兩個數包含這個質因子的次數高于其它所有次數。

16、17、19、23、25、27、29、31這幾個數包含次數最高的質因子。而相鄰的則隻有16，17。是以，這段程式所要求的數i就是，它不能被16、17整除，但能被30個數中的其它28個數整除，最小的i就是其它28個數的最小公倍數，從上表中知道，這個最小的i是：23*33*52*7*11*13*19*23*29*31，用電腦計算出這個數是：2123581660200。可以把上述程式中的for循環中的i初始化成這個數來檢驗。

2.21 隻考加法的面試題

參考:http://blog.csdn.net/yutianzuijin/article/details/10300067//  by zjerry 這篇稍好了解

http://www.cnblogs.com/peteryj/archive/2009/07/08/1944889.html

http://blog.csdn.net/lyso1/article/details/5399146

http://www.cnblogs.com/flyinghearts/archive/2011/03/27/1997285.html

3.1 字元串移位包含的問題

方法1是将源串進行循環移位,然後按題目直接意思去判斷是否包含,循環移位需要O(N*N),比對至少要O(M+N)

方法2是發現循環移位的終态可以用兩個源串的拼接來作新的比較串,轉化為字元串模式比對,但是增加了空間複雜度

擴充:

不需要申請額外空間:可以改進模式比對的長度為2*length(s1),而步進的規律也改為(i+1)%length(s1),最終用KMP等算法改進為O(M+N)

3.2 電話号碼對應英語單詞

直接看問題1和2,發現,都是要先做映射然後,比對字母組合是否是真的單詞,

結果看了書中解法發現,書中寫解法的人似乎沒讀懂題目,或者沒讀完全

問題1我認為簡單描述成:根據一個号碼,如果盡可能快地從其字母組合中找出有意義的單詞

問題2我認為可以描述成:問題1是否有答案....(實在看不出還能怎麼斷句了....)

在書中解法的基礎上(周遊或遞歸得到電話中數字按下後字母的所有組合),在每個字母組合上都查一遍單詞字典表,輸出有意義的單詞,這當然不是盡可能快的方法了,查詢一個數字對應的組合有O(3^N)(// 除了7,9對應是4位),查詢字典有O(LOGMAX),最終是每次查詢O(3^N*LOGMAX)

解決方法是:

将單詞字典表每個單詞都先轉化為數字映射O(N)//N是單詞字母數量,每次查詢O(LOGMAX)

3.3 計算字元串的相似度

遞歸求相似度，遞歸中會有重複計算，需要儲存記錄

參考：http://www.cnblogs.com/yujunyong/articles/2004724.html

動态規劃自底向上，或者備忘錄自頂向下

3.4 從無頭單連結清單中删除節點

節點删除需要知道前驅,想在O(1) 的情況下删除就隻能删除目前節點的資料,而實際上删除下一結點的空間,删除前把下一節點的資料複制過來

擴充問題

一次周遊,逆置單連結清單

數組中逆置的原理是将資料不斷交換過來(因為在序存儲空間配置設定後是固定的)

連結清單中逆置則可以不交換資料,隻修改連結的結構來實作實體上的逆置,具體實作需要借助三個指針,不停将P2指向P1

3.5 最短摘要的生成

我的了解就是滑動視窗,逐漸縮小每個摘要段落區間,進而求得最短摘要,時間複雜度可以優化到O(M*LOGN*N)// by zjerry 應該還能繼續優化,我想的太簡單了?

擴充問題:

LCS相似檢測

3.6 程式設計判斷兩個連結清單是否相交

判斷最後一個節點是否相同

擴充問題

1,如果連結清單有環,兩種情況,交點在環上,交點在尾巴上,兩種情況的判斷方法都是:

先利用快慢法找到一個連結清單的碰撞點,在環内,然後周遊另外一個連結清單,周遊過程中判斷是否與碰撞點相同

2.求出交點:

無環連結清單利用求兩連結清單長度差,然後先後走

有環連結清單1交點在環上,各自求出環的入口,2交點在尾巴上,與無環連結清單一樣求連結清單長度差

3.7 隊列中取最大值操作問題

問題基于:棧中取最值問題

3.8 求二叉樹中節點的最大距離

max(maxleft,maxright,height_left+heigth_right);//左孩子的最大距離，右孩子的最大距離，左子樹的高度+右子樹的高度

3.9 重建二叉樹

3.10 分層周遊二叉樹

BFS利用隊列周遊

擴充問題

1.BFS周遊（先通路右孩子）資料入棧，一層完結時作層标記入棧，全部完成再出棧

2.BFS周遊（先通路左孩子）資料入棧，一層完結時作層标記入棧，全部完成再出棧

3.11 程式改錯

二分查找

4.1金剛坐飛機問題

問題2的解法未完全了解和掌握

擴充1

每個乘客包括金剛都是随機選位置,是以答案依然是1/N

擴充2

分情況讨論

i不可能是1,因為金剛先入座

i=2時, 隻要金剛不選中第i個人的座位,假設是x,是以機率是  n-1/n

i=3時,金剛選中第2人座位,第2人不選x;另外一種情形是金剛未選第2人未選x,第2人選自己的,然後加法原理

i=4時,類似上述

4.2瓷磚覆寫地闆

擴充1

斐波那切數列

推廣1

DP問題暫時沒徹底弄明白

推廣2

解： ①M*N必須是p*q的整數倍 ②p和q中大數要小于等于M，N的大數，小數要小于等于M,N的小數 ③如果p*q是偶數，那麼M,N當中不是p,q倍數的邊長，必須是p和q的某種*+運算組合；   如果是奇數，那麼隻需要滿足前兩個條件即可

4.3買票找零 擴充 全部是Catalan數的應用問題 解決的思路在于找到第k個,将問題轉化為1到k-1,  k+1到n兩部分,然後分别用乘法原理和加法原理,得到推導公式; 主要是了解Catalan數的概念,一半+1與一半-1組成的數列,保證排列後的和>=0,則排列形式的個數即為Catalan數

4.4點是否在三角形内 方法一面積法 方法二叉乘判别法 擴充 不包括點在邊上,可以将點邊兩個頂點構成的向量計算是否平行來判斷是否在邊上(但這裡也有浮點類型的誤差問題) 其實如果認為無誤差, 面積法中判斷某個三角形面積為0即在邊上 叉乘判别法中判斷某個積為0即在邊上

擴充之判斷點是否在多邊形内

五種方法(還沒完全了解) http://www.cnblogs.com/lzjsky/archive/2011/06/20/2085314.html

http://wenku.baidu.com/link?url=HbLXTFZks-5BM6oA8GOcFWLRAcPSWtUC55OgF35-XRJfVNNCYpYFucTULwGG1OyHZgWCIdBbOdiowdeOSDYQ-2rtQCRWtH-Ts8yPjwRytZW http://www.cnblogs.com/hhyypp/archive/2011/12/05/2276984.html http://blog.csdn.net/hgl868/article/details/7947272 http://blog.163.com/[email protected]/blog/static/776556032011927105344884/

4.5錄音帶檔案存放優化

如果檔案長度和被通路機率都不同,選擇P/L從大到小排列可以得到最佳存儲順序,書中用的執行個體推導的結論,是否有通用性呢?

4.6桶中取黑白球

對奇偶的性質判斷 對加減法的應用 對異或的應用

擴充問題 2黑白數目不定,根據內插補點和數目小的數,這兩個數字的奇偶關系得到最終結果

4.7螞蟻爬杆 離端點最遠的螞蟻即是控制全部離開時間最長的那位(其他向近遠端離開都無所謂,這位向最遠離開) 離中點最近的螞蟻即是控制全部離開時間最短的那位(其他均向近端離開,這位向近端離開)

擴充問題 http://lam8da.sinaapp.com/?p=11

http://blog.csdn.net/weichaohnu/article/details/8748138

1 2 3 4 5

4.8三角形測試用例

一般情況下測試的幾個方面: 正常輸入的功能測試 非法輸入的異常回報 邊界輸入的處理效果

擴充1 改為浮點數後,主要是設定可接受精度, 特别在相等邊上的判斷, 如等腰,等邊

擴充2 另存為的功能 正常SAVE AS的用例過程: 選擇可儲存的目錄路徑(顯示相對路徑或絕對路徑),輸入系統可接受的檔案名,儲存為WORD對應格式的擴充名檔案,重新打開該檔案資料無差異 非法輸入 選擇無權限的路徑有提示,路徑下空間不足有提示,輸入非法檔案名有提示,輸入同名檔案提示是否覆寫,輸入其他擴充名有提示 邊界輸入 暫時沒想到這種測試,怎麼樣算是邊界

4.9數獨知多少 參考論文： http://www.afjarvis.staff.shef.ac.uk/sudoku/felgenhauer_jarvis_spec1.pdf

擴充問題： 最簡單的想法就是用0表示空格，因為數獨隻用了1-9,進一步壓縮可以增加轉義符号，0表示一個空格，/20表示兩個，增加了兩個符号，或者用字母，與數字不産生沖突,比如0表示一個空格，B0表示兩個空格

4.10數字啞謎和回文

http://wenku.baidu.com/link?url=2xnIFfvaVYedENAqdWn-BhaqNwkoZJhZczE-15IdXG5YGL-3BFGrj-JZQLy8Tv2F_PZhBVt440r--2hSDEJa8SqS2bgLiV6yfHxWHApa9Ba

// 某個整數能被1,2,3-9其中的某個數字整除的通用規律:将數abcdefg寫成abc*10000+defg(假設可以被10001整除),然後abc*10001+defg-abc,最後利用defg-abc可以整除該數字來簡化計算

擴充1 N位回文數有多少個? 轉為到的問題是(N+1)/2位的數字有多少個,比如說6位數和5位數的回文數都=3位數的數字個數900 擴充2 25^2=625 問題2的推廣 其他進制上數字等式的推測....暫時沒思考,除了二進制,十進制,其他的都頭疼...

4.11掃雷遊戲的機率 參考： http://blog.csdn.net/fivedoumi/article/details/7705073

http://www.cnblogs.com/easymind223/archive/2012/07/04/2576934.html

http://blog.csdn.net/wuyuegb2312/article/details/9302915

問題1 使用古典機率，而不是條件機率全機率，因為子雷區雷數的機率不好求 問題2 問題1解出來後可以用MATLAB劃離散圖形，詳細見參考3

1.11 NIM(1)一排石頭的遊戲

注明A先取,B後取

擴充

1.N=3K+1(K=0，1，2，……）時先取者A輸，其餘情況N=3K,N=3K+2時先取者A赢

http://blog.csdn.net/dreamvyps/article/details/22264903

http://hi.baidu.com/hehehehello/item/4115b9151a2f29fd756a8487

2.N%(K+1)=0時，玩家B有必勝政策，N%(K+1)!=0時，玩家A有必勝政策。

當d=0時，無論A取多少個石頭，B取相應的石頭，使得A和B一起取(K+1)個石頭，這樣最後取到石頭的肯定是玩家B。

1.12 NIM(2)"拈"遊戲分析

注明A先配置設定,B先取,A後取

http://www.cnblogs.com/yintingru/archive/2012/08/27/2658483.html

取石頭的過程與上一次他人取的數目始終保持一個"安全的狀态",即可以確定完勝,這裡安全的狀态是XOR為0

擴充問題

1如果取光者輸,當N=2,B先取,A必輸,N>2,A必勝,隻要確定堆數為奇,個數也為奇即可,N為奇數,則配置設定(1,1,1,...),N為偶數,則配置設定(N/2,N/2)

2若是先取光者勝,則A保持安全狀态為每次取走和為K+1(與1.11擴充問題類似),且每堆的個數為>=2(關鍵是取到隻剩下K+1,K+2...K+K-1堆時的抉擇問題上)

// by zjerry 未仔細認證,先到這裡

1.13 NIM(3)兩堆石頭的遊戲

注意A先取, B後取,AB可以兩堆中各拿相等數量的石頭或從一堆中取走任意

http://www.cnblogs.com/flyinghearts/archive/2011/03/22/1991972.html

擴充

1.A先取始終構造不安全局面給B,即可確定必勝(前提是初始狀态為安全)

2.NIM(4)

http://blog.sina.com.cn/s/blog_7689f89d01017u6y.html

http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/index.html // by  zjerry 台大數學系網站,希望兩岸統一,網站可以持久通路