經典算法面精彩試題及問題詳解

《經典算法面精彩試題及問題詳解》由會員上傳分享，免費在線閱讀，更多相關內容在工程資料-天天文庫。

1、文檔1.時針分針重合幾次表面上有60個小格，每小格代表一分鐘，時針每分鐘走1/12小格，分針每分鐘走1小格，從第一次重合到第二次重合分針比時針多走一圈即60小格，所以60/（1-1/12）=720/11每隔720/11分才重合一次（而并不是每小時重合一次）1440里有22個720/11，如果說算上0點和24點，那也是重合23次而已，但我覺得0點應該算到前一天的24點頭上，所以每一天循環(huán)下來重合22次啊2.找出字符串的最長不重復子串，輸出長度建一個256個單元的數(shù)組，每一個單元代表一個字符，數(shù)組中保存上次該字符上次出現(xiàn)的位置；依次讀入字

2、符串，同時維護數(shù)組的值；如果遇到沖突了，就返回沖突字符中保存的位置，繼續(xù)第二步。也可以用hashmap保存已經出現(xiàn)的字符和字符的位置3.說是有一個文本文件，大約有一萬行，每行一個詞，要求統(tǒng)計出其中最頻繁出文檔現(xiàn)的前十個詞。先用哈希，統(tǒng)計每個詞出現(xiàn)的次數(shù)，然后在用在N個數(shù)中找出前K大個數(shù)的方法找出出現(xiàn)次數(shù)最多的前10個詞。4.如題3，但是車次文件特別大，沒有辦法一次讀入內存。1)直接排序，寫文件時，同時寫入字符串及其出現(xiàn)次數(shù)。2)可以用哈希，比如先根據(jù)字符串的第一個字符將字符串換分為多個區(qū)域，每個區(qū)域的字符串寫到一個文件內，然后再用哈希

3、+堆統(tǒng)計每個區(qū)域內前10個頻率最高的字符串，最后求出所有字符串中前10個頻率最高的字符串。5.有一個整數(shù)n，將n分解成若干個整數(shù)之和，問如何分解能使這些數(shù)的乘積最大，輸出這個乘積m。例如：n=12（1）分解為1+1+1+…+1，12個1,m=1*1*1……*1=1（2）分解為2+2+…+2，6個2，m=64（3）分解為3+3+3+3，4個3，m=81（4）大于等于4時分解時只能分解為2和3，且2最多兩個f(n)=3*f(n-3)n>4文檔f(4)=2*2f(3)=3f(2)=2分解為4+4+4，3個4，m=646.求數(shù)組n中出現(xiàn)次數(shù)超

4、過一半的數(shù)把數(shù)組分成[n/2]組，則至少有一組包含重復的數(shù)，因為如果無重復數(shù)，則最多只有出現(xiàn)次數(shù)等于一半的數(shù)。算法如下：k<-n;whilek>3do把數(shù)組分成[k/2]組;fori=1to[k/2]do???if組內2個數(shù)相同，則任取一個數(shù)留下;???else2個數(shù)同時扔掉;k<-剩下的數(shù)ifk=3???then任取2個數(shù)進行比較;????if兩個數(shù)不同，則2個數(shù)都扔掉????else任取一個數(shù)文檔???ifk=2or1then任取一數(shù)7.A文件中最多有n個正整數(shù)，而且每個數(shù)均小于n，n<=10的七次方。不會出現(xiàn)重復的數(shù)。要求對A文

5、件中的數(shù)進行排序，可用內存為1M，磁盤可用空間足夠。不要把任何問題都往很復雜的算法上靠，最直接最簡單的解決問題才是工程師應有的素質，題目給的很有分寸：n個數(shù)，都小于n，兩兩不同，1M=10^6byte=10^7bit的內存，n<10^7思路：把1M內存看作是一個長度為10^7的位數(shù)組，每一位都初始化為0從頭掃描n個數(shù)，如果碰到i，就把位數(shù)組的第i個位置置為1，1M內存有點少，（1M=8Mbits),可以代表8M整數(shù)，現(xiàn)在n<=10的七次方，你可以讀2遍文件，就可以完成排序了。第一次排n<8M得數(shù)，第2遍排8M<=""div=""sty

6、le="word-wrap:break-word;">8.有10億個雜亂無章的數(shù)，怎樣最快地求出其中前1000大的數(shù)。文檔1)建一個1000個數(shù)的堆，復雜度為N*(log1000)=10N2)1.用每一個BIT標識一個整數(shù)的存在與否，這樣一個字節(jié)可以標識8個整數(shù)的存在與否，對于所有32位的整數(shù)，需要512Mb，所以開辟一個512Mb的字符數(shù)組A，初始全0??2.依次讀取每個數(shù)n，將A[n>>3]設置為A[n>>3]

7、(1<<=""div=""style="word-wrap:break-word;">??3.在A中，從大到小讀取100

8、0個值為1的數(shù)，就是最大的1000個數(shù)了。這樣讀文件就只需要1遍，在不考慮內存開銷的情況下，應該是速度最快的方法了。9.一棵樹節(jié)點1,2,3,...,n.怎樣實現(xiàn)：先進行O(n)預處理，然后任給兩個節(jié)點，用O(1)判斷它們的父子關系dfs一遍，記錄每個結點的開始訪問時間Si和結束訪問時間Ei對于兩個節(jié)點i,j，若區(qū)間[Si,Ei]包含[Sj,Ej]，則i是j的祖先。給每個節(jié)點哈夫曼編碼也行，但只適合一般的二叉樹，而實際問題未必是Binary的，所以編碼有局限性10.給定一個二叉樹，求其中N（N>=2）個節(jié)點的最近公共祖先節(jié)點。每個節(jié)點

9、只有左右孩文檔子指針，沒有父指針。后序遞歸給每個節(jié)點打分，每個節(jié)點的分數(shù)=左分數(shù)+右分數(shù)+k，如果某孩子是給定節(jié)點則+1最深的得分為N的節(jié)點就是所求吧，細節(jié)上應該不用遞歸結束就可以得到這個節(jié)點11.如何打印如下的螺旋隊列