re: 一著名軟件公司的java筆試算法題的答案 dreamingnest 2008-05-16 10:32
你給出的想法和代碼都很優秀,我覺得你對本題有兩點非常獨特的見解:1)你會使用字符索引來“組合”最后的字符串,而且幾處用到的indexOf非常合理,也很巧妙;2)validate函數的使用,尤其是判斷重復字符串上面,很難想到。我建議你還能去網上找到兩個版本的程序,其中一個也是用遞歸,另一個是圖的思想,一定要做多組測試,因為網上好多的程序都是錯誤的,你這幾組的數據都是對的。
補:在“注”中有筆誤,當i=0的時候,i+48是0的ASCII,因為你index中存的畢竟是索引,是位置嘛,所以是從0開始的
re: 拆半查找的遞歸和非遞歸算法 dreamingnest 2008-05-12 15:56
嗯,應該是的,只是測試的例子多了些,也看了好半天。汗``
re: 關于螞蟻問題(Ants) dreamingnest 2008-05-12 15:26
你為什么確定27-3=24是便是最長的呢?我覺得你說的“即所有螞蟻中離桿其中一端最遠的那只螞蟻,即為最長時間”和“所有螞蟻使用時間:A最短是3, B最短是7, C最短11, D最短是10, E最短是4”中的兩個“所有”和我解釋的還不太一樣,呵呵。
·最長時間:是按照你說的“螞蟻不調頭,即擦肩而過,繼續沿原來方向前進(與調頭是一樣的,只是換了一只螞蟻而已)”這樣,但有兩點說明:(1)通過分析,我們只需判斷最兩端的兩只螞蟻便足夠了,證明見二樓“銀河使者”的解釋。(2)一定要求出4個數進行比較后才可以,假設最左端和最右端的位置為L和R,中長度為T,那么最長的時間為max(max(L,T-L),max(R,T-R))。
·最短時間:通過分析后,也只需看最中間的一個(共奇數螞蟻)或兩個(共偶數螞蟻)螞蟻到達某一端的最短時間,對于奇數:min(L,T-L),對于偶數:max(min(L,T-L),min(R,T-R))。
·通過程序來實現是有必要的,這算是一道模擬題目,可在情況類似的計算應用中會遇到,正如英文描述中可能出現1000000數量級別的,這樣我們便無法直接得出結果。此題能作為面試題,而不是筆試題,就是在考察一種思想,避開“一根不能同時通過兩只螞蟻”的迷惑。
·感謝大家能仔細討論這個問題,寫程序相信每個人都能實現,只是這道題給我們的啟發是非常大的~
re: 百度面試題的java實現 dreamingnest 2008-05-10 11:37
剛剛看到你對這道題目的解釋,新寫了一篇文章,覺得最大是24秒,而且感覺沒有這么復雜,可以看一下,相互學習吧,加油~