簡(jiǎn)介這是《數(shù)據(jù)結(jié)構(gòu)與算法分析Java語(yǔ)言描述》第三版配套的習(xí)題答案文檔面向正在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的計(jì)算機(jī)專業(yè)學(xué)生、考研備考者以及需要鞏固Java算法基礎(chǔ)的開(kāi)發(fā)者。內(nèi)容覆蓋教材第一章的核心練習(xí)包含英文原版習(xí)題的完整解答過(guò)程資源包內(nèi)含1個(gè)docx文檔大小約1.52MB方便閱讀、批注與打印。已有2429人學(xué)習(xí)下載。文檔詳細(xì)解答了文件處理、遞歸算法、數(shù)學(xué)歸納法證明、數(shù)列求和、模運(yùn)算及大O符號(hào)估計(jì)等經(jīng)典題目例如processFile方法的遞歸實(shí)現(xiàn)、ones(int n)的二進(jìn)制位數(shù)求和以及對(duì)對(duì)數(shù)性質(zhì)的歸納證明通過(guò)逐題研讀可深入理解算法分析中的數(shù)學(xué)推導(dǎo)方法與復(fù)雜度估計(jì)思路。1. 數(shù)據(jù)結(jié)構(gòu)與算法分析Java語(yǔ)言描述第三版習(xí)題答案一份能直接照跑的解題參考數(shù)據(jù)結(jié)構(gòu)與算法分析Java語(yǔ)言描述第三版是很多軟件專業(yè)學(xué)生的噩夢(mèng)來(lái)源——教材好買(mǎi)課后題答案卻只能靠同學(xué)口口相傳網(wǎng)上流傳的版本還經(jīng)常缺章少頁(yè)。這份docx把前三章的習(xí)題解答完整整理了出來(lái)從遞歸函數(shù)、數(shù)學(xué)歸納法證明到復(fù)雜度排序、鏈表節(jié)點(diǎn)交換覆蓋的正是最容易被卡住的章節(jié)。它不是給每道題貼一句結(jié)論而是給出能直接編譯運(yùn)行的Java代碼和完整推導(dǎo)過(guò)程適合正在啃課本的在校生、準(zhǔn)備Java面試的開(kāi)發(fā)者以及想自己動(dòng)手驗(yàn)證算法結(jié)論的自學(xué)者。如果你也被一道歸納題卡了兩小時(shí)這份答案能省下大把翻論壇的時(shí)間。2. 第一章答案拆解遞歸寫(xiě)法、數(shù)學(xué)歸納法與數(shù)列求和實(shí)用技巧2.1 遞歸兩件套processFile與ones(int n)習(xí)題1.4講的是帶#include指令的文件遞歸處理。它的解法是一段典型的遞歸下降邏輯processFile( fileName ): 打開(kāi) fileName 逐行讀取 如果當(dāng)前行是 #include SomeFile: 遞歸調(diào)用 processFile( SomeFile ) 處理當(dāng)前文件內(nèi)容 關(guān)閉文件這段描述說(shuō)明了文件I/O里最常見(jiàn)的遞歸場(chǎng)景嵌套包含的頭文件無(wú)法用單層循環(huán)解決因?yàn)榘疃炔淮_定而遞歸天然匹配這個(gè)“未知深度”的樹(shù)形結(jié)構(gòu)。更關(guān)鍵的是題目里提到的自引用檢測(cè)——維護(hù)一個(gè)“尚未結(jié)束處理”的文件列表進(jìn)入遞歸前先查這個(gè)列表重復(fù)出現(xiàn)就說(shuō)明存在循環(huán)包含得立刻終止。實(shí)際做代碼靜態(tài)掃描時(shí)這個(gè)列表通常用HashSet存文件絕對(duì)路徑遇到重復(fù)路徑直接跳過(guò)否則會(huì)無(wú)限遞歸棧溢出。習(xí)題1.5是另一個(gè)更純粹的遞歸例子計(jì)算一個(gè)整數(shù)二進(jìn)制表示中1的個(gè)數(shù)public static int ones(int n) { if (n 2) { return n; } return n % 2 ones(n / 2); }邏輯說(shuō)明n % 2取出最低位n / 2把整數(shù)右移一位遞歸累加每一位的值。以ones(13)為例13的二進(jìn)制是110113%21遞歸66%20遞歸33%21遞歸112直接返回1合計(jì)10113。這個(gè)遞歸深度等于二進(jìn)制位數(shù)所以時(shí)間復(fù)雜度是O(log n)。參數(shù)說(shuō)明n按非負(fù)整數(shù)設(shè)計(jì)。如果你把負(fù)數(shù)傳進(jìn)來(lái)Java的/2向零取整-1%2結(jié)果是-1而不是1返回值會(huì)違背“二進(jìn)制中1的個(gè)數(shù)”的定義同樣的邏輯用Python跑取余結(jié)果又不一樣。這就是跨語(yǔ)言移植的第一個(gè)坑——遞歸的數(shù)學(xué)語(yǔ)義在Java里要謹(jǐn)慎對(duì)待負(fù)數(shù)邊界。2.2 數(shù)學(xué)歸納法從log X X到斐波那契上界習(xí)題1.7(a)要證明log X X對(duì)X0恒成立。答案用的歸納結(jié)構(gòu)值得反復(fù)看先驗(yàn)證0X≤1區(qū)間此時(shí)log X≤0顯然小于X再驗(yàn)證1X≤2log X≤1≤X然后假設(shè)pX≤2p區(qū)間成立推導(dǎo)2pY≤4p區(qū)間log Y 1 log(Y/2)而Y/2落在(p, 2p]內(nèi)由歸納假設(shè)log(Y/2) Y/2所以log Y 1 Y/2 ≤ Y/2 Y/2 Y。這個(gè)“區(qū)間倍增、區(qū)間覆蓋”的思路比直接對(duì)X放縮更嚴(yán)謹(jǐn)因?yàn)閘og X在接近0處是負(fù)無(wú)窮直接證明很麻煩。習(xí)題1.11(b)的斐波那契上界F_k φ^kφ為黃金比例也用了歸納法但技巧性更強(qiáng)。關(guān)鍵觀察是φ滿足φ 1 φ2變形得φ?1 φ?2 1。歸納步驟F_{k1} F_k F_{k-1} φ^k φ^(k-1) φ^(k1)(φ?1 φ?2) φ^(k1)第三節(jié)習(xí)題1.10的模運(yùn)算題還展示了快速冪的數(shù)學(xué)基礎(chǔ)2?16≡1 (mod 5)所以21??(2?)2?≡12?≡1 (mod 5)。這種“先找循環(huán)節(jié)再取?！钡氖址ㄔ诤竺鎸W(xué)快速冪算法時(shí)會(huì)反復(fù)遇到。2.3 錯(cuò)位相減從4/3到20/27的數(shù)列求和推導(dǎo)習(xí)題1.8是這份答案里最容易讓人看得一頭霧水的地方因?yàn)閐ocx排版把公式拆散了。理順之后其實(shí)是標(biāo)準(zhǔn)的錯(cuò)位相減鏈。先看基礎(chǔ)公式Σ_{i0}^∞ 1/4^i 4/3基于這個(gè)結(jié)果求S Σ_{i1}^∞ i/4^i。列兩個(gè)等式S 1/4 2/16 3/64 … 4S 1 2/4 3/16 4/64 …用4S - S錯(cuò)位相減左邊得3S右邊除了首項(xiàng)1之外剩下的就是Σ_{i1}^∞ 1/4^i 1/3。所以3S 1 1/3 4/3S 4/9。繼續(xù)求Σ_{i1}^∞ i2/4^i同樣設(shè)它為S做4S - S后得到3S 1 3/4 5/16 7/64 …把右邊拆成1 Σ(2i1)/4^i再利用Σi/4^i 4/9和Σ1/4^i 1/3算出3S 1 8/9 1/3 20/9S 20/27。習(xí)題1.12的平方和、立方和公式同樣可以用歸納法或直接代數(shù)推導(dǎo)完成答案里給出的是歸納版本平方和Σ(2i-1)N2立方和Σi3(N(N1)/2)2。這里有個(gè)經(jīng)驗(yàn)遇到這種被排版打亂的公式先按題目編號(hào)回到教材原題確認(rèn)求和符號(hào)的上下標(biāo)再按“列等式、錯(cuò)位相減、拆項(xiàng)”三步走基本都能復(fù)原。文檔里的推導(dǎo)對(duì)錯(cuò)判斷標(biāo)準(zhǔn)很簡(jiǎn)單——最終結(jié)果代回去能不能自洽。3. 第二章算法分析答案詳解復(fù)雜度排序、運(yùn)行時(shí)間推算與循環(huán)陷阱3.1 復(fù)雜度函數(shù)排序記住這張表習(xí)題2.1給出一串函數(shù)要求按增長(zhǎng)率從小到大排列。答案的排序是序號(hào)函數(shù)說(shuō)明12/N, 37常數(shù)級(jí)2/N隨N增大趨近于02√N(yùn)低于任何多項(xiàng)式N^kk0.5時(shí)3N線性4N log log N比線性略高5N log N, N log(N2)同階log(N2)2logN常數(shù)可忽略6N log2N比N log N高一個(gè)log因子7N^1.5介于N log2N和N2之間8N2, N2 logN平方級(jí)9N3立方級(jí)102^(N/2), 2^N指數(shù)級(jí)判斷這類排序題核心規(guī)則只有三條多項(xiàng)式之間比最高次冪對(duì)數(shù)函數(shù)比任何正次冪增長(zhǎng)慢指數(shù)函數(shù)比任何多項(xiàng)式增長(zhǎng)快。最容易錯(cuò)的是N log N和N log(N2)很多人以為后者更快其實(shí)差一個(gè)常數(shù)2漸近上完全同階。排序結(jié)果怎么驗(yàn)證直接取N10?代進(jìn)去算近似值或者畫(huà)一張雙對(duì)數(shù)坐標(biāo)圖立刻能看出哪幾個(gè)函數(shù)擠在一起。面試?yán)飭?wèn)“N log N和N log(N2)誰(shuí)增長(zhǎng)快”是經(jīng)典陷阱答案是“一樣快”。3.2 運(yùn)行時(shí)間推算從0.5ms到62.5ms的直覺(jué)建立習(xí)題2.11假設(shè)某算法處理當(dāng)前輸入耗時(shí)0.5ms輸入規(guī)模擴(kuò)大5倍問(wèn)各復(fù)雜度下的新耗時(shí)復(fù)雜度計(jì)算新耗時(shí)O(N)0.5 × 52.5 msO(N log N)0.5 × 5 × (log5N / logN)略大于2.5 msO(N2)0.5 × 2512.5 msO(N3)0.5 × 12562.5 ms這里的O(N log N)項(xiàng)沒(méi)法給精確倍數(shù)因?yàn)閘og5N/logN和N有關(guān)。N越小這個(gè)比值越大N趨近無(wú)窮時(shí)它趨近1。實(shí)際工作中我一般估算成“比線性倍率大一點(diǎn)點(diǎn)”如果面試官追問(wèn)就給出這個(gè)公式。習(xí)題2.12反過(guò)來(lái)問(wèn)時(shí)間限制擴(kuò)大12000倍輸入規(guī)模能擴(kuò)大多少答案分別是線性擴(kuò)大12000倍平方級(jí)擴(kuò)大√12000≈109.54倍立方級(jí)擴(kuò)大12000^(1/3)≈22.9倍N log N級(jí)別答案是“約425000”——但要注意這不是固定倍率它依賴基線N。假設(shè)基線N100N log N約664時(shí)間擴(kuò)大12000倍后要解M log M ≈ 664×12000M才約等于425000。理解這點(diǎn)比背數(shù)字重要因?yàn)檎鎸?shí)系統(tǒng)的性能估算永遠(yuǎn)依賴當(dāng)前基線的位置。3.3 六段代碼復(fù)雜度循環(huán)層數(shù)相乘為什么翻車習(xí)題2.7給了六段循環(huán)嵌套代碼答案是嚴(yán)肅的算法分析訓(xùn)練?？焖僬f(shuō)結(jié)論代碼段外層中層內(nèi)層實(shí)際復(fù)雜度IN無(wú)無(wú)O(N)IINN無(wú)O(N2)IIINNNO(N3)IVN/2N無(wú)O(N2)VNi2jO(N?)VINNNO(N?)最值得展開(kāi)的是VI。它的三層循環(huán)每一層都到N但內(nèi)層有一句if條件只有條件成立才進(jìn)入最內(nèi)層的O(N)操作。答案說(shuō)這個(gè)條件總共只成立O(N2)次所以總時(shí)間是O(N2)×O(N)O(N?)而不是O(N?)。這就是“循環(huán)層數(shù)相乘”的局限——它只在所有分支等概率進(jìn)入時(shí)成立。遇到帶條件的內(nèi)層循環(huán)必須統(tǒng)計(jì)條件成立次數(shù)而不是直接數(shù)循環(huán)層數(shù)。這道題在面試?yán)镆渤Ｗ凅w出現(xiàn)一個(gè)看起來(lái)O(N3)的三重循環(huán)因?yàn)橐粋€(gè)if (ij k)硬生生變成O(N2)考察的就是你會(huì)不會(huì)用條件頻率代替循環(huán)深度。3.4 隨機(jī)排列與有序矩陣搜索從洗牌到線性掃描習(xí)題2.8討論三種生成隨機(jī)排列的算法。第一種逐位隨機(jī)生成重復(fù)就重試期望復(fù)雜度O(N2 log N)第二種用集合維護(hù)已選元素降到O(N log N)第三種是Fisher-Yates洗牌的變體線性完成。答案特別指出如果洗牌算法里把swap(a[i], a[randint(i, n-1)])改成randint(0, n-1)均勻性會(huì)立刻被破壞。證明方式很巧妙——N3時(shí)randint(0,2)共有27種等概率交換序列而6個(gè)排列無(wú)法被27整除所以排列不可能是等概率的。習(xí)題2.27是有序矩陣搜索矩陣每行每列都遞增從右上角開(kāi)始當(dāng)前值大于目標(biāo)就左移小于目標(biāo)就下移最多NM次比較。這是一道高頻面試題比二分查找更考察“利用有序性”的思維。習(xí)題2.28的最大差值問(wèn)題則是一維掃描的經(jīng)典——維護(hù)掃描到當(dāng)前位置前的最小值用當(dāng)前值減最小值更新答案一趟O(N)收工。這兩道題在答案里都給了完整推演建議直接背下來(lái)當(dāng)模板。4. 第三章鏈表答案實(shí)戰(zhàn)printLots、節(jié)點(diǎn)交換、交集并集與Josephus問(wèn)題4.1 printLots(L, P)同步推進(jìn)兩個(gè)迭代器習(xí)題3.1要求打印鏈表L中由位置列表P指定的所有元素且P中的位置是遞增的。答案用兩個(gè)迭代器同步推進(jìn)避免了每次從頭遍歷鏈表import java.util.Iterator; import java.util.List; public static AnyType void printLots(ListAnyType L, ListInteger P) { IteratorAnyType iterL L.iterator(); IteratorInteger iterP P.iterator(); AnyType itemL null; Integer itemP 0; int start 0; while (iterL.hasNext() iterP.hasNext()) { itemP iterP.next(); System.out.println(Looking for position itemP); while (start itemP iterL.hasNext()) { start; itemL iterL.next(); } System.out.println(itemL); } }邏輯說(shuō)明iterP每次取一個(gè)位置itemPiterL在內(nèi)層循環(huán)里推進(jìn)itemP - start步把start更新到當(dāng)前位置。兩個(gè)迭代器都只往一個(gè)方向走總體代價(jià)是O(|L| |P|)而不是O(|L|×|P|)。要注意P必須遞增如果P是無(wú)序列表這個(gè)算法直接失效得改用哈希表緩存下標(biāo)。邊界條件需要注意當(dāng)itemP超過(guò)鏈表長(zhǎng)度時(shí)內(nèi)層循環(huán)會(huì)因iterL.hasNext()為false而退出此時(shí)itemL是鏈表的最后一個(gè)節(jié)點(diǎn)會(huì)被重復(fù)打印。嚴(yán)格的做法是在內(nèi)層循環(huán)結(jié)束后判斷start itemP是否成立不成立就說(shuō)明位置越界。答案省略了這個(gè)保護(hù)實(shí)際復(fù)用時(shí)要自己加。4.2 swapWithNext單鏈表與雙鏈表的指針重連習(xí)題3.2要求交換相鄰兩個(gè)節(jié)點(diǎn)。單鏈表的做法是操作待交換節(jié)點(diǎn)的前驅(qū)beforeppublic static void swapWithNext(Node beforep) { Node p beforep.next; Node afterp p.next; // p和afterp假定都不為null p.next afterp.next; beforep.next afterp; afterp.next p; }雙鏈表版本則需要同時(shí)維護(hù)prev和next答案的寫(xiě)法是public static void swapWithNext(Node p) { Node beforep p.prev; Node afterp p.next; p.next afterp.next; beforep.next afterp; afterp.next p; p.next.prev p; p.prev afterp; afterp.prev beforep; }邏輯說(shuō)明雙鏈表交換的頭疼之處在于四個(gè)方向都要斷鏈。p.next afterp.next先把p的后繼接到afterp后面p.next.prev p把p的新后繼的prev指回pafterp.prev beforep讓afterp的prev指向beforep之后beforep.next afterp和afterp.next p完成剩余兩處連接。順序可以微調(diào)但最后一步一定是補(bǔ)p.prev afterp否則p的prev還指著afterp下次遍歷會(huì)死循環(huán)。兩個(gè)版本都沒(méi)做空指針檢查。如果在鏈表的tail上調(diào)用雙鏈表版本afterp.next是nullp.next.prev p會(huì)空指針。真正放進(jìn)生產(chǎn)代碼前必須加判空或者約定“禁止對(duì)尾節(jié)點(diǎn)調(diào)用此方法”。4.3 intersection與union有序表合并的統(tǒng)一模板習(xí)題3.4和3.5是配套題分別求兩個(gè)有序鏈表的交集和并集。交集的答案核心是二路歸并public static AnyType extends Comparable? super AnyType void intersection(ListAnyType L1, ListAnyType L2, ListAnyType Intersect) { ListIteratorAnyType iterL1 L1.listIterator(); ListIteratorAnyType iterL2 L2.listIterator(); AnyType itemL1 null, itemL2 null; if (iterL1.hasNext() iterL2.hasNext()) { itemL1 iterL1.next(); itemL2 iterL2.next(); } while (itemL1 ! null itemL2 ! null) { int compareResult itemL1.compareTo(itemL2); if (compareResult 0) { Intersect.add(itemL1); itemL1 iterL1.hasNext() ? iterL1.next() : null; itemL2 iterL2.hasNext() ? iterL2.next() : null; } else if (compareResult 0) { itemL1 iterL1.hasNext() ? iterL1.next() : null; } else { itemL2 iterL2.hasNext() ? iterL2.next() : null; } } }邏輯說(shuō)明compareTo返回負(fù)值說(shuō)明L1的元素小鏈表L1推進(jìn)正值說(shuō)明L2的小鏈表L2推進(jìn)相等則收入結(jié)果集、兩邊同時(shí)推進(jìn)。整個(gè)過(guò)程和歸并排序的merge階段一模一樣。并集版本只在分支處理上不同相等時(shí)加一個(gè)并推進(jìn)兩邊不等時(shí)加較小的那個(gè)再推進(jìn)對(duì)應(yīng)鏈表。這里有個(gè)容易被忽略的細(xì)節(jié)extends Comparable? super AnyType這個(gè)泛型約束不是裝飾它允許AnyType自身實(shí)現(xiàn)Comparable也允許它的父類實(shí)現(xiàn)Comparable。實(shí)際工程里如果你定義了一個(gè)子類繼承字符串包裝類這個(gè)約束能在編譯期就兜住類型不匹配。題目答案里反復(fù)出現(xiàn)這個(gè)簽名值得在IDE里敲一遍體會(huì)它的作用。4.4 Josephus問(wèn)題從M mod N到反向搜索習(xí)題3.6的Josephus問(wèn)題是鏈表章節(jié)的壓軸題N個(gè)人圍成一圈每數(shù)到M就刪除問(wèn)最后留下誰(shuí)。最樸素的做法是每次都從頭遍歷M步總復(fù)雜度O(N·M)。答案給出兩個(gè)實(shí)用改進(jìn)。第一個(gè)改進(jìn)是M mod N當(dāng)M大于當(dāng)前剩余人數(shù)時(shí)繞圈多走的完整圈數(shù)沒(méi)有意義取?？梢员苊獯罅繜o(wú)效遍歷。第二個(gè)改進(jìn)是反向搜索當(dāng)M超過(guò)剩余人數(shù)的一半時(shí)從當(dāng)前位置往前找N - M步等價(jià)于往后找M步。這兩個(gè)改進(jìn)疊加后最壞時(shí)間復(fù)雜度是O(N·min(M, N))但多數(shù)情況下遠(yuǎn)快于這個(gè)上界。實(shí)際寫(xiě)的時(shí)候還要補(bǔ)一層邊界處理M1時(shí)直接刪頭節(jié)點(diǎn)即可O(1)N1時(shí)連刪除都不用做。典型的翻車現(xiàn)場(chǎng)是把M mod N寫(xiě)錯(cuò)成M % size但size在刪除過(guò)程中不斷變化取模時(shí)機(jī)不同結(jié)果就不同。正確做法是每次刪除前用最新size取模而不是只在開(kāi)始時(shí)取一次。5. 避坑指南習(xí)題答案在學(xué)習(xí)與復(fù)現(xiàn)時(shí)最容易翻車的四個(gè)細(xì)節(jié)5.1 公式亂碼與排版拆解現(xiàn)象docx里出現(xiàn)“4S ? 1 ? 2 ? 3 ?.442”這種斷行亂碼連求和符號(hào)都被拆成碎片。原因原文檔排版時(shí)混用了公式編輯器域代碼和普通文本不同軟件渲染時(shí)對(duì)上下標(biāo)、分?jǐn)?shù)線的支持不一致尤其用在線預(yù)覽或文本編輯器打開(kāi)時(shí)幾乎必亂。解決用Office或WPS打開(kāi)不要用記事本類的工具。遇到亂碼公式根據(jù)題號(hào)回到教材原題對(duì)照按“列出等式、錯(cuò)位相減、代入已知結(jié)果”三步自己重推一遍比盯著亂碼猜要快得多。5.2 泛型代碼缺import導(dǎo)致編譯失敗現(xiàn)象直接復(fù)制3.1節(jié)的printLots代碼javac報(bào)“找不到List”或“找不到Iterator”。原因答案文檔省略了import java.util.*。這在競(jìng)賽代碼里常見(jiàn)但直接照抄到IDE里必然編譯失敗。解決開(kāi)頭補(bǔ)全三行import java.util.List;、import java.util.Iterator;、import java.util.ListIterator;。如果你在Eclipse或IDEA里多數(shù)情況下快捷鍵自動(dòng)補(bǔ)全但建議理解每個(gè)import對(duì)應(yīng)哪個(gè)接口面試時(shí)被問(wèn)到能說(shuō)清楚。5.3 printLots越界與非法位置輸入現(xiàn)象L有5個(gè)元素P里傳了位置100程序不報(bào)錯(cuò)打印出鏈表的最后一個(gè)元素。原因內(nèi)層while (start itemP iterL.hasNext())在鏈表耗盡時(shí)靜默退出itemL停在最后一個(gè)節(jié)點(diǎn)上。題目默認(rèn)P中位置合法但實(shí)際傳參沒(méi)有這種保證。解決在內(nèi)層循環(huán)結(jié)束后檢查start itemP不相等直接拋IllegalArgumentException或者在調(diào)用前用L.size()和P的每個(gè)元素做一次合法性校驗(yàn)。5.4 循環(huán)復(fù)雜度直接相乘導(dǎo)致誤判現(xiàn)象看到三層嵌套循環(huán)就寫(xiě)O(N3)看到更深的嵌套直接寫(xiě)O(N?)結(jié)果2.7(VI)的正確答案是O(N?)。原因循環(huán)層數(shù)相乘只在無(wú)條件進(jìn)入內(nèi)層時(shí)成立遇到if分支就必須統(tǒng)計(jì)成立次數(shù)。很多人栽在“內(nèi)層O(N2)操作對(duì)外層每次循環(huán)都執(zhí)行”的錯(cuò)誤假設(shè)上。解決逐層分析。先確認(rèn)最內(nèi)層語(yǔ)句是否每次都被執(zhí)行統(tǒng)計(jì)條件成立的總次數(shù)再乘以單次執(zhí)行代價(jià)。養(yǎng)成“先算執(zhí)行次數(shù)再算單次代價(jià)”的習(xí)慣復(fù)雜度分析就不容易翻車。6. 把習(xí)題答案變成面試素材驗(yàn)證、改寫(xiě)與追問(wèn)拿到這份答案最高效的用法不是“看”而是“跑”。我習(xí)慣把每段Java代碼復(fù)制到IDE里寫(xiě)一個(gè)main方法做單元驗(yàn)證。比如ones(int n)用標(biāo)準(zhǔn)庫(kù)的Integer.bitCount(n)做基準(zhǔn)循環(huán)0到1000逐個(gè)斷言public static void main(String[] args) { for (int i 0; i 1000; i) { int expected Integer.bitCount(i); int actual ones(i); if (expected ! actual) { System.out.println(Mismatch at i); } } }這一步能把“我以為我懂了”變成“我確認(rèn)它是對(duì)的”。跑通之后再想兩個(gè)追問(wèn)ones的遞歸深度是多少對(duì)int輸入最多遞歸31次。能不能改成循環(huán)當(dāng)然能while (n 0) { count n % 2; n / 2; }。能不能更快用n (n - 1)逐次消掉最低位的1循環(huán)次數(shù)等于1的個(gè)數(shù)而非位數(shù)。這三個(gè)追問(wèn)在Java面試?yán)锍霈F(xiàn)的頻率不低答案文檔只給了遞歸版后面兩層要靠自己推。另一類面試高頻點(diǎn)是復(fù)雜度排序表。建議按3.1節(jié)的表格默寫(xiě)三遍直到能在一分鐘內(nèi)從2/N排到2^N。遇到“N log N和N log(N2)誰(shuí)快”這種送命題能脫口而出“同階”才算過(guò)關(guān)。最后是鏈表題的改寫(xiě)。把printLots改成用L.get(itemP)的隨機(jī)訪問(wèn)版本對(duì)比一下性能差異你就明白為什么題目強(qiáng)調(diào)“鏈表上不能用下標(biāo)”。把swapWithNext加空指針保護(hù)再補(bǔ)一個(gè)單元測(cè)試覆蓋“尾部節(jié)點(diǎn)交換拋異常”的場(chǎng)景——這些改動(dòng)讓教材答案變成了生產(chǎn)級(jí)代碼面試官問(wèn)到邊界處理時(shí)你也能接得住。從那以后我拿到任何一份習(xí)題答案都強(qiáng)制自己先盲寫(xiě)一遍再對(duì)照把所有代碼跑起來(lái)驗(yàn)證過(guò)才敢說(shuō)“會(huì)了”。這份docx雖然排版亂、公式散但核心推導(dǎo)和代碼都是對(duì)的值得花一下午消化。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取