2021微軟技術(shù)面試心得

微軟技術(shù)面試心得第1——游戲中碰到的題目第2——數(shù)字中的技巧第3——字符串及鏈表的探索第4——數(shù)學(xué)游戲的樂趣索引第1章游戲之樂——游戲中碰到的題目研究院舉辦過幾屆桌上足球（football）公開賽，第一屆的冠軍是一位文靜的女實(shí)習(xí)生。這一章的題目原計(jì)劃叫做“ProblemSolving”——運(yùn)用所學(xué)的知識(shí)解決問題，直譯為“問題解決”，甚為不美。事實(shí)上這里面大部分題目都是和游戲相關(guān)的，因此本章改名為“游戲之樂”。這些題目從游戲和作者平時(shí)遇到的有趣問題出發(fā)，向程序員提出挑戰(zhàn)。個(gè)人電腦（PC）在蹣跚起步的時(shí)候，就被當(dāng)時(shí)的主流觀點(diǎn)視為玩具。PC上的確有各種各樣的游戲，電腦上的游戲是給人玩的，如果你愿意，CPU也可以讓人“玩”。筆者曾經(jīng)用“CPU使用率”這個(gè)問題問了十幾個(gè)應(yīng)聘者，一個(gè)典型的模式如下。我：筆試考得怎么樣？發(fā)揮了多少水平？答：我不習(xí)慣在紙上寫程序，平時(shí)都在電腦上寫我：那你對(duì)Windows、操作系統(tǒng)這些東西熟悉嗎？答：那是相當(dāng)熟悉……我：好，那你可否在這筆記本電腦上幫我解決一個(gè)問題——讓CPU的使用率劃出一條直線，比如就在50%的地方。這個(gè)時(shí)候可以觀察應(yīng)聘者的好幾個(gè)方面。應(yīng)聘者面對(duì)這個(gè)陌生問題的時(shí)候如何開始分析。有人知道觀察任務(wù)管理器如何運(yùn)行，有人在紙上寫寫畫畫，有人明顯沒有什么想法。當(dāng)提示可以在網(wǎng)上搜索資料時(shí)，應(yīng)聘者如何尋找資料，如何學(xué)習(xí)。IETabMSDNMSDN網(wǎng)站應(yīng)該怎么用。有些人反復(fù)讀了函數(shù)的說明，仍不得其解。在電腦上是怎么寫程序，怎么調(diào)試程序的。有人能很嫻熟地使用C/C#的各種語(yǔ)言特性，很快地寫出程序，有人寫的程序編譯了好幾次都不能通過，對(duì)編譯錯(cuò)誤束手無策。程序第一次運(yùn)行的時(shí)候，任務(wù)管理器的CPU使用率不按預(yù)想的軌道運(yùn)行，這時(shí)候有人就十分慌亂，在程序中瞎改一通，希望能“蒙”對(duì)。有人則有條理地分析，最后找到并解決問題。我想，45是不行，雙方都明白了。這一章的其他題目大多和游戲有關(guān)，同學(xué)們?cè)谕妗翱债?dāng)接龍”“俄羅斯方塊”，甚至“魔獸”的時(shí)候，有沒有動(dòng)過好奇心——有把好奇心轉(zhuǎn)化為行動(dòng)？喜歡玩電腦、會(huì)玩電腦的人，也會(huì)運(yùn)用電腦解決實(shí)際問題，這也是我們要找的人才。讓CPU占用率曲線聽你指揮寫一個(gè)程序，讓用戶來決定Windows任務(wù)管理器（TaskManager）的CPU占用率。程序越精簡(jiǎn)越好，計(jì)算機(jī)語(yǔ)言不限。例如，可以實(shí)現(xiàn)下面三種情況[1]：CPU的占用率固定在50%，為一條直線；CPU的占用率為一條直線，具體占用率由命令行參數(shù)決定（參數(shù)范圍1~100）；CPU分析與解法有一名學(xué)生寫了如下的代碼：while（true）{if（busy）i++；else}然后她就陷入了苦苦思索：else干什么呢？怎么才能讓電腦不做事情呢？CPU使用率為0的時(shí)候，到底是什么東西在用CPU？另一名學(xué)生花了很多時(shí)間構(gòu)想如何“深入內(nèi)核，以控制CPU占用率”——可是事情真的有這么復(fù)雜嗎？MSRAIEG（MicrosoftResearchAsia,InnovationEngineeringGroup）的一些實(shí)習(xí)生寫了各種解法，他們寫的簡(jiǎn)單程序可以達(dá)到如圖1-1所示的效果。圖1-1編程控制CPU占用率呈現(xiàn)正弦曲線形態(tài)不小心寫了一個(gè)死循環(huán)，CPU占用率就會(huì)跳到最高，并且一直保持在100%。我們也可以打開任務(wù)管理器[2]，實(shí)際觀測(cè)一下它是怎樣變動(dòng)的。憑肉眼觀察，它大約是1秒鐘更新一次。一般情況下，CPU使用率會(huì)很低。但是，當(dāng)用戶運(yùn)行一個(gè)程序，執(zhí)行一些復(fù)雜操作的的使用率會(huì)急劇升高。當(dāng)用戶晃動(dòng)鼠標(biāo)時(shí)，CPU的使用率也有小幅度的變化。CPU使用率為0的時(shí)候，是誰(shuí)在使用CPU呢？通過任務(wù)管理器的“進(jìn)程（Process）”一欄可以看到，SystemIdleProcess占用了CPU空閑的時(shí)間——這時(shí)候大家該回憶起在“操作系統(tǒng)原理”這門課上學(xué)到的一些知識(shí)了吧。系統(tǒng)中有那么多進(jìn)程，它們什么時(shí)候能“閑下來”呢？答案很簡(jiǎn)單，這些程序或在等待用戶的輸入，或者在等待某些事件的發(fā)生[3]，或者主動(dòng)進(jìn)入休眠狀態(tài)[4]。在任務(wù)管理器的一個(gè)刷新周期內(nèi)，CPU忙（執(zhí)行應(yīng)用程序）的時(shí)間和刷新周期總時(shí)間的比率，就是CPU的占用率，也就是說，任務(wù)管理器中顯示的是每個(gè)刷新周期內(nèi)CPU占用率的統(tǒng)計(jì)平均值。因此，我們可以寫一個(gè)程序，讓它在任務(wù)管理器的刷新期間內(nèi)一會(huì)兒忙，一會(huì)兒閑，然后調(diào)節(jié)忙/閑的比例，就可以控制任務(wù)管理器中顯示的CPU占用率。解法一：簡(jiǎn)單的解法要操縱CPU的使用率曲線，就需要使CPU在一段時(shí)間內(nèi)（根據(jù)TaskManager的采樣率）跑busy和idle兩個(gè)不同的循環(huán)（loop），從而通過不同的時(shí)間比例，來調(diào)節(jié)CPU使用率。Busyloop可以通過執(zhí)行空循環(huán)來實(shí)現(xiàn)，idle可以通過Sleep（）來實(shí)現(xiàn)。問題的關(guān)鍵在于如何控制兩個(gè)loop的時(shí)間，我們先試驗(yàn)一下Sleep一段時(shí)間，然后循環(huán)n次，估算n的值。那么對(duì)于一個(gè)空循環(huán)for（i=0;i<n;i++）；又該如何來估算這個(gè)最合適的n值呢？我們都知道CPU執(zhí)行的是機(jī)器指令，而最接近于機(jī)器指令的語(yǔ)言是匯編語(yǔ)言，所以我們可以先把這個(gè)空循環(huán)簡(jiǎn)單地寫成如下匯編代碼（此代碼為示意性的偽代碼）后再進(jìn)行分析：next:mov eax,dwordptr[i] ；將i放入寄存器add eax,1 ；寄存器加mov dwordptr[i],eax ；寄存器賦回icmp eax,dwordptr[n] ；比較i和njl next ;i小于n時(shí)重復(fù)循環(huán)假設(shè)這段代碼要運(yùn)行的CPU是P42.4Ghz（2.4×10的9次方個(gè)時(shí)鐘周期每秒）?，F(xiàn)代CPU每個(gè)時(shí)鐘周期可以執(zhí)行兩條以上的代碼，我們?nèi)∑骄祪蓷l，于是有（2400000000×2）/5=960000000（循環(huán)/秒），也就是說CPU1秒鐘可以運(yùn)行這個(gè)空循環(huán)960000000次。不過我們還是不能簡(jiǎn)單地將n=960000000，然后Sleep（1000）了事。如果我們讓CPU工作1秒鐘，然后休息1秒鐘，波形很有可能就是鋸齒狀的——先達(dá)到一個(gè)峰值（>50%），然后跌到一個(gè)很低的占用率。我們嘗試著降低兩個(gè)數(shù)量級(jí)，令n=9600000，而睡眠時(shí)間則相應(yīng)地改為1毫秒（Sleep（10））。用10毫秒是因?yàn)楸容^接近Windows的調(diào)度時(shí)間片。如果選得太小（比如1毫秒），會(huì)造成線程頻繁地被喚醒和掛起，無形中又增加了內(nèi)核時(shí)間的不確定性。最后我們可以得到代碼清單1-1。代碼清單1-1在不斷調(diào)整9600000的參數(shù)后，我們就可以在一臺(tái)指定的機(jī)器上獲得一條大致穩(wěn)定的50%CPU占用率直線。使用這種方法要注意兩點(diǎn)影響：盡量減少sleep/awake的頻率，減少操作系統(tǒng)內(nèi)核調(diào)度程序的干擾；盡量不要調(diào)用systemcall（比如I/O這些privilegeinstruction），因?yàn)樗矔?huì)導(dǎo)致很多不可控的內(nèi)核運(yùn)行時(shí)間。該方法的缺點(diǎn)也很明顯：不能適應(yīng)機(jī)器差異性。一旦換了一個(gè)CPU，我們又得重新估算n值。有沒有辦法動(dòng)態(tài)地了解CPU的運(yùn)算能力，然后自動(dòng)調(diào)節(jié)忙/閑的時(shí)間比呢？請(qǐng)看下一個(gè)解法。解法二：使用GetTickCount（）和Sleep（）我們知道GetTickCount（）可以得到“系統(tǒng)啟動(dòng)到現(xiàn)在”所經(jīng)歷時(shí)間的毫秒值，最多能夠統(tǒng)計(jì)到49.7天。我們可以利用GetTickCount（）來判斷busyloop要循環(huán)多久，偽代碼如清單1-2所示。代碼清單1-2這兩種解法都是假設(shè)目前系統(tǒng)上只有當(dāng)前程序在運(yùn)行，但實(shí)際上，操作系統(tǒng)中有很多程序會(huì)同時(shí)執(zhí)行各種各樣的任務(wù)，如果此刻其他進(jìn)程使用了10%的CPU，那我們的程序就只能使用40%的CPU，這樣才能達(dá)到50%的效果。怎么做呢？這就要用到另一個(gè)工具來幫忙——Perfmon.exe。PerfmonWindowsNTWindows管理工具組中的專業(yè)檢測(cè)工具之一（如圖1-2所示）。Perfmon可獲取有關(guān)操作系統(tǒng)、應(yīng)用程序和硬件的各種效能計(jì)數(shù)器（perf。Perfmon的用法相當(dāng)直接，只要選擇你所要檢測(cè)的對(duì)象（比如：處理器、RAM或硬盤），然后選擇效能計(jì)數(shù)器（比如監(jiān)視物理磁盤的平均隊(duì)列長(zhǎng)度）即可。圖1-2系統(tǒng)監(jiān)視器（Perfmon）我們可以寫程序來查詢Perfmon的值，Microsoft.NetFramework提供了PerformanceCounter這一對(duì)象，可以方便地得到當(dāng)前各種性能數(shù)據(jù)，包括CPU的使用率。例如下面這個(gè)程序（見代碼清單1-3）。解法三：能動(dòng)態(tài)適應(yīng)的解法代碼清單1-3可以看到，上面的解法能方便地處理各種CPU使用率參數(shù)。這個(gè)程序可以解答前面提到的問題2。有了前面的積累，我們應(yīng)該可以讓任務(wù)管理器畫出優(yōu)美的正弦曲線了，見代碼清單1-4。解法四：正弦曲線代碼清單1-4討論如果機(jī)器是多核或多CPU，上面的程序會(huì)出現(xiàn)什么結(jié)果？如何在多核或多CPU時(shí)顯示同樣的狀態(tài)？例如，在雙核的機(jī)器上，如果讓一個(gè)單線程的程序死循環(huán)，能讓兩個(gè)CPU的使用率達(dá)到50%的水平嗎？為什么？多CPU的問題首先需要獲得系統(tǒng)的CPU信息。可以使用GetProcessorInfo（）獲得多處理器的信息，然后指定進(jìn)程在哪一個(gè)處理器上運(yùn)行。其中指定運(yùn)行使用的是SetThreadAffinityMask（）函數(shù)。另外，還可以使用RDTSC指令獲取當(dāng)前CPU核心運(yùn)行周期數(shù)。在x86平臺(tái)上定義函數(shù)：inlineunsignedint64GetCPUTickCount（）{asm{rdtsc;}}在x64平臺(tái)上定義：#defineGetCPUTickCount（）rdtsc（）使用CallNtPowerInformationAPI得到CPU頻率，從而將周期數(shù)轉(zhuǎn)化為毫秒數(shù)，例如代碼清單1-5所示。1-5_PROCESSOR_POWER_INFORMATIONinfo;CallNTPowerInformation（11, //queryprocessorpowerinformationNULL, //noinputbuffer0, //inputbuffersizeiszero&info, //outputbuffersizeof（info））; //outbufsizeunsignedint64t_begin=GetCPUTickCount（）;//dosomethingunsignedint64t_end=GetCPUTickCount（）;doublemillisec=（double）（t_end-t_begin）/（double）info.CurrentMhz;RDTSC指令讀取當(dāng)前CPU的周期數(shù)，在多CPU系統(tǒng)中，這個(gè)周期數(shù)在不同的CPU之間基數(shù)不同，頻率也可能不同。用從兩個(gè)不同的CPU得到的周期數(shù)來計(jì)算會(huì)得出沒有意義的值。如果線程在運(yùn)行中被調(diào)度到了不同的CPU，就會(huì)出現(xiàn)上述情況。可用SetThreadAffinityMask避免線程遷移。另外，CPU的頻率會(huì)隨系統(tǒng)供電及負(fù)荷情況有所調(diào)整?？偨Y(jié)能幫助你了解當(dāng)前線程/進(jìn)程/系統(tǒng)效能的API大致有以下這些。1.Sleep（）——這個(gè)方法能讓當(dāng)前線程“停”下來。2.WaitForSingleObject（）——自己停下來，等待某個(gè)事件發(fā)生。3.GetTickCount（）——有人把Tick翻譯成“嘀嗒”，很形象。、QueryPerformanceCounter（）——讓你訪問到精度更高的CPU數(shù)據(jù)。timeGetSystemTime（）——另一個(gè)得到高精度時(shí)間的方法。6.PerformanceCounter——效能計(jì)數(shù)器。。遇到多核的問題怎么辦呢？這兩個(gè)方法能夠幫你更好地控制CPU。。想拿到CPU核心運(yùn)行周期數(shù)嗎？用用這個(gè)方法吧。了解并應(yīng)用了上面的API，就可以考慮在簡(jiǎn)歷中寫上“精通Windows”了。中國(guó)象棋將帥問題下過中國(guó)象棋的朋友都知道，雙方的“將”和“帥”相隔遙遠(yuǎn)，并且不能照面。在象棋殘局中，許多高手能利用這一規(guī)則走出精妙的殺招。假設(shè)棋盤上只有“將”和“帥”二子（如圖1-3所示）（為了下面敘述方便，我們約定用A表示“將”,B表示“帥”）。圖1-3棋盤上的將和帥A、B二子被限制在己方3×3的格子里運(yùn)動(dòng)。例如，在如上的表格里，A被正方形{d10,f10,d8,f8}包圍，而B被正方形{d3,f3,d1,f1}包圍。每一步，A、B分別可以橫向或縱向移動(dòng)一格，但不能沿對(duì)角線移動(dòng)。另外，A不能面對(duì)B，也就是說，A和B不能處于同一縱向直線上（比如A在d10的位置，那么B就不能在d1、d2以及d3的位置上）。請(qǐng)寫出一個(gè)程序，輸出A、B所有合法位置。要求在代碼中只能使用一個(gè)字節(jié)存儲(chǔ)變量。分析與解法問題本身并不復(fù)雜，只要把所有A、B互相排斥的條件列舉出來就可以完成本題的要求。由于本題要求只能使用一個(gè)變量，所以首先必須想清楚在寫代碼的時(shí)候，有哪些信息需要存儲(chǔ)，并且盡量高效率地存儲(chǔ)信息。稍微思考一下，可以知道這個(gè)程序的大體框架是：遍歷A的位置遍歷B的位置判斷A、B的位置組合是否滿足要求如果滿足，則輸出因此，需要存儲(chǔ)的是A、B的位置信息，并且每次循環(huán)都要更新。首先創(chuàng)建一個(gè)邏輯坐標(biāo)系統(tǒng)，一個(gè)可行的方法是用1~9的數(shù)字，按照行優(yōu)先的順序來表示每個(gè)格點(diǎn)的位置（如圖1-4所示）。這樣，只需要用模余運(yùn)算就可以得到當(dāng)前的列號(hào)，從而判斷A、B是否互斥。圖1-4用1~9的數(shù)字表示A、B的坐標(biāo)第二，題目要求只用一個(gè)變量，我們卻要存儲(chǔ)A和B兩個(gè)子的位置信息，該怎么辦呢？可以先把已知變量類型列舉一下，然后分析。對(duì)于bool類型，估計(jì)沒有辦法做任何擴(kuò)展了，因?yàn)樗荒鼙硎総rue和false兩個(gè)值；而byte或int類型，它們能夠表達(dá)的信息則更多。事實(shí)上，對(duì)本題來說，每個(gè)子都只需要9個(gè)數(shù)字就可以表示它的全部位置。一個(gè)8位的byte類型能夠表達(dá)28=256個(gè)值，所以用它來表示A、B的位置信息綽綽有余，因此可以把這個(gè)字節(jié)的變量（設(shè)為b）分成兩部分。用前面的4bit表示A的位置，用后面的4bit表示B的位置，而4個(gè)bit可以表示16個(gè)數(shù)，這已經(jīng)足夠了。問題在于：如何使用bit級(jí)的運(yùn)算將數(shù)據(jù)從這一byte變量的左邊和右邊分別存入和讀出。下面是做法。將byteb（10100101）的右邊4bit（0101）設(shè)為n（0011）：首先清除b右邊的bits，同時(shí)保持左邊的bits:然后將上一步得到的結(jié)果與n做或運(yùn)算：將byteb（10100101）左邊的4bit（1010）設(shè)為n（0011）：首先，清除b左邊的bits，同時(shí)保持右邊的bits：現(xiàn)在，把n移動(dòng)到byte數(shù)據(jù)的左邊：n<<4=00110000然后對(duì)以上兩步得到的結(jié)果做或運(yùn)算，從而得到最終結(jié)果。得到byte數(shù)據(jù)的右邊4bits或左邊4bits（e.g.10100101中的1010以及0101）：清除b左邊的bits，同時(shí)保持右邊的bits：清除b右邊的bits，同時(shí)保持左邊的bits：將結(jié)果右移4bits：10100000>>4=00001010for循環(huán)。可以重復(fù)利用1byte來抽象化代碼，例如：for（LSET（b,1）;LGET（b）<=GRIDW*GRIDW;LSET（b,（LGET（b）+1）））解法一（如代碼清單1-6所示）代碼清單1-6輸出格子的位置用N來表示，N=1,2,…,8,9，依照行優(yōu)先的順序，如圖1-5所示。圖1-5格子的位置考慮了這么多因素，總算得到了本題的一個(gè)解法，但是MSRA里卻有人說，下面的一小段代碼也能達(dá)到同樣的目的。BYTEi=81;while（i--）{if（i/9%3==i%9%3）continue;printf（“A=%d,B=%d\n”,i/9+1,i%9+1）;}很快又有另一個(gè)人說他的解法才是效率最高的（如代碼清單1-7所示）。代碼清單1-7struct{unsignedchara:4;unsignedcharb:4;}i;for（i.a=1;i.a<=9;i.a++）for（i.b=1;i.b<=9;i.b++）if（i.a%3!=i.b%3）printf（“A=%d,B=%d\n”,i.a,i.b）;讀者能自己證明一下嗎？[5]一摞烙餅的排序星期五的晚上，一幫同事在希格瑪大廈附近的“硬盤酒吧”多喝了幾杯。程序員多喝了幾杯之后談什么呢？自然是算法問題。有個(gè)同事說：“我以前在餐館打工，顧客經(jīng)常點(diǎn)非常多的烙餅。店里的餅大小不一，我習(xí)慣在到達(dá)顧客飯桌前，把一摞餅按照大小次序擺好——子，只好用另一只手，一次抓住最上面的幾塊餅，把它們上下顛倒個(gè)個(gè)兒，反復(fù)幾次之后，這摞烙餅就排好序了?！蔽液髞硐?，這實(shí)際上是個(gè)有趣的排序問題：假設(shè)有n塊大小不一的烙餅，那最少要翻幾次，才能達(dá)到大小有序的結(jié)果呢？”如圖1-6所示。你能否寫出一個(gè)程序，對(duì)于n塊大小不一的烙餅，輸出最優(yōu)化的翻餅過程呢？圖1-6翻烙餅的順序分析與解法這個(gè)排序問題非常有意思，首先我們要弄清楚解決問題的關(guān)鍵操作——“餅，全部顛倒”。1-7。圖1-7烙餅的翻轉(zhuǎn)過程每次我們只能選擇最上方的一堆餅，一起翻轉(zhuǎn)。而不能一張張地直接抽出來，然后進(jìn)行插入，也不能交換任意兩塊餅。這說明基本的排序辦法都不太好用。那么怎么把這n個(gè)烙餅排好序呢？由于每次操作都是針對(duì)最上面的餅，如果最底層的餅已經(jīng)排序，那我們只用處理上面的n-1個(gè)烙餅。這樣，我們可以再簡(jiǎn)化為n-2、n-3，直到最上面的兩個(gè)餅排好序。解法一我們用圖1-8演示一下，為了把最大的烙餅擺在最下面，我們先把最上面的和最大的烙餅之間的翻轉(zhuǎn)（1~4之間），這樣，最大的烙餅就在最上面了。接著，我們把所有烙餅翻轉(zhuǎn)（4~5之間），最大的烙餅就擺在最下面了。圖1-8兩次翻轉(zhuǎn)烙餅，調(diào)整最大的烙餅到最底端之后，我們對(duì)上面n-1、n-2個(gè)餅重復(fù)這個(gè)過程。那經(jīng)過兩次翻轉(zhuǎn)可以把最大的烙餅翻轉(zhuǎn)到最下面。因此，最多需要把上面的n-1個(gè)烙餅依次翻轉(zhuǎn)兩次。那么，我們至多需要2（n-1）次翻轉(zhuǎn)就可以把所有烙餅排好序（烙餅排好的時(shí)候，最小的烙餅已經(jīng)在最上面了）。這樣看來，單手翻轉(zhuǎn)的想法是肯定可以實(shí)現(xiàn)的。我們進(jìn)一步想想怎么減少翻轉(zhuǎn)烙餅的次數(shù)吧。怎樣才能通過程序來搜索到一個(gè)最優(yōu)的方案呢？通過每次找出最大的烙餅進(jìn)行翻轉(zhuǎn)是一個(gè)可行的解決方案。這個(gè)方案是最好的一個(gè)嗎？考慮這樣一種情況，假如這堆烙餅中有好幾個(gè)不同的部分相對(duì)有序，憑直覺來猜想，我們可以先把小一些的烙餅進(jìn)行翻轉(zhuǎn)，讓其有序。這樣會(huì)比每次翻轉(zhuǎn)最大的烙餅要更快。既然如此，有類似的方案可以達(dá)到目的嗎？比如說，考慮每次翻轉(zhuǎn)的時(shí)候，把兩個(gè)本來應(yīng)該相鄰的烙餅盡可能地?fù)Q到一起。這樣，等所有的烙餅都換到一起之后，實(shí)際上就是完成排序了。（從這個(gè)意義上來說，每次翻最大烙餅的方案實(shí)質(zhì)上就是每次把最大的和次大的交換到一起。）在這個(gè)基礎(chǔ)之上，本能的想法就是窮舉。只要窮舉出所有可能的交換方案，那么，我們一定能夠找到最優(yōu)的一個(gè)。沿著這個(gè)思路去考慮，我們自然就會(huì)使用動(dòng)態(tài)規(guī)劃或遞歸的方法來實(shí)現(xiàn)了?？梢詮牟煌姆D(zhuǎn)策略開始，比如說第一次先翻最小的，然后遞歸把所有的可能全部翻轉(zhuǎn)一遍。這樣，最終肯定是可以找到一個(gè)解的。但是，既然是遞歸就一定有退出的條件。在這個(gè)過程中，第一個(gè)退出的條件肯定是所有的烙餅已經(jīng)排好序。那么，有其他的嗎？大家仔細(xì)想想就會(huì)發(fā)現(xiàn)到，既然2（n-1）是一個(gè)最多的翻轉(zhuǎn)次數(shù)。如果在算法中，需要翻轉(zhuǎn)的次數(shù)多于2（n-1），我們就應(yīng)該放棄這個(gè)翻轉(zhuǎn)算法，直接退出。另外，既然這是一個(gè)排序問題。我們也應(yīng)該利用排序的信息來處理。同樣，在翻轉(zhuǎn)的過程中，我們可以看看當(dāng)前的烙餅數(shù)組排序情況如何，然后利用這些信息來減少翻轉(zhuǎn)次數(shù)。代碼清單1-8是在前面討論的基礎(chǔ)之上形成的一個(gè)粗略的搜索最優(yōu)方案的程序。代碼清單1-8當(dāng)烙餅不多的時(shí)候，我們已經(jīng)可以很快地找出最優(yōu)的翻轉(zhuǎn)方案。還有優(yōu)化方案嗎？我們已經(jīng)知道怎么構(gòu)造一個(gè)可行的翻轉(zhuǎn)方案，所以最優(yōu)方案肯定不會(huì)比這個(gè)差。這個(gè)就是我們程序中的上界（UpperBound），就是說，我們感興趣的最優(yōu)方案最差也就是上面的方案了。如果我們能夠找到一個(gè)更好的構(gòu)造方案，搜索空間就會(huì)繼續(xù)縮小，所以我們一開始就設(shè)m_nMaxSwap為UpperBound，而程序中有一個(gè)剪枝：nEstimate=LowerBound（m_ReverseCakeArray,m_n）;if（step+nEstimate>m_nMaxSwap）return;m_nMaxSwap越小，這個(gè)剪枝條件就越容易滿足，更多的情況就不需要再去搜索。當(dāng)然，程序也就能更快地找出最優(yōu)方案。仔細(xì)分析上面的剪枝條件，在到達(dá)m_ReverseCakeArray狀態(tài)之前，我們已經(jīng)翻轉(zhuǎn)了step次，nEstimate是在當(dāng)前這個(gè)狀態(tài)我們至少還要翻轉(zhuǎn)多少次才能成功的次數(shù)。如果step+nEstimate大于m_nMaxSwap，也就說明從當(dāng)前狀態(tài)繼續(xù)下去，一定會(huì)超過上界。當(dāng)然就沒有必要再繼續(xù)了。顯然，nEstimate越大，剪枝條件越容易被滿足。而這正是我們希望的。結(jié)合上面兩點(diǎn)，我們希望UpperBound越小越好，而下界（LowerBound）越大越好。假設(shè)有神仙指點(diǎn)，只要告訴神仙當(dāng)前的狀態(tài)，他就能告訴你最少需要多少次翻轉(zhuǎn)。這樣，我們可以花費(fèi)O（N2）的時(shí)間得到最優(yōu)的方案。但是，現(xiàn)實(shí)中，沒有這樣的神仙。我們只能盡可能地減小UpperBound，增加LowerBound，從而減少需要搜索的空間。利用上面的程序，做一個(gè)簡(jiǎn)單的比較。對(duì)于一個(gè)輸入，10個(gè)烙餅，從上到下，烙餅半徑分別為3,2,1,6,5,4,9,8,7,0。對(duì)應(yīng)上面程序的輸入為103216549870如果LowerBound在任何狀態(tài)都為0下，你至少需要0Search函數(shù)被調(diào)用了575225200次。LowerBound稍微改進(jìn)一下（如上面程序中所計(jì)算的方法估計(jì)），要調(diào)用172126次Search函數(shù)便可以得到最優(yōu)方案：6486849程序中的下界怎么估計(jì)呢？每一次翻轉(zhuǎn)我們最多使得一個(gè)烙餅與大小跟它相鄰的烙餅排到一起。如果當(dāng)前n個(gè)烙餅中，有m對(duì)相鄰的烙餅半徑不相鄰，那么我們至少需要m次才能排好序。從上面的例子，大家都會(huì)發(fā)現(xiàn)改進(jìn)上界和下界，好處可不少。除了上界和下界的改進(jìn)，還有什么辦法可以提高搜索效率嗎？如果我們翻了若干次之后，又回到一個(gè)已經(jīng)出現(xiàn)過的狀態(tài)，還值得繼續(xù)從這個(gè)狀態(tài)開始搜索嗎？我們?cè)鯓尤z測(cè)一個(gè)狀態(tài)是否出現(xiàn)過呢？讀者也許不相信，比爾·蓋茨在上大學(xué)的時(shí)候也研究過這個(gè)問題，并且發(fā)表過論文。你不妨跟蓋茨的結(jié)果[6]比比吧。擴(kuò)展問題有一些服務(wù)員會(huì)把上面的一摞餅子放在自己頭頂上（放心，他們都戴著潔白的帽子然后再處理其他餅子，在這個(gè)條件下，我們的算法能有什么改進(jìn)？得考慮讓烙餅大小有序，并且金黃色的一面都要向上。這樣要怎么翻呢？有一次師傅烙了三個(gè)餅，一個(gè)兩面都焦了，一個(gè)兩面都是金黃色，一個(gè)一面是焦的，一是焦的概率是多少？餅的總個(gè)數(shù)最少，結(jié)果會(huì)如何呢？對(duì)于任意次序的n前的研究成果如下。目前找到的最大下界是 15n/14 ，就是說，如果有100個(gè)烙餅，那么我們至少需要15×100/14=108次翻轉(zhuǎn)才能把烙餅翻好——而且具體如何翻還不知道。目前找到的最小的上界是 （5n+5）/3 ，對(duì)于100個(gè)烙餅，這個(gè)上界是169。任意次序的n個(gè)烙餅翻轉(zhuǎn)排序所需的最小翻轉(zhuǎn)次數(shù)被稱為第n數(shù)為第14個(gè)烙餅數(shù)P14還沒有找到，讀者朋友們，能否在吃烙餅之余考慮一下這個(gè)問題？買書問題在節(jié)假日的時(shí)候，書店一般都會(huì)做促銷活動(dòng)。由于《哈利波特》系列相當(dāng)暢銷，店長(zhǎng)決定通過促銷活動(dòng)來回饋?zhàn)x者。上柜的《哈利波特》平裝本系列中，一共有五卷。假設(shè)每一卷單獨(dú)銷售均需8歐元[7]。如果讀者一次購(gòu)買不同的兩卷，就可以扣除5%的費(fèi)用，三卷則更多。假設(shè)具體折扣的情況如下。受到5%的折扣。另外一本卷一則不能享受折扣。如果有多種折扣，希望計(jì)算出的總額盡可能的低。分析與解法怎么購(gòu)買比較省錢呢？第一個(gè)感覺，當(dāng)然是優(yōu)先考慮最大折扣，然后次之。這的確是一個(gè)有效的辦法。但這個(gè)算法是不是最省錢的呢？我們直接分析可能的拆解方式，來看看算法的可行性。比如對(duì)于兩本不同卷的書，最多只能享受到2×5%=0.1的折扣。對(duì)于三本不同卷的書，可以按照3卷的折扣或按照2卷+1卷的折扣。折扣額度分別為3×10%=0.3或者2×5%+1×0%=0.1。基于這樣的推算，除去所有不能享受折扣的組合[8]（比如把三卷不同的書拆成三個(gè)一本來買，就不能享受任何折扣），可以得出如下的折扣表。[9]表1-1折扣計(jì)算表對(duì)于總數(shù)為10本以上的情況，都可以分解成為表1-1中所存在的組合。從表1-1加粗的地方違反了貪心的規(guī)則。當(dāng)我們要買8本書時(shí)，比如說買兩本第一卷，兩本第二卷，兩本第三卷，一本第四卷，一本第五卷，其序列為（2,2,2,1,1）。按照優(yōu)先考慮最大折扣的策略，即選擇5+3，購(gòu)買序列為（1,1,1,1,1）和（1,1,1,0,0）。我們先買每卷各一本，花去5×8×（1-25%）=30，再買第一、二、三卷，花去3×8×（1-10%）=21.6，共計(jì)51.6歐元。但是如果我們換一個(gè)策略，即選擇4+4，購(gòu)買序列為（1,1,1,1,0）及（1,1,1,0,1）。先買第一、二、三、四卷，然后再買第一、二、三、五卷，那么總共花去2×4×8×（1-20%）=51.2歐元。因此，針對(duì)這個(gè)問題試圖用貪心策略行不通[10]。解法一那么，有可能改進(jìn)貪心算法，從而得到一個(gè)可行的方案嗎？從表1-1中可以看出，該貪心策略會(huì)在買5+3本的時(shí)候出錯(cuò)。因?yàn)楦鶕?jù)貪心算法所推薦的5+3的購(gòu)買方式，沒有4+4購(gòu)買方式的折扣大。回過頭對(duì)比一下。在小于5本的情況下，直接按折扣買就好了。這些用貪心算法都是適用的。那么如果大于5本呢？由于折扣的規(guī)則僅針對(duì)2到5本的情況，那么選擇兩次扣除的最大的組合數(shù)為每次5本，最多為10本。對(duì)于10本以上理論上都能拆解為表1-1中出現(xiàn)的組合。因此，暫時(shí)先來研究總數(shù)在10本以內(nèi)的情況。如果要買的書為（Y1,Y2,Y3,Y4,Y5）（其中Y1＞=Y2＞=Y3＞=Y4＞=Y5），貪心策略建議我們Y5次5卷，（Y4?Y5）次4卷，（Y3?Y4）次3卷，（Y2?Y3）次2卷和（Y1?Y2）次1卷。根據(jù)表1-1中出現(xiàn)的反例，必須做相應(yīng)的調(diào)整。即考慮把5+3的組合都變成為4+4的組合（這樣的調(diào)整總是可行的嗎？）。因此，把K次5卷和K次3卷重新組合成2×K次4卷（K=min{Y5,Y3?Y4}）。結(jié)果就是應(yīng)該購(gòu)買（Y5?K）次5卷，（Y4?Y5+2K）次4卷，（Y3?Y4?K）次3卷，（Y2?Y3）次2卷和（Y1?Y2）次1卷（K=min{Y5,Y3?Y4}）。比如要買2本第一卷，2本第二卷，1本第三卷，1本第四卷和3本第五卷，像前面所說的，我們要買的書可以用（3,2,2,1,1）表示。在新的貪心策略下，K=min{Y5,Y3?Y4}=min{1,1}=1。那么購(gòu)買各種卷數(shù)的數(shù)量為5種不同卷Y5?K=1?1=04種不同卷Y4?Y5+2K=1?1+2=23種不同卷Y3?Y4?K=2?1?1=02Y2?Y3=2?2=01Y1?Y2=3?2=1具體組合信息如下。表1-2書籍分解表那么，對(duì)于10本以上的情況，仍然有可能基于調(diào)整的貪心算法思路做應(yīng)用嗎？第一種可能：比如說，可以考慮把任意多組數(shù)據(jù)都分解為10以內(nèi)的情況?？紤]對(duì)大于10本的情況提出如下假設(shè)：假設(shè)在分解的過程中，可以找到如下一種分法：可以把10本以上的書籍分成小于10的多組（X11,X12,X13,X14,X15）,（X21,X22,X23,X24,X25）…（Xn1,Xn2,Xn3,Xn4,Xn5），并且使得只要把每組的最優(yōu)解相加，就可以得到全局的最優(yōu)解。這樣就可以應(yīng)用以上的修改方法來進(jìn)行計(jì)算，從而得到最優(yōu)解。那么這種分法是正確的嗎？有辦法證明或者找到反例嗎？第二種可能：對(duì)于適用貪心算法的情況來講，最重要的原則就是做出當(dāng)前最好的選擇，而不考慮整體最優(yōu)。那么，如果我們考慮在貪心算法的選擇上做些文章，把貪心算法的選擇思路做進(jìn)一步擴(kuò)充，結(jié)果會(huì)不會(huì)更好呢？既然依然沿著貪心選擇的思路來走，那么，在對(duì)任意一組數(shù)據(jù)的分解上來看，依然考慮按照最大的分法進(jìn)行組合。比如給定一個(gè)序列（7,6,5,3,2），根據(jù)貪心算法，勢(shì)必會(huì)分成如下組合。表1-3貪心算法表根據(jù)表1-1出現(xiàn)的反例，直接按照貪心算法分解會(huì)得到錯(cuò)誤的結(jié)果。那么，是否有可能約束使做當(dāng)前選擇時(shí)，僅僅往前面多考慮一步，根據(jù)下一步的情況來決定當(dāng)前的選擇呢？比如說，當(dāng)前理論上應(yīng)該選擇5，但是由于下面有4或者3的組合，那么應(yīng)該把5+3的組合拆分為4+4的組合。很快地，我們會(huì)發(fā)現(xiàn)，當(dāng)前給出的例子第一次選擇5之后，下一步仍然選擇5，也就是說我們很難僅僅根據(jù)多考慮一步的情況來做出正確選擇，從而得到最優(yōu)解。如果換個(gè)思路呢？比如根據(jù)貪心算法計(jì)算出一個(gè)表，如表1-3，直接套用總數(shù)為10本以下的調(diào)整方法，找出所有違反貪心算法的反例，直接進(jìn)行調(diào)整（如把所有5+3的組合改變成為4+4的組合）呢？這樣是否可以充分利用貪心算法的便捷，同時(shí)又對(duì)其不足和反例進(jìn)行調(diào)整？比如，對(duì)于當(dāng)前序列（7,6,5,3,2），貪心的結(jié)果是5+5+4+3+3+2+1的組合，調(diào)整之后會(huì)成為4+4+4+4+4+2+1的組合。這個(gè)看起來是正確的。那么，有辦法證明查表法是正確的嗎？解法二經(jīng)過多次努力，我們很難證明貪心算法，甚至是找到一個(gè)合適的改進(jìn)過的貪心算法。那么，還有什么辦法嗎？似乎只能使用動(dòng)態(tài)規(guī)劃法了。首先，在使用動(dòng)態(tài)規(guī)劃之前，得考慮怎么表達(dá)購(gòu)買中間出現(xiàn)的狀態(tài)。假設(shè)我們用Xn來表示購(gòu)買第n卷書籍的數(shù)量。如果要買X1本第一卷，X2本第二卷，X3本第三卷，X4本第四卷，X5本第五卷，那么我們可以用（X1,X2,X3,X4,X5）表示，而F（X1,X2,X3,X4,X5）表示我們要買這些書需要的最少花費(fèi)。如果我們要買X3本第一卷，X2本第二卷，X1本第三卷，X4本第四卷，X5本第五卷呢？是否需要用F（X3,X2,X1,X4,X5）來表示呢？其實(shí)不難看出，因?yàn)楦骶淼膬r(jià)格一樣，需要的最少花費(fèi)仍然等于F（X1,X2,X3,X4,X5）。也就是說，F(xiàn)（X1,X2,X3,X4,X5）等價(jià)于F（X3,X2,X1,X4,X5）。因此我們沒有必要區(qū)分不同的卷。那么對(duì)于所有跟（X1,X2,X3,X4,X5）等價(jià)的情況，我們用什么來表示呢？F（X1,X2,X3,X4,X5）還是F（X1,X2,X3,X5,X4），還是……根據(jù)排列組合的規(guī)則，最多有5！種可選擇的表示方法，我們可以選擇一種特別的表示（Y1,Y2,Y3,Y4,Y5）（其中，Yn用來表示購(gòu)買第n卷書籍的數(shù)量，Y1,Y2,Y3,Y4,Y5是X1,X2,X3,X4,X5的重新排列，滿足Y1≥Y2≥Y3≥Y4≥Y5），我們稱它為所有跟（X1,X2,X3,X4,X5）等價(jià)的情況的“最小表示”。接下來，就需要考慮怎么把一個(gè)大問題轉(zhuǎn)化為小一點(diǎn)的問題。假定要買的書為（Y1,Y2,Y3,Y4,Y5）。如果第一次考慮為5本不同卷付錢（當(dāng)然這里需要保證Y5>=1），那么剩下還要再付錢的書集合為（Y1-1,Y2-1,Y3-1,Y4-1,Y5-1）。顯然，如果一次買5本書，我們沒有其他的選擇。如果第一次考慮買4本不同卷（Y4>=1）那么我們就有如下可能的買書集合。（Y1-1,Y2-1,Y3-1,Y4-1,Y5）（Y1-1,Y2-1,Y3-1,Y4,Y5-1）（Y1-1,Y2-1,Y3,Y4-1,Y5-1）（Y1-1,Y2,Y3-1,Y4-1,Y5-1）（Y1,Y2-1,Y3-1,Y4-1,Y5-1）根據(jù)題意，不同卷的書組合起來才能享受折扣，至于具體是哪幾卷，并沒有要求。但是，問題在于，應(yīng)該如何選擇一種組合來繼續(xù)分解下去呢？憑直覺來看，選擇（Y1-1,Y2-1,Y3-1,Y4-1,Y5）的組合能夠留下最多的后續(xù)組合。因?yàn)閅1≥Y2≥Y3≥Y4≥Y5。比如對(duì)于（2,2,2,2,1）這樣的卷數(shù)組合來說，選擇扣除（1,1,1,1,0）之后，留下的組合為（1,1,1,1,1）還可以做一次基于5本書的折扣。但是如果選擇扣除（1,1,1,0,1）之后，留下的組合是（1,1,1,2,0）。后續(xù)只能分解為（1,1,1,1,0）和（0,0,0,1,0）。那么，是否能夠證明（Y1-1,Y2-1,Y3-1,Y4-1,Y5）就是最好的組合呢？可以做如下的假設(shè)，假設(shè)在（Y1,Y2,Y3,Y4,Y5）的情況下選擇扣除（1,1,1,0,1）得到了最優(yōu)解。此時(shí)，剩下的組合為（Y1-1,Y2-1,Y3-1,Y4,Y5-1）。在此基礎(chǔ)上，如果能夠證明在扣除（1,1,1,1,0）之后，剩下組合為（Y1-1,Y2-1,Y3-1,Y4-1,Y5）的情況下也能得到最優(yōu)解，那么，可以認(rèn)為每次都按照（1,1,1,1,0）的扣除方式可以代表后續(xù)的所有組合。從選擇扣除4本書的組合來看，目前的選擇扣除為（1,1,1,0,1），由于Y4≥Y5，那么，顯然在（Y1-1,Y2-1,Y3-1,Y4,Y5-1）的組合中，Y4>Y5?1。則在（Y1-1,Y2-1,Y3-1,Y4,Y5-1）的所有最優(yōu)解中，一定存在某些組合僅有Y4而沒有Y5。舉例來說明。假設(shè)Y1=Y2=Y3=Y4=Y5=2。選擇（1,1,1,1,0），剩下（Y1-1,Y2-1,Y3-1,Y4-1,Y5）的組合為（1,1,1,1,2），號(hào)集合為{1,2,3,4,5,5}。（1,1,1,0,1），剩下（Y1-1,Y2-1,Y3-1,Y4,Y5-1）的組合為（1,1,1,2,1），剩下的書序號(hào)集合為{1,2,3,4,4,5}。由于Y4≥Y5>Y5?1，所以后者的各種折扣方案中，總是有一個(gè)方案的某個(gè)組合中存在第4本書而沒有第5本書。（Y1-1,Y2-1,Y3-1,Y4,Y5-1）的可能折扣方案：{1,2,3,4,5}{4}{1,2,3,4}{4,5}{1,2,4}{3,4,5}…可以看到不管哪個(gè)方案，都一定存在有第4本書，而沒有第5本書的分解情況。{1,2,3,4,5}{4}中的{4}{1,2,3,4}{4,5}中的{1,2,3,4}{1,2,4}{3,4,5}中的{1,2,4}這樣，我們總可以把有第4本書，而沒有第5本書的組合里面的第4本書換成第5本書。{1,2,3,4,5}{4}→{1,2,3,4,5}{5}{1,2,3,4}{4,5}→{1,2,3,5}{4,5}{1,2,4}{3,4,5}→{1,2,5}{3,4,5}右邊的這些解，就是扣除（1,1,1,1,0）之后，（Y1-1,Y2-1,Y3-1,Y4-1,Y5）的解。也就是說，對(duì)于任何（Y1-1,Y2-1,Y3-1,Y4,Y5-1）的最優(yōu)解都能轉(zhuǎn)化為（Y1-1,Y2-1,Y3-1,Y4-1,Y5）的一個(gè)解，那么對(duì)于在扣除4本書折扣組合的情況下，選擇（Y1-1,Y2-1,Y3-1,Y4-1,Y5）可以代表其他組合的解，即我們不用再考慮其他的可能，如（Y1-1,Y2-1,Y3-1,Y4,Y5-1）。其他同理，不再做具體討論。根據(jù)如上推理可以得到狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)化之后得到的（Y1-1,Y2-1,Y3-1,Y4-1,Y5）等可能不是“最小表示”，我們需要把它們轉(zhuǎn)化為對(duì)應(yīng)的最小表示。比如：從上面的表示公式中可以看出，整個(gè)動(dòng)態(tài)規(guī)劃的算法需要耗費(fèi)O（Y1×Y2×Y3×Y4×Y5）的空間來保存狀態(tài)的值，所需要的時(shí)間復(fù)雜度也為O（Y1×Y2×Y3×Y4×Y5）?？焖僬页龉收蠙C(jī)器關(guān)心數(shù)據(jù)挖掘和搜索引擎的程序員都知道，我們需要很多的計(jì)算機(jī)來存儲(chǔ)和處理海量數(shù)務(wù)質(zhì)量，我們需要保證每份數(shù)據(jù)都有多個(gè)備份。簡(jiǎn)單起見，我們假設(shè)一個(gè)機(jī)器僅儲(chǔ)存一個(gè)標(biāo)號(hào)為ID的記錄（假設(shè)ID是小于10億的整數(shù)），假設(shè)每份數(shù)據(jù)保存兩個(gè)備份，這樣就有兩個(gè)機(jī)器儲(chǔ)存了同樣的數(shù)據(jù)。ID一次的ID？如果已經(jīng)知道只有一臺(tái)機(jī)器死機(jī)（也就是說只有一個(gè)備份丟失）機(jī)呢（假設(shè)同一個(gè)數(shù)據(jù)的兩個(gè)備份不會(huì)同時(shí)丟失）？分析與解法解法一這個(gè)問題可以轉(zhuǎn)化成：有很多的ID，其中只有一個(gè)ID出現(xiàn)的次數(shù)小于2，其他正常ID出現(xiàn)的次數(shù)都等于2，問如何找到這個(gè)次數(shù)為1的ID。為了達(dá)到這個(gè)目的，最簡(jiǎn)單的辦法就是直接遍歷列表，利用一個(gè)數(shù)組記下每個(gè)ID出現(xiàn)的次數(shù)，遍歷完畢之后，出現(xiàn)次數(shù)小于2的ID就是我們想要的結(jié)果。假設(shè)有N個(gè)IDID取值在0～（N?1）之間，這個(gè)解法占用的時(shí)間復(fù)雜度為O（N），空間復(fù)雜度為O（N）。IDGB甚至幾十GB一步地減少空間復(fù)雜度呢？解法二仔細(xì)思考一下，哪些數(shù)據(jù)是不必存儲(chǔ)的呢？大部分的機(jī)器ID出現(xiàn)次數(shù)都等于2，這些ID的信息有必要嗎？我們可以利用這樣一個(gè)特性：ID出現(xiàn)次數(shù)等于2的機(jī)器肯定不是故障的機(jī)器，可以不予考慮。因此，可以把解法1數(shù)組中等于2的元素清空，然后用來存儲(chǔ)下一個(gè)機(jī)器ID的出現(xiàn)次數(shù)，這樣就可以減少需要的空間。具體方法如下：遍歷列表，利用哈希表記下每個(gè)ID出現(xiàn)的次數(shù)，每次遇見一個(gè)ID，就向哈希表中增加一個(gè)元素；如果這個(gè)ID出現(xiàn)的次數(shù)為2，那么就從哈希表中刪除這個(gè)ID，最后剩下的ID就是我們想要的結(jié)果。這個(gè)算法空間復(fù)雜度在最好情況下可以達(dá)到O（1），在最壞情況下仍然是O（N）。解法三前面的兩個(gè)算法的時(shí)間復(fù)雜度已經(jīng)達(dá)到了O（N），并且空間復(fù)雜度也已經(jīng)有了一定的突破，那么是否有可能進(jìn)一步提高算法的性能呢？分別從時(shí)間復(fù)雜度，空間復(fù)雜度方面考慮，時(shí)間復(fù)雜度上面很難有太大的突破。因?yàn)?，已?jīng)降到了O（N）這個(gè)規(guī)模了。那么，空間復(fù)雜度呢？如果想繼續(xù)降低空間復(fù)雜度，就要摒棄遍歷列表計(jì)數(shù)這種方法了，考慮采用完全不同的模式來計(jì)算。N加極端一點(diǎn)，是否可能使得空間復(fù)雜度降為O（1），歷列表的結(jié)果。如果這樣，我們可以把這個(gè)變量寫成：x（i）=f（list[0],list[1],…,list[i]），也就是說這個(gè)變量是已經(jīng)遍歷過的列表元素的函數(shù)。這個(gè)函數(shù)需要滿足的條件就是：x（N）=ID_Lost。也就說遍歷完整個(gè)列表后，這個(gè)變量的值應(yīng)該等于丟失備份的ID。我們需要做的就是尋找合適的f。顯然，f的形式不只一種。那么，我們可以先考慮找出一種可行的函數(shù)。對(duì)于第一問，我們已經(jīng)知道，列表中僅有一個(gè)ID出現(xiàn)了一次。那么，可以考慮使用異或關(guān)系來幫忙找到結(jié)果。因?yàn)閄⊕X=0且X⊕0=X，因此，可以把這個(gè)關(guān)系應(yīng)用到構(gòu)造這個(gè)函數(shù)上面。因?yàn)?，正確的機(jī)器都會(huì)有兩個(gè)ID，不正確的機(jī)器只有一個(gè)ID。所以所有ID的異或值就等于這個(gè)僅出現(xiàn)一次的ID（因?yàn)楫惢蜻\(yùn)算滿足交換律和結(jié)合律，其他出現(xiàn)兩次的ID異或完都為0）。這樣我們只使用一次遍歷運(yùn)算就得到了只有一臺(tái)故障機(jī)器情況下故障機(jī)器的ID。因此，就可以使用x（i）=list[0]⊕list[1]⊕…⊕list[i]來作為結(jié)果值。O（N），度為O（1）。對(duì)于第二問，由于有兩個(gè)ID僅出現(xiàn)了一次，設(shè)它們?yōu)锳和B，那么所有ID的異或值為A⊕B（道理同上面分析的一樣）。但還是無法確定A和B的值?？梢赃M(jìn)行分類討論：如果A=B，則A⊕B為0，也就是說丟失的是同一份數(shù)據(jù)的兩個(gè)拷貝，我們可以通過求和的方法得到A和B（A=B=（所有ID之和?所有正常工作機(jī)器ID之和）/2）。如果A⊕B不等于0，那么這個(gè)異或值的二進(jìn)制中某一位為1。顯然，A和B中有且僅有一個(gè)數(shù)的相同位上也為1。ID分成兩類，一類在這位上為1，另一類這位上為0。那么對(duì)于這兩類每一類分別含有A和B中的一個(gè)。那么我們使用兩個(gè)變量，在遍歷列表時(shí)，分別計(jì)算這兩類ID的異或和，即可得到A和B的值。解法四O（1），O（N），最優(yōu)。但對(duì)于第二問兩臺(tái)機(jī)器死機(jī)的情況，只能解決兩臺(tái)故障機(jī)器ID不同的情況，如果ID相同則無法解決。那如果需要考慮死機(jī)的兩臺(tái)機(jī)器ID相同的情況，還有沒有辦法解決呢？讓我們?cè)倩仡^仔細(xì)分析一下，這個(gè)問題可以抽象為：在一個(gè)事先預(yù)定的整數(shù)（ID）集合當(dāng)中，怎么樣找出其中丟失的一個(gè)數(shù)（ID）或者兩個(gè)數(shù)（ID）？讓我們回憶一下以前數(shù)學(xué)中的“不變量”的概念，就會(huì)發(fā)現(xiàn)所有機(jī)器ID的求和是一個(gè)固定的值，也就是我們所說的“不變量”?；蛟S這個(gè)“不變量”可以用來解決我們當(dāng)前的問題。如果只有一臺(tái)機(jī)器死機(jī)，相當(dāng)于我們這個(gè)ID集合里面少了一個(gè)ID，也就是說我們把剩下的ID求和，和所有ID的求和（“不變量”）的差就是當(dāng)前缺少的ID的數(shù)值！可以得到如下算法：預(yù)先計(jì)算并保存好所有ID的求和（“不變量”），順序列舉當(dāng)前所有剩下的ID，對(duì)它們求和，然后用所有ID的求和（“不變量”）減去當(dāng)前剩下所有ID的和，結(jié)IDID的求和（“不變量”）的檢測(cè)中只算一次，當(dāng)前算法的時(shí)間復(fù)雜度為O（N），空間復(fù)雜度為O（1），和解法三一樣是計(jì)算復(fù)雜度最優(yōu)的算法。對(duì)于第二問，我們考慮所有的情況，即兩個(gè)ID可以不同也可以相同。這時(shí)候就相當(dāng)于在ID的集合里面丟失了兩個(gè)ID。用上面的同樣方法我們只能得到這兩個(gè)ID的和，假設(shè)丟失的兩個(gè)ID分別是x和y，我們只能知道x+y的值，寫成x+y=a，并不能分辨x和y的值。顯然我們需要更多的信息來確定x和y要兩個(gè)方程才能求出解，我們現(xiàn)在只有一個(gè)，如果我們還能再構(gòu)造出一個(gè)關(guān)于x和y的方程，就能求出x和y的值?？赡茏x到這里，聰明的讀者已經(jīng)能構(gòu)造出第二個(gè)方程了。第二個(gè)方程有很多種構(gòu)造方法，這里提供一種供大家參考：我們?cè)儆靡粋€(gè)所有ID乘積的不變量，預(yù)先計(jì)算并保存好所有ID的乘積（“不變量”），順序列舉當(dāng)前所有剩下的ID，把他們乘起來得到乘積，然后用所有ID的乘積（“不變量”）除以當(dāng)前剩下所有ID的乘積，結(jié)果就是兩臺(tái)死機(jī)的機(jī)器ID的乘積，也就是xy的值，寫成xy=b。這樣我們通過聯(lián)立上面兩個(gè)方程x+y=a和xy=b，就可以計(jì)算出x和y的值。計(jì)算時(shí)間復(fù)雜度為O（N），空間復(fù)雜度為O（1）。當(dāng)然這里說的是一種理想的情況，聰明的讀者可能會(huì)發(fā)現(xiàn)這里有一個(gè)問題。因?yàn)镮D通常是一個(gè)比較大的整數(shù)，而機(jī)器ID的數(shù)量通常又比較多，產(chǎn)生的問題就是很多整數(shù)相乘結(jié)果可能會(huì)溢出。這點(diǎn)涉及實(shí)現(xiàn)的問題，我們就不多加討論了，其實(shí)也是有辦法可以避免的，比如不采用乘積的形式構(gòu)造第二個(gè)方程，而采用平方和的形式構(gòu)造第二個(gè)方程。擴(kuò)展問題如果所有的機(jī)器都有3個(gè)備份，也就是說同一ID的機(jī)器有3臺(tái)，而且同時(shí)又有3臺(tái)機(jī)器死機(jī)，還能用上面解法四的思路解決嗎？如果有N個(gè)備份，而且同時(shí)又有N臺(tái)機(jī)器死機(jī)，是否還能解決？相關(guān)問題這個(gè)問題本質(zhì)上也是從一堆數(shù)字中找到丟失的一個(gè)數(shù)字的問題。有這樣的一個(gè)撲克牌抽牌問題：“給你一副雜亂的撲克牌（不包括大小王），任意從其中抽出一張牌，怎樣用最簡(jiǎn)單的方法分析抽出的是1~13中的哪一張（不要求知道花色）”。飲料供貨在微軟亞洲研究院上班，大家早上來的第一件事是干啥呢？查看郵件？No，是去水房拿飲料：酸奶，豆?jié){，綠茶、王老吉、咖啡、可口可樂……（當(dāng)然，還是有很多同事把拿飲料當(dāng)成第二件事）。管理水房的阿姨們每天都會(huì)準(zhǔn)備很多的飲料給大家，為了提高服務(wù)質(zhì)量，她們會(huì)統(tǒng)計(jì)大家對(duì)每種飲料的滿意度。一段時(shí)間后，阿姨們已經(jīng)有了大批的數(shù)據(jù)。某天早上，當(dāng)實(shí)習(xí)生小飛第一個(gè)沖進(jìn)水房并一次拿了五瓶酸奶、四瓶王老吉、三瓶鮮橙多時(shí)，阿姨們逮住了他，要他幫忙。從阿姨們統(tǒng)計(jì)的數(shù)據(jù)中，小飛可以知道大家對(duì)每一種飲料的滿意度。阿姨們還告訴小飛，STC（SmartTeaCorp.）負(fù)責(zé)給研究院供應(yīng)飲料，每天總量為V。STC很神奇，他們提供的每種飲料之單個(gè)容量都是2的方冪，比如王老吉，都是23=8升的，可樂都是25=32升的。當(dāng)然STC的存貨也是有限的，這會(huì)是每種飲料購(gòu)買量的上限。統(tǒng)計(jì)數(shù)據(jù)中用飲料名字、容量、數(shù)量、滿意度描述每一種飲料。那么，小飛如何完成這個(gè)任務(wù)，求出保證最大滿意度的購(gòu)買量呢？分析與解法解法一我們先把這個(gè)問題“數(shù)學(xué)化”。假設(shè)STC共提供n種飲料，用（Si、Vi、Ci、Hi、Bi）（對(duì)應(yīng)的是飲料名字、容量、可能的最大數(shù)量、滿意度、實(shí)際購(gòu)買量）來表示第i種飲料（i=0,1,…,n-1），其中可能的最大數(shù)量指STC存貨的上限?；谌缟媳硎荆猴嬃峡?cè)萘繛?；總滿意度為 ；那么題目的要求就是，在滿足條件的基礎(chǔ)上，求解 。最優(yōu)化的問題，我們來看看動(dòng)態(tài)規(guī)劃能否解決。用Opt（V',i）表示從第i,i+1,i+2,…,n-1種飲料中，算出總量為V’的方案中滿意度之和的最大值。因此，Opt（V,n）就是我們要求的值。那么，我們可以列出如下的推導(dǎo)公式：Opt（V',i）=max{k×Hi+Op（tV'-Vi×k,i+1）}（k=0,1,…,Ci,i=0,1,…,n-1）。即：最優(yōu)化的結(jié)果=“選擇k個(gè)第i種飲料的滿意度+剩下部分不考慮第i種飲料的最優(yōu)化結(jié)果”的最大值。根據(jù)推導(dǎo)公式，我們列出如下的初始邊界條件：Opt（0,n）=0，即容量為0的情況下，最優(yōu)化結(jié)果為0；Opt（x,n）=-INF（x!=0）（–INF為負(fù)無窮大），即在容量不為0的情況下，把最優(yōu)化結(jié)果設(shè)為負(fù)無窮大，并把它作為初值。根據(jù)以上的推導(dǎo)公式，就不難列出動(dòng)態(tài)規(guī)劃求解代碼，如代碼清單1-9所示。代碼清單1-9在上面的算法中，空間復(fù)雜度為O（V×N），時(shí)間復(fù)雜度約為O（V×N×Max（Ci））。opt[i][j]opt[i][j+2]，只需要opt[i][j]和opt[i][j+1]，所以空間復(fù)雜度可以降為O（V）。解法二存在其相應(yīng)的記錄項(xiàng)中。若記錄項(xiàng)中存儲(chǔ)的已不是初始值，則表示該子問題已經(jīng)被計(jì)算過，此時(shí)只需要從記錄項(xiàng)中取出該子問題的解答即可。因此，我們可以應(yīng)用備忘錄法來進(jìn)一步提高算法的效率（如代碼清單1-10）。代碼清單1-10解法三請(qǐng)注意這個(gè)題目的限制條件，看看它能否給我們一些特殊的提示。我們把信息重新整理一下，按飲料的容量（單位為L(zhǎng)）排序：如上表，我們有n0種容量為20L的飲料，它們的數(shù)量和滿意度分別為（TC0_0,H0_0），（TC0_1,H0_1）……假設(shè)最大容量為2ML。一開始，如果V%（21）定需要購(gòu)買20L容量的飲料，至少一瓶。在這里可以使用貪心規(guī)則，購(gòu)買滿意度最高的一瓶。除去這個(gè)，我們只要再購(gòu)買總量（V-20）L的飲料就可以了。這時(shí)，如果我們要購(gòu)買21L21L容量里面滿意度最高的，我們還應(yīng)該考慮，兩個(gè)容量20L20L的飲料按滿意度從大到小排列，并用最大的兩個(gè)滿意度組合出一個(gè)新的“容量為2L”[11]的飲料。不斷地使用這樣貪心原則，即得解。這是不是就簡(jiǎn)單了很多呢？光影切割問題不少人很愛玩游戲，例如CS[12]，游戲設(shè)計(jì)也成為程序開發(fā)的熱點(diǎn)之一。我們假設(shè)要設(shè)計(jì)破舊倉(cāng)庫(kù)之類的場(chǎng)景作為戰(zhàn)爭(zhēng)游戲的背景，倉(cāng)庫(kù)的地面會(huì)因?yàn)殛?yáng)光從屋頂?shù)穆┒椿蛘叽翱谡丈溥M(jìn)來而形成許多光照區(qū)域和陰影區(qū)域。簡(jiǎn)單起見，假設(shè)不同區(qū)域的邊界都是直線[13]，我們把這些直線都叫做“光影線”，并假設(shè)沒有光影線是平行于Y軸的，且不存在三條光影線相交于一點(diǎn)的情況。如圖1-9所示。圖1-9倉(cāng)庫(kù)地面被光影分割成不同的區(qū)域那么，如果我們需要快速計(jì)算某個(gè)時(shí)刻，在X坐標(biāo)[A,B]區(qū)間的地板上被光影劃分成多少塊。如何設(shè)計(jì)算法？分析與解法解法一在分析問題之前，我們可以先研究一下圖形中不同線段之間的關(guān)系。在圖1-10中，每一條直線代表一條光影。那么，直線相交之后產(chǎn)生的分塊信息是否和直線的交點(diǎn)有直接的關(guān)系呢？圖1-10投影示意圖可以先通過分析比較簡(jiǎn)單的例子來得到一些規(guī)律。對(duì)于兩條直線的情況，如圖1-11所示。圖1-11直線分割示意圖顯然，兩條直線最多能把區(qū)間分劃為4個(gè)部分。對(duì)于三條直線，會(huì)有如下的情況，如圖1-12所示。圖1-12直線分割示意圖三條直線如果只有兩個(gè)交點(diǎn)，會(huì)把空間分成6個(gè)部分（圖1-12左）；如果有三個(gè)交點(diǎn)，會(huì)把空間分為7個(gè)部分（圖1-12右）。那么，如下規(guī)律可循：兩條直線→一個(gè)交點(diǎn)→空間分成4個(gè)部分三條直線→兩個(gè)交點(diǎn)→空間分成6個(gè)部分三條直線→三個(gè)交點(diǎn)→空間分成7個(gè)部分由上可以推出，每增加一條直線，如果增加m個(gè)交點(diǎn)，那么這條直線被新增加的m個(gè)交點(diǎn)，分成（m+1）段。每一段直線會(huì)將原來一塊區(qū)域分成兩塊，因此，新增加（m+1）新區(qū)域。如果總共有N條直線，M個(gè)交點(diǎn)，那么區(qū)域的數(shù)目為N+M+1。因此，平面被劃分成多少塊的問題可以轉(zhuǎn)化為直線的交點(diǎn)有多少個(gè)的問題。那么，將N條直線逐一投影到坐標(biāo)區(qū)間上，假設(shè)當(dāng)?shù)趉條直線投影到坐標(biāo)區(qū)間的時(shí)候，它與之前的k-1條直線的交點(diǎn)為Nk個(gè)，那么它使得區(qū)間[A,B]之間的平面塊增加Nk+1個(gè)（為什么），全部直線（N條）都投影完畢之后，我們可得到區(qū)間[A,B]平面被劃分的塊數(shù)，即 ，其中1為區(qū)間[A,B]的初始平面塊數(shù)。因此，只要求出所有直線兩兩相交的交點(diǎn)，然后再查找哪些交點(diǎn)在[A,B]之間，進(jìn)而就可以求出平面被劃分的塊數(shù)。我們可以考慮將N條直線的所有交點(diǎn)存儲(chǔ)于數(shù)組Intersect中，然后進(jìn)行計(jì)算。這樣，原問題就轉(zhuǎn)化成查找交點(diǎn)數(shù)組的問題了。需要對(duì)數(shù)組進(jìn)行初始化。初始化的過程，實(shí)質(zhì)上就是計(jì)算所有交點(diǎn)的過程。我們需要查詢每條直線是否與其他N-1條直線有交點(diǎn)，初始化的時(shí)間復(fù)雜度將為O（N2）。每次查詢的時(shí)間復(fù)雜度為O（|Intersect|）。如果在初始化后對(duì)所有交點(diǎn)按X軸坐標(biāo)排序，則復(fù)雜度為O（N2+|Intersect|×log|Intersect|），其中|Intersect|×log|Intersect|為排序時(shí)間，之后可采用二分查找，每次查詢的時(shí)間復(fù)雜度將為O（log|Intersect|）。解法二但是，如果查詢比較少，我們是否可以不浪費(fèi)那么多時(shí)間來預(yù)處理呢？圖1-13直線分割示意圖分析上面兩個(gè)情況（如圖1-13所示），左圖為有一個(gè)交點(diǎn)的情況，兩條直線a和b與左邊界的交點(diǎn)從上到下按順序?yàn)椋╝,b），右邊界上的交點(diǎn)順序?yàn)椋╞,a），可以看到，順序被反過來了，因?yàn)樗鼈冊(cè)趦蓚€(gè)邊界之間有一個(gè)交點(diǎn)。如果沒有交點(diǎn)，它們與邊界的交點(diǎn)順序則不會(huì)有變化。進(jìn)一步分析圖1-13的右圖可以知道，區(qū)域內(nèi)的交點(diǎn)數(shù)目就等于一個(gè)邊界上交點(diǎn)順序相對(duì)另一個(gè)邊界交點(diǎn)順序的逆序總數(shù)（這里利用到條件“沒有三條直線相交于一個(gè)點(diǎn)”）。在右圖中，左邊界順序?yàn)椋╝,b,c），右邊界為（c,b,a），假設(shè)a=1,b=2,c=3，那么（c,b,a）=（3,2,1），它的逆序數(shù)為3。因此，問題轉(zhuǎn)化為求一個(gè)N個(gè)元素的數(shù)組的逆序數(shù)（第三次對(duì)問題進(jìn)行了轉(zhuǎn)換）。最直接的求解逆序數(shù)方法還是O（N2），如果用分治的策略可以將時(shí)間復(fù)雜度降為O（N×log2N），求N個(gè)元素的逆序數(shù)的分治思想如下，首先求前N/2個(gè)元素的逆序數(shù)，再求后N/2個(gè)元素的逆序數(shù)，最后在排序過程中合并前后兩部分之間的逆序數(shù)。小結(jié)呢？小飛的電梯調(diào)度算法微軟亞洲研究院所在的希格瑪大廈一共有6部電梯。在高峰時(shí)間，每層都有人上下，電梯在每層都停。實(shí)習(xí)生小飛常常會(huì)被每層都停的電梯弄得很不耐煩，于是他提出了這樣一個(gè)辦法：由于樓層并不太高，那么在繁忙的上下班時(shí)間，每次電梯從一層往上走時(shí)，我們只允許電梯停在其中的某一層。所有的乘客都從一樓上電梯，到達(dá)某層樓后，電梯停下來，所有乘客再?gòu)倪@里爬樓梯到自己的目的層。在一樓的時(shí)候，每個(gè)乘客選擇自己的目的層，電梯則自動(dòng)計(jì)算出應(yīng)停的樓層。問：電梯停在哪一層樓，能夠保證這次乘坐電梯的所有乘客爬樓梯的層數(shù)之和最少。分析與解法該問題本質(zhì)上是一個(gè)優(yōu)化問題。首先為這個(gè)問題找到一個(gè)合適的抽象模型。從問題中可以看出，有兩個(gè)因素會(huì)影響到最后的結(jié)果：乘客的數(shù)目及需要停的目的樓層。因此，我們可以從統(tǒng)計(jì)到達(dá)各層的乘客數(shù)目開始分析。假設(shè)樓層總共有N層，電梯停在第x層，要去第i層的乘客數(shù)目總數(shù)為Tot[i]梯的總數(shù)就是。因此，我們就是要找到一個(gè)整數(shù)x，使得的值最小解法一首先考慮簡(jiǎn)單解法?？梢詮牡?層開始枚舉x一直到第N層，然后再計(jì)算出如果電梯在第x層樓停的話，所有乘客總共要爬多少層樓。這是最為直接的一個(gè)解法?？梢钥闯?，這個(gè)算法需要兩重循環(huán)來完成計(jì)算（偽代碼如清單1-1所示）。代碼清單1-11這個(gè)基本解法的時(shí)間復(fù)雜度為O（N2）。解法二我們希望盡可能地減少算法的時(shí)間復(fù)雜度。那么，是否有可能在低于O（N2）的規(guī)模下求出這個(gè)問題的解呢？我們可以進(jìn)一步地分析。假設(shè)電梯停在第i層樓，顯然我們可以計(jì)算出所有乘客總共要爬樓梯的層數(shù)Y。如果有N1個(gè)乘客目的樓層在第i層樓以下，有N2個(gè)乘客在第i層樓，還有N3個(gè)乘客在第i層樓以上。這個(gè)時(shí)候，如果電梯改停在i-1層，所有目的地在第i層及以上的乘客都需要多爬1層，總共需要多爬N2+N3層，而所有目的地在第i-1層及以下的乘客可以少爬1層，總共可以少爬N1層。因此，乘客總共需要爬的層數(shù)為Y-N1+（N2+N3）=Y-（N1-N2-N3）層。反之，如果電梯在i+1層停，那么乘客總共需要爬的層數(shù)為Y+（N1+N2-N3）層。由此可見，當(dāng)N1>N2+N3時(shí)，電梯在第i-1層樓停更好，乘客走的樓層數(shù)減少（N1-N2-N3）；而當(dāng)N1+N2<N3時(shí)，電梯在i+1層停更好；其他情況下，電梯停在第i層最好。根據(jù)這個(gè)規(guī)律，我們從第一層開始考察，計(jì)算各位乘客需要爬樓梯的數(shù)目。然后再根據(jù)上面的策略進(jìn)行調(diào)整，直到找到最佳樓層?？偟臅r(shí)間復(fù)雜度將降為O（N），代碼如清單1-12所示。代碼清單1-12擴(kuò)展問題往上爬樓梯，總是比往下走要累的。假設(shè)往上爬一個(gè)樓層，要耗費(fèi)k單位的能量，而往下走只需要耗費(fèi)1題怎么解決呢？這個(gè)問題可以用類似上面的分析方法來解答，因此筆者不再贅述，留給讀者自行解決。在一個(gè)高樓里面，電梯只在某一個(gè)樓層停，這個(gè)政策還是不太人性化。如果電梯會(huì)在k個(gè)樓層停呢？讀者可以發(fā)揮自己的想象力，看看如何尋找最優(yōu)方案。高效率地安排見面會(huì)在校園招聘的季節(jié)里，為了能讓學(xué)生們更好地了解微軟亞洲研究院各研究組的情況，HR部門計(jì)劃為每一個(gè)研究組舉辦一次見面會(huì)，讓各個(gè)研究組的員工能跟學(xué)生相互了解和交流（如圖1-14所示）。已知有n位學(xué)生，他們分別對(duì)m個(gè)研究組中的若干個(gè)感興趣。為了滿足所有學(xué)生的要求，HR希望每個(gè)學(xué)生都能參加自己感興趣的所有見面會(huì)。如果每個(gè)見面會(huì)的時(shí)間為t，那么，如何安排才能夠使得所有見面會(huì)的總時(shí)間最短？最簡(jiǎn)單的辦法，就是把m個(gè)研究組的見面會(huì)時(shí)間依次排開，那我們就要用m×t的總時(shí)間，我們有10多個(gè)研究小組，時(shí)間會(huì)拖得很長(zhǎng)，能否進(jìn)一步提高效率？圖1-14校園招聘開始了分析與解法這兩個(gè)研究小組感興趣，它們之間就沒有約束。我們可以想到利用圖模型來解決這個(gè)問題。我們把每個(gè)小組看成是一些散布的點(diǎn)。如果有一位同學(xué)同時(shí)對(duì)兩個(gè)小組感興趣，就在這兩個(gè)小組對(duì)應(yīng)的兩個(gè)點(diǎn)間加上一條邊。所以，如果某個(gè)同學(xué)同時(shí)對(duì)k個(gè)小組感興趣，那么這k個(gè)小組中任意兩個(gè)小組對(duì)應(yīng)的頂點(diǎn)之間都要有一條邊。例如，有兩位同學(xué)A和B，他們分別希望參加（1,2,3）和（1,3,4）小組的見面會(huì)。那么，根據(jù)上面的構(gòu)圖方法，我們可以得到下面的圖1-15。圖1-15參加見面會(huì)選擇示意圖見面會(huì)最少的時(shí)間安排就對(duì)應(yīng)于這個(gè)圖的最少著色問題。圖的最少著色問題可以這樣描述，對(duì)于一個(gè)圖G（E,V），試用最少的顏色為這個(gè)圖的頂點(diǎn)著色，使得?（vi,vj）∈E，有vi和vj顏色不同。這個(gè)問題至今沒有有效的算法，但可以用下面兩個(gè)思路求解。解法一對(duì)頂點(diǎn)1分配顏色1，然后對(duì)剩下的n-1個(gè)頂點(diǎn)枚舉其所有的顏色可能，再一一驗(yàn)證是否可以滿足我們的著色要求，枚舉的復(fù)雜度是O（（n?1）n），驗(yàn)證一種顏色配置是否滿足要求需要的時(shí)間復(fù)雜度是O（n2）。所以總共的時(shí)間復(fù)雜度是O（（n?1）nn2）。時(shí)間復(fù)雜度高，但是能夠保證得到正確的結(jié)果。算法的性能提高還在于使用有用的上下界函數(shù)剪枝來避免不必要的搜索。解法二我們可以嘗試對(duì)這個(gè)圖進(jìn)行K種著色，首先把K設(shè)為1，看看有沒有合適的方案，再逐漸把K提高。當(dāng)假設(shè)待求解的圖之最少著色數(shù)遠(yuǎn)小于圖的頂點(diǎn)數(shù)時(shí)，則這個(gè)方法的復(fù)雜度要遠(yuǎn)低于解法一。當(dāng)然，我們還可以用啟發(fā)式算法來得到一個(gè)近似解，而不是最優(yōu)解。擴(kuò)展問題問題一N行，它們的時(shí)間分別為[B[i],E[i]]（B[i]為面試開始時(shí)間，E[i]為面試結(jié)束時(shí)間）。假設(shè)一N如果你是微軟亞洲研究院的HR，現(xiàn)在給定這N個(gè)面試的時(shí)間之后，你能計(jì)算出至少需要多少個(gè)面試點(diǎn)嗎？請(qǐng)給出一個(gè)可行的方案。比如圖1-16有4個(gè)面試，分別在時(shí)間段[1,5],[2,3],[3,4],[3,6]進(jìn)行。圖1-16面試時(shí)間示意圖剛看完上面的建立圖模型思路的讀者可能會(huì)說，這道題也可以用圖模型求解啊。每場(chǎng)面試是一個(gè)頂點(diǎn)，如果兩場(chǎng)面試時(shí)間上有重疊，就用一條邊把它們連接起來。這樣，這個(gè)問題不也轉(zhuǎn)化成一個(gè)圖的最少著色問題了嗎？不錯(cuò)，還是同樣的模型。對(duì)于這個(gè)新的問題，能否在多項(xiàng)式時(shí)間復(fù)雜度內(nèi)求出解呢？路就是對(duì)于所有的面試I[i]=[B[i],E[i]]，按B[i]從小到大排序，然后按順序?qū)Ω鱾€(gè)區(qū)間著色。對(duì)當(dāng)前區(qū)間i著色時(shí)，必須保證所著的顏色（Color[i]）沒有被出現(xiàn)在這個(gè)區(qū)域之前且時(shí)間段與當(dāng)前區(qū)間有重疊的區(qū)間用到。假設(shè)面試的總數(shù)為N，那么相應(yīng)的代碼如清單1-13所示。代碼清單1-13nMaxColors就是最后返回的所需的最少顏色。isForbidden是對(duì)于每個(gè)時(shí)間區(qū)間i，其他時(shí)間區(qū)間j中開始時(shí)間位于這個(gè)時(shí)間區(qū)間之前的且與這個(gè)時(shí)間區(qū)間有重疊的面試所占用的顏色的標(biāo)識(shí)數(shù)組。Overlap函數(shù)，則是用來判斷兩個(gè)時(shí)間區(qū)間是否有重疊。通過簡(jiǎn)單分析，我們可以知道這個(gè)算法的時(shí)間復(fù)雜度是O（N2）。實(shí)際上，這個(gè)區(qū)間圖中每一個(gè)頂點(diǎn)所代表的時(shí)間區(qū)間，是在一個(gè)一維的時(shí)間軸上順序排列的。我們只需要找到這個(gè)時(shí)間軸上的某一個(gè)時(shí)間點(diǎn)，使包括這個(gè)時(shí)間點(diǎn)的時(shí)間區(qū)間個(gè)數(shù)最多（設(shè)為MaxI），那么這個(gè)MaxI就是我們要求的值。讀者可以自行證明，上面的多項(xiàng)式復(fù)雜度算法可以找到這個(gè)MaxI。而一個(gè)普通的圖，沒有這種在某個(gè)一維軸上順序排列的性質(zhì)，所以沒辦法用這種貪心算法得到最優(yōu)方案。此外，相信有些讀者已經(jīng)發(fā)現(xiàn)，在上述算法中，查找一個(gè)可行顏色的時(shí)候，我們遍歷了整個(gè)isForbidden數(shù)組。如果我們使用更高效的存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)（例如，堆），可以進(jìn)一步把時(shí)間復(fù)雜度降低到O（N×log2N）。B[i]、E[i]按大小排序，得到一個(gè)長(zhǎng)度為2×N的有序數(shù)組。然后我們遍歷這個(gè)數(shù)組，遇到一個(gè)B[i]，就把當(dāng)前已使用的顏色數(shù)目加1，在遇到對(duì)應(yīng)的E[i]時(shí)，就把當(dāng)前已經(jīng)使用的顏色數(shù)目減1多有多少種顏色正被使用（MaxColor），循環(huán)結(jié)束時(shí)，MaxColor就是我們需要的最少顏色數(shù)。這個(gè)算法的時(shí)間復(fù)雜度主要是由排序所影響，復(fù)雜度應(yīng)為O（N×log2N）。這個(gè)算法的代碼如清單1-14所示。代碼清單1-14問題二小飛看了時(shí)間安排，他發(fā)現(xiàn)自己感興趣的兩個(gè)研究小組的見面會(huì)分別被安排在同一天的第一個(gè)和最后一個(gè)，他覺得不爽，能不能在優(yōu)化總的見面會(huì)時(shí)間的基礎(chǔ)上，讓每個(gè)同學(xué)參加見面會(huì)的時(shí)間盡量集中？雙線程高效下載我們經(jīng)常需要編寫程序，從網(wǎng)絡(luò)上下載數(shù)據(jù)，然后存儲(chǔ)到硬盤上。一個(gè)簡(jiǎn)單的做法，就是下載一塊數(shù)據(jù)，寫入硬盤，然后再下載，再寫入硬盤……不斷重復(fù)這個(gè)過程，直到所有的內(nèi)容下載完畢為止。能否對(duì)此進(jìn)行優(yōu)化？我們不妨對(duì)問題做一些抽象和簡(jiǎn)化。Blockg_buffer[BUFFER_COUNT]假設(shè)兩個(gè)基本函數(shù)已經(jīng)實(shí)現(xiàn)（你可以假定兩個(gè)函數(shù)都能正常工作，不會(huì)拋出異常）：//downloadsablockfromInternetsequentiallyineachcall//returntrue,iftheentirefileisdownloaded,otherwisefalse.boolGetBlockFromNet（Block*out_block）;//writesablocktoharddiskboolWriteBlockToDisk（Block*in_block）;上述的想法可以用代碼清單1-15代碼清單1-15while（true）{boolisDownloadCompleted;isDownloadCompleted=GetBlockFromNet（g_buffer）;WriteBlockToDisk（g_buffer）;if（isDownloadCompleted）break;}可以看到，在上述方法中，我們要下載完一塊數(shù)據(jù)之后才能寫入硬盤。下載數(shù)據(jù)和寫入硬盤的過程是串行的。為了提高效率，我們希望能夠設(shè)計(jì)兩個(gè)線程，使得下載和寫硬盤能并行進(jìn)行。線程A：從網(wǎng)絡(luò)中讀取一個(gè)數(shù)據(jù)塊，存儲(chǔ)到內(nèi)存的緩存中。線程B：從緩存中讀取內(nèi)容，存儲(chǔ)到文件中。試實(shí)現(xiàn)如下子程序：初始化部分線程A線程B你可以使用下面的多線程API（如代碼清單1-16）。代碼清單1-16L1I/OL2的性能問題，并考慮是否還有其他改進(jìn)的設(shè)計(jì)方法？分析與解法這道題目出現(xiàn)在2007年微軟校園招聘的筆試中。出題者為了讓不同知識(shí)背景的同學(xué)都能發(fā)揮水平，特地提供了詳細(xì)的說明。這樣，沒有接觸過實(shí)際的Windows多線程編程的同學(xué)也能寫出代碼?，F(xiàn)在越來越多的電腦采用雙核甚至是多核的體系結(jié)構(gòu)，并行計(jì)算會(huì)成為常用的程序工作模式。這道題只是一個(gè)簡(jiǎn)單的例子。在實(shí)際工作中，程序員經(jīng)常要依靠已有的模塊和API完成任務(wù)，這些模塊也許只有簡(jiǎn)單的接口說明，沒有源代碼。在這種情況下能夠高效地完成任務(wù)，也是優(yōu)秀程序員的特質(zhì)之一。我們需要使用兩個(gè)線程來完成從網(wǎng)絡(luò)上下載數(shù)據(jù)并存儲(chǔ)到硬盤上的過程。下載線程和存儲(chǔ)線程共享一個(gè)全局緩存區(qū)，我們需要協(xié)調(diào)兩個(gè)線程的工作。下面若干因素是我們要重點(diǎn)考慮的。什么時(shí)候才算完成任務(wù)？候，兩個(gè)線程才能正常終止。為了提高效率，希望兩個(gè)線程能盡可能地同時(shí)工作。如果使用Mutex，下載和存儲(chǔ)線程將不能同時(shí)工作。因此，Semaphore是更好的選擇[14]。下載和存儲(chǔ)線程工作的必要條件如下。如果共享緩存區(qū)已滿，沒有緩沖空間來存儲(chǔ)下載的內(nèi)容，則應(yīng)該暫停下載。如果所有的內(nèi)容都已經(jīng)下載完畢，也沒必要繼續(xù)下載。如果緩存區(qū)為空，則沒必要運(yùn)行存儲(chǔ)線程。進(jìn)一步，如果下載工作已經(jīng)完成，存儲(chǔ)線程也可以結(jié)束了。共享緩存區(qū)的數(shù)據(jù)結(jié)構(gòu)。下載線程和存儲(chǔ)線程工作的過程是“先進(jìn)先出”，先下載的內(nèi)容要先存儲(chǔ)，這樣才能保證內(nèi)容的正確順序。“先進(jìn)先出”的典型數(shù)據(jù)結(jié)構(gòu)是隊(duì)列。由于我們采用了固定的緩沖空間來保存下載的內(nèi)容，循環(huán)隊(duì)列會(huì)是一個(gè)很好的選擇。綜合考慮上面的因素，調(diào)用題目提供的API可以得到下面這個(gè)可供參考的偽代碼（如代碼清單1-17所示）。代碼清單1-17上面的偽代碼中，ProcAProcBL1I/OL2，那么這個(gè)多線程程序執(zhí)行的時(shí)間約為Max（L1,L2）。尤其是需要下載的內(nèi)容很多的時(shí)候，基本可以保證兩個(gè)線程是流水線工作。而在單線程的情況下，需要的時(shí)間是L1+L2。如果網(wǎng)絡(luò)延遲遠(yuǎn)大于I/O存儲(chǔ)延遲，則多個(gè)下載線程的設(shè)計(jì)將可以進(jìn)一步改善性能。但也將帶來一些更復(fù)雜的問題。多個(gè)下載線程和存儲(chǔ)線程之間如何協(xié)同工作呢？這個(gè)問題留給讀者思考。微軟亞洲研究院的研發(fā)主管鄒欣曾經(jīng)參加過多個(gè)版本MicrosoftOutlook的開發(fā)，他提供了這個(gè)題目，并且講了下面的故事。在Outlook和Exchange服務(wù)器連接的情況下，Outlook需要下載一系列的“離線地址簿文件”（OAB,OfflineAddressBook）以支持Outlook在離線的情況下還能正常地搜索到公司所有E-mail用戶和用戶組的信息。這個(gè)文件相當(dāng)大，對(duì)于Microsoft這樣的公司來說，大概有300MB~500MB，原來的算法是單線程的（正如題目所示），運(yùn)行要花很長(zhǎng)時(shí)間，用戶天后，同事們高興地反映，新的版本的確快多了！但是又有另兩位同事抱怨，這個(gè)功能太“狠”了，在筆記本電腦上，Outlook像瘋了一樣地寫硬盤，他們都做不了其他事情！后慢速度，如果發(fā)現(xiàn)用戶在幾秒鐘內(nèi)沒有鼠標(biāo)、鍵盤的輸入，那雙線程會(huì)逐漸恢復(fù)高速運(yùn)行。從那以后，我就再也沒有聽到類似的抱怨了。也許提高程序效能（performance）的最高境界，就是把事情做了，同時(shí)又不讓用戶感覺到程序在費(fèi)力地做事情。最近發(fā)布的Windows桌面搜索（DesktopSearch）也有類似的“人性化”功能，如果你正在使用電腦，它會(huì)提示“Indexspeedisreducedwhileyou'reusingthecomputer”，那么Windows中的哪些API能了解用戶是否在使用鼠標(biāo)或者鍵盤呢？這個(gè)問題留給讀者去探索。NIM（1）一排石頭的游戲面試是一個(gè)讓面試雙方互相增進(jìn)了解的過程，不一定總是你問我答，有時(shí)候兩人可以玩一些游戲，比如：N塊石頭排成一行，每塊石頭有各自固定的位置（如圖1-17所示）。兩個(gè)玩家依次取石頭，每個(gè)玩家每次可以取其中任意一塊石頭，或者相鄰的兩塊石頭，石頭在游戲過程中不能移位（即編號(hào)不會(huì)改變），最后能將剩下的石頭一次取光的玩家獲勝。這個(gè)游戲有必勝策略嗎？圖1-17一排石頭的位置分析與解法初看這個(gè)游戲，感覺輸贏似乎只是運(yùn)氣問題。但是我們通過深入分析，還是可以發(fā)現(xiàn)一些規(guī)律的。注意游戲中“相連”這個(gè)條件，若給N塊石頭從1到N依次編號(hào)，則我們只能取編號(hào)相連的兩塊石頭，例如可以同時(shí)取編號(hào)為1和2的兩塊石頭，但不能同時(shí)取編號(hào)為1和3的兩塊石頭，以此類推。當(dāng)題目中有“N個(gè)”之類的字眼出現(xiàn)時(shí)，我們往往可以從討論一些簡(jiǎn)單的特例出發(fā)，進(jìn)而逐漸掌握解題的規(guī)律：石頭的數(shù)目N=1或者N=2即只有一塊或者兩塊石頭，先取者即可一次取完所有的石頭而獲勝。石頭的數(shù)目N=3設(shè)三塊石頭排成一行，其編號(hào)依次為1、2、3（如圖1-18所示），那么先