25道常見算法面試題

1、Problem1:Isitaloop?(判斷鏈表是否有環(huán)？)Assumethatwehaveaheadpointertoalink-list.Alsoassumethatweknowthelistissingle-linked.CanyoucomeupanalgorithmtocheckwhetherthislinklistincludesaloopbyusingO(n)timeand0(1)spacewherenisthelengthofthelist?Furthermore,canyoudosowithO(n)timeandonlyoneregister?方法：使用兩個指針，從頭開始，一個

2、一次前進一個節(jié)點，一個前進2個節(jié)點,則最多2N，后兩個指針可以重合；如果無環(huán)，則正常停止。同樣的，可以找到鏈表的中間節(jié)點。同上。Problem2:設(shè)計一個復(fù)雜度為n的算法找到鏈表倒數(shù)第m個元素。最后一個元素假定是倒數(shù)第0個。提示：雙指針查找Problem3:用最簡單的方法判斷一個LONG整形的數(shù)A是25(2的n次方)提示：x&(x-1)Problem4:兩個燒杯，一個放糖一個放鹽，用勺子舀一勺糖到鹽，攪拌均勻，然后舀一勺混合物會放糖的燒杯，問你兩個燒杯哪個雜質(zhì)多？提示：相同。假設(shè)雜質(zhì)不等，那么將雜質(zhì)放回原杯中，則杯中物體重量必變化，不合理。Problem5:給你a、b兩個文件，各存放5

3、0億條url，每條url各占用64字節(jié)，內(nèi)存限制是4G,讓你找出a、b文件共同的url。法1:使用hash表。使用a中元素創(chuàng)建hash表，hash控制在適當(dāng)規(guī)模。在hash中查找b的元素，找不到的url先存在新文件中，下次查找。如果找到，則將相應(yīng)的hash表項刪除，當(dāng)hash表項少于某個閾值時，將a中新元素重新hash。再次循環(huán)。法2:對于hash表項增加一項記錄屬于的文件a，b。只要不存在的表項即放入hash表中，一致的項則刪除。注意：可能存在很多重復(fù)項，引起插入，刪除頻繁。Problem6:給你一個單詞a，如果通過交換單詞中字母的順序可以得到另外的單詞b，那么定義b是a的兄弟單詞?，F(xiàn)在給你

4、一個字典，用戶輸入一個單詞，讓你根據(jù)字典找出這個單詞有多少個兄弟單詞。提示：將每個的單詞按照字母排序，則兄弟單詞擁有一致的字母排序（作為單詞簽名）。使用單詞簽名來查找兄弟單詞。Problem7:五桶球，一桶不正常，不知道球的重量和輕重關(guān)系，用天平稱一次找出那桶不正常的球Problem8:給兩個燒杯，容積分別是m和n升(m!=n)，還有用不完的水，用這兩個燒杯能量出什么容積的水？m,n,m+n,m-n以及線性疊加的組合Problem9:寫出一個算法，對給定的n個數(shù)的序列，返回序列中的最大和最小的數(shù)。Problem10:你能設(shè)計出一個算法，只需要執(zhí)行1.5n次比較就能找到序列中最大和最小的數(shù)嗎？能

5、否再少？提示：先通過兩兩比較，區(qū)分大小放入“大”，“小”兩個數(shù)組中。從而最大數(shù)在“大”數(shù)組中，最小數(shù)在“小”數(shù)組中。Problem11:給你一個由n-1個整數(shù)組成的未排序的序列，其元素都是1到n中的不同的整數(shù)。請寫出一個尋找序列中缺失整數(shù)的線性-時間算法。提示：累加求和Problem12:voidstrton(constchar*src,constchar*token)假設(shè)src是一長串字符，token存有若干分隔符，只要src的字符是token中的任何一個，就進行分割，最終將src按照token分割成若干單詞。找出一種0(n)算法？提示：查表的方法，將所有的字符串存儲在長度為128的數(shù)組中，

6、并將作為分隔符的字符位置1，這樣即可用常數(shù)時間判斷字符是否為分隔符，通過n次掃描，將src分割成單詞。Problem13:一個排好序的數(shù)組A，長度為n，現(xiàn)在將數(shù)組A從位置m（m<n，m未知）分開，并將兩部分互換位置，假設(shè)新數(shù)組記為B,找到時間復(fù)雜度為O（lgn）的算法查找給定的數(shù)x是否存在數(shù)組B中？提示：同樣采用二分查找。核心思想就是確定所查找數(shù)所在的范圍。通過比較3個數(shù)（頭，尾，中間）和所查找數(shù)之間的關(guān)系，可以確定下次查找的范圍。Problem14:一個排好序的數(shù)組A，長度為n，現(xiàn)在將數(shù)組A從位置m（m<n，m已知）分開，并將兩部分互換位置，設(shè)計一個0（n）的算法實現(xiàn)這樣的倒置，

7、只允許使用一個額外空間。（循環(huán)移位的效率不高）提示：（A'B'）'=BAProblem15:給出Vector的一個更好實現(xiàn)。（STL的vector內(nèi)存的倍增的，但是每次倍增需要拷貝已存元素，平均每個元素需要拷貝一次，效率不高）提示：可使用2An的固定長度作為每次分配的最小單位，并有序的記錄每個塊的首地址。這中結(jié)構(gòu)同樣可以實現(xiàn)線性查找，并且拷貝代價很低（僅有指針）Problem16:給出已排序數(shù)組A,B,長度分別為n,m，請找出一個時間復(fù)雜度為(Ign)的算法，找到排在第k位置的數(shù)。提示：二分查找。Problem17:給出任意數(shù)組A，B，長度分別為n，m，請找出一個時間復(fù)

8、雜度為(Ign)的算法，找到排在第k位置的數(shù)。提示：通過最小堆記錄k個數(shù)，不斷更新，掃描一次完畢。這個提示有問題，求最優(yōu)算法！Problem18:假設(shè)數(shù)組A有n個元素，元素取值范圍是1n，判定數(shù)組是否存在重復(fù)元素？要求復(fù)雜度為0(n)。法1:使用n的數(shù)組，記錄元素，存在記為1，兩次出現(xiàn)1，即重復(fù)。法2:使用m的數(shù)組，分別記錄大小：n/m,2n/m.的元素個數(shù)。桶方法法3:累加求和?？捎糜谇髢H有一個元素重復(fù)的方法。Problem19:給定排好序的數(shù)組A，大小為n,現(xiàn)給定數(shù)X,判斷A中是否存在兩數(shù)之和等于X。給出一個0(n)的算法。提示：從中間向兩邊查找。利用有序的條件重復(fù)元素，且不能使用額外空間

9、。提示，既然有重復(fù)，必有冗余空間。將元素放入數(shù)組的前面，并記錄下次可放位置，不斷向后掃描即可。Problem21:給定兩個排好序的數(shù)組A，B,大小分別為n，m。給出一個高效算法查找A中的哪些元素存在B數(shù)組中。注意：一般在大數(shù)組中執(zhí)行二分查找，將小數(shù)組的元素作為需查找的對象。更優(yōu)算法(軒轅刃提供)：可以使用兩個指針遍歷AB，比較當(dāng)前大小就可以了時間復(fù)雜度o(n+m)Problem22:問：有1000桶酒，其中1桶有毒。而一旦吃了，毒性會在1周后發(fā)作?，F(xiàn)在我們用小老鼠做實驗，要在1周內(nèi)找出那桶毒酒，問最少需要多少老鼠。答案：10只。將酒編號為11000將老鼠分別編號為512喂酒時讓酒的編號等于老鼠

10、編號的加和如：17號酒喂給1號和16號老鼠76號酒喂給4號、8號和64號老鼠七天后將死掉的老鼠編號加起來得到的編號就是有毒的那桶酒因為2的10次方等于1024所以10只老鼠最多可以測1024桶酒證明如下：使用二進制表示：01,10,100,1000,，1,000,000,000如果砝碼只能放單邊，1，2，4，512最好。（只能單加）如果允許砝碼雙邊放，1,3,9,最好。（可加可減）已知1,3，如何計算下一個數(shù)?，F(xiàn)可稱重量1,2,3,4。設(shè)下個數(shù)為x,可稱重量為，x-4,x-3,x-2,x-1,x,x+1,x+2,x+3,x+4。為使砝碼最好，所稱重量應(yīng)該不重復(fù)（浪費）。故x=9。同理,可得后面。圖形算法題Problem24:如何判斷一個點是否在一個多邊形內(nèi)?提示：對多邊形進行分割，成為一個個三角形，判斷點是否在三角形內(nèi)一個非常有用的解析幾何結(jié)論：如果P2（x1,y1）,P2（x2,y2）,P3（x3,y3）是平面上的3個點，那么三角形P1P2P3的面積等于下面絕對值的二分之一：|x1y11|x2y21|=x1y2+x3y1+x2y3-（3y2-x2y1-x1y3|x3y31|當(dāng)且僅當(dāng)點P3位于直線P1P2（有向直線P1->P2）的右側(cè)時，該表達式的符號為正。這個公式可以在固定的時間內(nèi)，檢查一個點位于兩點確定直線的哪側(cè)，以及點到直線的距離（面積=底*