常見(jiàn)算法筆試或面試題

1、Problem 1 : Is it a loop(判斷鏈表是否有環(huán))Assume that wehave a head poin ter to a lin k-list. Also assumethat we know the listis sin gle-l in ked. Can you come up an algorithm to checkwhether this link listin cludes a loop by using O(n) time and 0(1) space where n is the len gth of the listFurthermore, can

2、you do so with O( n) time and onlyone register方法：使用兩個(gè)指針，從頭開(kāi)始，一個(gè)一次前進(jìn)一個(gè)節(jié)點(diǎn)，一個(gè)前進(jìn)2個(gè)節(jié)點(diǎn)，則最多2N,后兩個(gè)指針可以重合；如果無(wú)環(huán)，則正常停止。同樣的，可以找到鏈表的中間節(jié)點(diǎn)。同上。Problem 2 :設(shè)計(jì)一個(gè)復(fù)雜度為 n的算法找到鏈表倒數(shù)第m個(gè)元素。最后一個(gè)元素假定是倒數(shù)第0個(gè)。提示：雙指針查找Problem 3 :用最簡(jiǎn)單的方法判斷一個(gè)LONG整形的數(shù)A是25( 2的n次方)提示：x&(x-1)Problem 4 :兩個(gè)燒杯，一個(gè)放糖一個(gè)放鹽，用勺子舀一勺糖到鹽，攪拌均勻，然后舀一勺 混合物會(huì)放糖的燒杯，問(wèn)你

3、兩個(gè)燒杯哪個(gè)雜質(zhì)多提示：相同。假設(shè)雜質(zhì)不等，那么將雜質(zhì)放回原杯中，則杯中物體重量必變化，不合理。Problem 5：給你a、b兩個(gè)文件，各存放50億條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表項(xiàng)刪除，當(dāng)hash表項(xiàng)少于某個(gè)閾值時(shí)，將a中新元素重新hash。再次循環(huán)。法2 :對(duì)于hash表項(xiàng)增加一項(xiàng)記錄屬于的文件a，b。只要不存在的表項(xiàng)即放入hash表中，一致的項(xiàng)則刪除。注意：可能存在

4、很多重復(fù)項(xiàng)，弓I起插入，刪除頻繁。Problem 6：給你一個(gè)單詞a，如果通過(guò)交換單詞中字母的順序可以得到另外的單詞b,那么定義b是a的兄弟單詞?，F(xiàn)在給你一個(gè)字典，用戶輸入一個(gè)單詞， 讓你根據(jù)字典找出這個(gè)單 詞有多少個(gè)兄弟單詞。提示：將每個(gè)的單詞按照字母排序，則兄弟單詞擁有一致的字母排序(作為單詞簽名)。使用單詞簽名來(lái)查找兄弟單詞。Problem 7 :五桶球，一桶不正常，不知道球的重量和輕重關(guān)系，用天平稱(chēng)一次找出那桶不 正常的球。Problem &給兩個(gè)燒杯，容積分別是 m和n升(m!=n),還有用不完的水，用這兩個(gè)燒杯能 量出什么容積的水m, n, m+n, m-n 以及線性疊加的

5、組合Problem 9 :寫(xiě)出一個(gè)算法，對(duì)給定的n個(gè)數(shù)的序列，返回序列中的最大和最小的數(shù)。Problem 10：你能設(shè)計(jì)出一個(gè)算法，只需要執(zhí)行次比較就能找到序列中最大和最小的數(shù)嗎能否再少提示：先通過(guò)兩兩比較，區(qū)分大小放入“大”，“小”兩個(gè)數(shù)組中。從而最大數(shù)在“大”數(shù) 組中，最小數(shù)在“小”數(shù)組中。Problem 11 :給你一個(gè)由n-1個(gè)整數(shù)組成的未排序的序列，其元素都是1到n中的不同的整數(shù)。請(qǐng)寫(xiě)出一個(gè)尋找序列中缺失整數(shù)的線性-時(shí)間算法。提示：累加求和Problem 12 : void strt on(const char* src, con st char*toke n)假設(shè) src 是一長(zhǎng)串

6、字符，token存有若干分隔符，只要src的字符是token中的任何一個(gè)，就進(jìn)行分割，最終將src按照token分割成若干單詞。找出一種0(n)算法提示：查表的方法，將所有的字符串存儲(chǔ)在長(zhǎng)度為128的數(shù)組中，并將作為分隔符的字符位置1，這樣即可用常數(shù)時(shí)間判斷字符是否為分隔符，通過(guò)n次掃描，將src分割成單詞。Problem 13 : 一個(gè)排好序的數(shù)組 A,長(zhǎng)度為n,現(xiàn)在將數(shù)組 A從位置m(m<n m未知)分開(kāi)， 并將兩部分互換位置，假設(shè)新數(shù)組記為B，找到時(shí)間復(fù)雜度為 O(lgn)的算法查找給定的數(shù)x是否存在數(shù)組B中提示：同樣采用二分查找。核心思想就是確定所查找數(shù)所在的范圍。通過(guò)比較3個(gè)數(shù)

7、(頭，尾，中間)和所查找數(shù)之間的關(guān)系，可以確定下次查找的范圍。Problem 14 : 一個(gè)排好序的數(shù)組 A，長(zhǎng)度為n，現(xiàn)在將數(shù)組 A從位置m(m<n m已知)分開(kāi)， 并將兩部分互換位置，設(shè)計(jì)一個(gè)O(n)的算法實(shí)現(xiàn)這樣的倒置，只允許使用一個(gè)額外空間。(循 環(huán)移位的效率不高)提示：(A' B' ) ' =BAProblem 15 :給出Vector的一個(gè)更好實(shí)現(xiàn)。(STL的vector內(nèi)存的倍增的，但是每次倍增 需要拷貝已存元素，平均每個(gè)元素需要拷貝一次，效率不高)提示：可使用25的固定長(zhǎng)度作為每次分配的最小單位，并有序的記錄每個(gè)塊的首地址。這 中結(jié)構(gòu)同樣可以實(shí)現(xiàn)線

8、性查找，并且拷貝代價(jià)很低(僅有指針)Problem 16:給出已排序數(shù)組 A, B，長(zhǎng)度分別為n，m請(qǐng)找出一個(gè)時(shí)間復(fù)雜度為(Ign )的 算法，找到排在第 k位置的數(shù)。提示：二分查找。Problem 17：給出任意數(shù)組 A，B,長(zhǎng)度分別為n，m請(qǐng)找出一個(gè)時(shí)間復(fù)雜度為(Ign )的算 法，找到排在第k位置的數(shù)。提示：通過(guò)最小堆記錄k個(gè)數(shù)，不斷更新，掃描一次完畢。這個(gè)提示有問(wèn)題，求最優(yōu)算法！Problem 18 :假設(shè)數(shù)組A有n個(gè)元素，元素取值范圍是 1n，判定數(shù)組是否存在重復(fù)元素要 求復(fù)雜度為0(n)。法1:使用n的數(shù)組，記錄元素，存在記為1,兩次出現(xiàn)1,即重復(fù)。法2 :使用m的數(shù)組，分別記錄大

9、?。簄/m, 2n/m.的元素個(gè)數(shù)。桶方法法3 :累加求和。可用于求僅有一個(gè)元素重復(fù)的方法。Problem 19 :給定排好序的數(shù)組 A,大小為n，現(xiàn)給定數(shù) X判斷A中是否存在兩數(shù)之和等 于X。給出一個(gè)0(n)的算法。提示：從中間向兩邊查找。利用有序的條件Problem 20：給定排好序的數(shù)組 A，大小為n，請(qǐng)給出一個(gè) 0(n)的算法，刪除重復(fù)元素，且 不能使用額外空間。提示，既然有重復(fù)，必有冗余空間。將元素放入數(shù)組的前面，并記錄下次可放位置，不斷向 后掃描即可。Problem 21 :給定兩個(gè)排好序的數(shù)組A， B,大小分別為n，給出一個(gè)高效算法查找A中的哪些元素存在 B數(shù)組中。注意：一般在大

10、數(shù)組中執(zhí)行二分查找，將小數(shù)組的元素作為需查找的對(duì)象。更優(yōu)算法（軒轅刃提供）：可以使用兩個(gè)指針遍歷AB比較當(dāng)前大小就可以了 時(shí)間復(fù)雜度 o（n+m）Problem 22：?jiǎn)枺河?000桶酒，其中1桶有毒。而一旦吃了，毒性會(huì)在1周后發(fā)作?，F(xiàn)在我們用小老鼠做實(shí)驗(yàn)，要在1周內(nèi)找出那桶毒酒，問(wèn)最少需要多少老鼠。答案：10只。將酒編號(hào)為11000將老鼠分別編號(hào)為1 2 4 8 16 32 64 128 256 512 喂酒時(shí) 讓酒的編號(hào)等于老鼠編號(hào)的加和如：17號(hào)酒喂給1號(hào)和16號(hào)老鼠76號(hào)酒喂給4號(hào)、8號(hào)和64號(hào)老鼠 七天后將死掉的老鼠編號(hào)加起來(lái)得到的編號(hào)就是有毒的那桶酒因?yàn)?的10次方等于1024所以

11、10只老鼠最多可以測(cè)1024桶酒證明如下：使用二進(jìn)制表示：01, 10, 100, 1000,，1,000,000,000 。對(duì)于任何一個(gè)小于1024的數(shù)，均可以采用前面的唯一一組二進(jìn)制數(shù)來(lái)表示。故成立。Problem 23 :設(shè)計(jì)一組最少個(gè)數(shù)砝碼，使得天平能夠稱(chēng)量11000的重量。如果砝碼只能放單邊，1, 2 , 4 , 512最好。（只能單加）如果允許砝碼雙邊放，1, 3, 9, 27最好。（可加可減）已知1,3，如何計(jì)算下一個(gè)數(shù)?，F(xiàn)可稱(chēng)重量1,2,3,4。設(shè)下個(gè)數(shù)為 x,可稱(chēng)重量為,x-4, x-3, x-2, x-1, x, x+1, x+2, x+3,x+4。為使砝碼最好，所稱(chēng)重量應(yīng)

12、該不重復(fù)（浪費(fèi)）。故x=9。同理，可得后面。圖形算法題Problem 24 :如何判斷一個(gè)點(diǎn)是否在一個(gè)多邊形內(nèi)提示：對(duì)多邊形進(jìn)行分割，成為一個(gè)個(gè)三角形，判斷點(diǎn)是否在三角形內(nèi)。一個(gè)非常有用的解析幾何結(jié)論：如果P2（x1,y1）,P2（x2,y2）, P3（x3,y3）是平面上的3個(gè)點(diǎn)，那么三角形P1P2P3的面積等于下面絕對(duì)值的二分之一：| x1 y1 1 | x2 y2 1 | = x1y2 + x3y1 + x2y3- x3y2 - x2y1 - x1y3| x3 y3 1 |當(dāng)且僅當(dāng)點(diǎn)P3位于直線P1P2（有向直線P1->P2）的右側(cè)時(shí)，該表達(dá)式的符號(hào)為正。這個(gè)公式 可以在固定的時(shí)間內(nèi)，檢查一個(gè)點(diǎn)位于兩點(diǎn)確定直線的哪側(cè)，以及