編程之美答案

㈠ 學習數據結構，有哪些值得推薦的好書

在微信高校專業集裡面粘貼
入門
1.《啊哈！演算法》
2.《演算法設計與分析基礎》
3.《演算法引論：一種創造性方法》
4.原書名：Introction to Algorithms
中文名：演算法導論
5.數據結構與演算法分析：C語言描述（原書第2版）
進階
1.原書名：The Design and Analysis of Computer Algorithms
中文名：演算法設計與分析
作者：Aho，Hopcroft，Ullman
2.原書名：Algorithms Design Techniques and Analysis
中文名：演算法設計技巧與分析
作者：M.H.Alsuwaiyel
3.中文名：演算法與數據結構
作者：傅清祥 王曉東
程序設計競賽
1.原書名：Introction to Algorithms
中文名：演算法導論
作者：Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest,Clifford Stein
2.原書名：Introction to The Design & Analysis of Algorithms
中文名：演算法設計與分析基礎
作者：Anany Levitin
4.演算法競賽 | 信息學奧賽一本通
5.演算法競賽 | 演算法競賽進階指南

㈡ 終於知道怎麼判斷字元串相似度了

一直不理解，為什麼要計算兩個字元串的相似度呢。什麼叫做兩個字元串的相似度。經常看別人的博客，碰到比較牛的人，然後就翻了翻，終於找到了比較全面的答案和為什麼要計算字元串相似度的解釋。因為搜索引擎要把通過爬蟲抓取的頁面給記錄下來，那麼除了通過記錄url是否被訪問過之外，還可以這樣，比較兩個頁面的相似度，因為不同的url中可能記錄著相同的內容，這樣，就不必再次記錄到搜索引擎的存儲空間中去了。還有，大家畢業的時候都寫過論文吧，我們論文的查重系統相信也會採用計算兩個字元串相似度這個概念。
以下敘述摘自編程之美一書：
許多程序會大量使用字元串。對於不同的字元串，我們希望能夠有辦法判斷其相似程序。我們定義一套操作方法來把兩個不相同的字元串變得相同，具體的操作方法為：
1.修改一個字元（如把「a」替換為「b」）;
2.增加一個字元（如把「abdd」變為「aebdd」）;
3.刪除一個字元（如把「travelling」變為「traveling」）;
比如，對於「abcdefg」和「abcdef」兩個字元串來說，我們認為可以通過增加/減少一個「g」的方式來達到目的。上面的兩種方案，都僅需要一 次 。把這個操作所需要的次數定義為兩個字元串的距離，而相似度等於「距離+1」的倒數。也就是說，「abcdefg」和「abcdef」的距離為1，相似度 為1/2=0.5。
給定任意兩個字元串，你是否能寫出一個演算法來計算它們的相似度呢？
原文的分析與解法
不難看出，兩個字元串的距離肯定不超過它們的長度之和（我們可以通過刪除操作把兩個串都轉化為空串）。雖然這個結論對結果沒有幫助，但至少可以知道，任意兩個字元串的距離都是有限的。我們還是就住集中考慮如何才能把這個問題轉化成規模較小的同樣的子問題。如果有兩個串A=xabcdae和B=xfdfa，它們的第一個字元是 相同的，只要計算A[2,...,7]=abcdae和B[2,...,5]=fdfa的距離就可以了。但是如果兩個串的第一個字元不相同，那麼可以進行 如下的操作（lenA和lenB分別是A串和B串的長度）。
1.刪除A串的第一個字元，然後計算A[2,...,lenA]和B[1,...,lenB]的距離。
2.刪除B串的第一個字元，然後計算A[1,...,lenA]和B[2,...,lenB]的距離。
3.修改A串的第一個字元為B串的第一個字元，然後計算A[2,...,lenA]和B[2,...,lenB]的距離。
4.修改B串的第一個字元為A串的第一個字元，然後計算A[2,...,lenA]和B[2,...,lenB]的距離。
5.增加B串的第一個字元到A串的第一個字元之前，然後計算A[1,...,lenA]和B[2,...,lenB]的距離。
6.增加A串的第一個字元到B串的第一個字元之前，然後計算A[2,...,lenA]和B[1,...,lenB]的距離。
在這個題目中，我們並不在乎兩個字元串變得相等之後的字元串是怎樣的。所以，可以將上面的6個操作合並為：
1.一步操作之後，再將A[2,...,lenA]和B[1,...,lenB]變成相字元串。
2.一步操作之後，再將A[2,...,lenA]和B[2,...,lenB]變成相字元串。
3.一步操作之後，再將A[1,...,lenA]和B[2,...,lenB]變成相字元串。

通過以上1和6,2和5，3和4的結合操作，最後兩個字元串每個對應的字元會相同，但是這三種操作產生的最終的兩個字元串是不一樣的。我們不知道通過上述的三種結合那種使用的操作次數是最少的。所以我們要比較操作次數來求得最小值。

㈢ 有什麼適合大一計算機專業學生免費的刷題網站

既然大一的同學選擇計算機專業，當然少不了刷題啦！但是有很多刷題網站是免費的，同學們想知道嗎？下面由我來講講吧。

1.力扣

這個網站收錄了很多知名互聯網公司出的演算法題目，相信大一同學很熟悉了，很多同學都在這里刷題，增強對計算機基礎知識掌握。它支持多種編程語言，如：java、Ptthon、Ruby等。最常做的是演算法題，目前有一千多道的題目。有專門的圖文和視頻講解，方便同學們茶樓補缺。也可以在個人界面查看進展，看自己的學習情況。如果出來工作筆試中，面試官會從這里抽題。刷題過程中全部會了，那麼工作沒有什麼大問題。

以上我列舉了三個計算機免費刷題的網站，同學們看到我寫的推薦後，來收藏夾吃灰~希望同學們有時間使用這三個網站學習計算機相關知識，提高計算機專業能力，祝你們學有所成！

㈣ 計算機面試主考官一般都會問到什麼問題

《編程之美——微軟技術面試心得》裡面有60多道面試題目，很多IT公司的演算法或者程序設計題目都跟它類似，而且裡面每個題目都給出了好幾種解法，還有擴展問題。
不知道符不符合你的要求。

㈤ 求高手用c++解決二十四點的問題，具體如下

24點演算法分析
很久沒有研究程序了，慚愧中。。。這個夏天大致地翻了一下微軟亞洲研究院出的《編程之美》，很喜歡這本書的風格，裡面很多題目都很有意思。書中主要突出的是一個「巧」字，最關鍵的，就是從變化中尋找不變的規律。 這次說的問題其實也很簡單，給四個數，寫一個程序輸出算24點的結果，如果沒有就輸出「No Answer」。但是如果用我們自己算24點的思維來寫程序是不行的，因為那屬於一種「湊」的方法，有碰巧和經驗的成分。計算機能做的，就是通過一種固定的方式來找尋結果。如果沒有一般性的所謂「固定」方式，那麼只有通過遍歷和窮舉來解決問題。這樣的方法下誕生了很多所謂的NP難問題，如果原始數據規模比較大就要花很長的時間來得到結果。
24點這個問題最直接的方法就是，列舉四個數所有的排列組合，加上各種運算符以及括弧，所有的情況經過處理之後可以得到一個包含所有計算結果和計算式的列表，從其中尋找24的影蹤就可以了。如果不計計算結果重復的情況，最終的結果有7680種，數據量還是有點大，因此這個演算法需要進一步的優化。例如，考慮到加法和乘法的交換律，如果遇到相應的情況只計算一種，對於另一種直接返回。這樣的剪枝處理可以減少不少的運算。
不過我用的是書中的另一種思路，採用了劃分的思想。具體的演算法是：
如果A是一個數組，定義f(A)為數組中的所有數經過四則運算所能得到的結果的集合。對於A中元素個數大於1的情況，可以將A分拆成兩個集合，定義運算 Fork(A,B)為f(A)和f(B)中各取一個元素的四則運算得到的所有的結果的集合。這樣，如果列舉出集合A所有的拆分情況，那麼所有Fork結果的並集就是f(A)的結果。
對於24點的情況，因為數組A有4個數，因此將其用各種方法拆分即可得到最終的f(A)，然後查詢其中是否存在元素24即可得到有解或者無解的判斷。
需要說明的有幾點：
1.這個問題表面上需要採用遞歸的演算法，即如果只有一個元素那麼直接返回，否則將問題轉化為多個f的計算，而每個f的計算又要經過轉化，層層遞歸，直至只有一個元素的情況。但是，不要忘了遞歸的方法一般都是針對回溯次數不確定的問題。例如漢諾塔問題，只有一個盤子的情況和64個盤子的情況，回溯次數截然不同，千差萬別；但是對於24點，因為只有4個數，實際上分拆的可能性是固定的，就那麼有限種情況。遞歸演算法的思路是從樹的根部往下遍歷，而且一般不知道樹的大小和規模。而對於24點問題，這棵樹的大小固定，完全可以從樹的葉子著手，從葉子向根步進，從而得到最終的結果。
2.分拆有一定的技巧，最合適的方法是通過位運算。比如一種分拆方法是{a1,a2},{a3,a4},那麼寫做1100和0011。這種方法的好處在於，比如要判斷1000是不是1100的一個子集，只需要將兩者做與運算，最後的結果如果還等於1100則表明確實是子集，同時分拆的另一個結果便是兩者的差。這樣至多隻需要比較 10多次就可以列舉出每個集合所有的分拆情況，比較巧妙的方法。同時，位運算的速度也很快，不會對計算的時間有較大的影響。
3.這個方法的缺點在於，最終得到的只是一個無解或者有解的判斷，並沒有輸出表達式。
所以我對這個演算法進行了一定的改進，使之能輸出表達式。
首先要考慮的，也是最重要的，是這個程序的數據結構。最終的目的自然是為了達到最少的時間復雜度。由於上述方法中f函數返回的是「集合」，因此不存在重復的元素。這樣的情況下，哈希表自然是首選的數據結構。
為了記錄表達式，需要引入另一套數據結構。每一個計算的結果都必須和一個表達式對應。這樣，當最終查詢到一個計算結果為24的時候，只需查找相應的表達式就可以得到結果。
這里就產生了沖突。哈希表的特點是存放是亂序的，也就是說，如果只採用一個哈希表存放計算結果，用一個vector存放表達式，那麼無法產生對應關系。
因此，有兩種方案：
第一種方案比較節省存儲空間，將計算結果和表達式分別存在兩個vector中，由於兩者都是有序的集合類，因此可以在插入數據的時候令各自的下標對應，這樣就可以方便地得到對應關系。但是，這樣做的後果是，在插入新數據的時候需要在vector中查找是否已經存在這個計算結果，如果已有則不必插入。 vector的查找是窮舉式的，效率比較低，尤其是當vector比較大的時候將很大程度上影響計算的效率。但如果不進行查找，勢必會計算很多沒有意義的重復結果，這樣就失去了這個演算法的意義了。
第二種方案在第一種方案的基礎上將計算結果多存一份哈希表數據。這樣做增加了存儲空間，但是在時間上的優勢是顯而易見的。在插入的時候，通過查找哈希表來決定是否已經存在這個結果，由於哈希表的查找效率很高，因此這一步不會對這個程序造成時間上的瓶頸。如果不存在，那麼同時在哈希表和兩個vector中同時插入數據即可。計算結果和表達式的對應關系依然存在，同時查找的效率也大大提高，整個程序的時間復雜度大大降低。這是典型的空間換時間的方法。
寫演算法我首選的語言還是c++，但是很慚愧c++的HashTable我不會用，因此用java寫了一個版本，還算比較成功，能輸出最終的結果。在寫程序前我寫了一個小程序來測試java的HashSet和ArrayList的查找效率，結果很令人驚訝。在10000次查詢中，HashSet所用時間為0ms，而ArrayList則用了1300多ms，看來這個效率完全不是一個數量級上的。因此我採用了上述的第二種方案，最終的效果還不錯。
曾經有人問過我5，5，5，1怎麼算24點，當時想了很久都沒想出來。現在用這個程序可以很輕松地算出5*(5-1/5)=24。看來這個程序可以輸出一些大家想不到的結果，很強大把。類似的例子還有很多，比如3，3，7，7等等。總之呢，優化了的窮舉法（我這個程序實際上還是一種變相的窮舉）是一種很不錯的解決問題的思路，值得採用！
過幾天就開學了。也許每年的開學前才有時間去研究下這種問題，等到開學之後就基本沒什麼時間了。嗯，好好工作把，也願今年能開個好題，明年好好做畢設。Good luck。

PS:昨天經同學提醒才發現有更好的解決方法。主要是因為好久沒用，把java的HashMap給忘了。這個數據結構用在這里正合適，也就是說不用兩個HashSet加兩個ArrayList解決了，直接存在一個HashMap裡面就可以。
具體的做法是：把計算結果存在map的key中，而表達式存在map的value中，問題徹底解決。map中key的查找效率是很高的，同時插入也很快；當找到一個計算結果為24的時候直接根據這個key去尋找相應的value即可得到完美的答案，同時HashMap也保證了每個計算結果只保留一個表達式，避免了重復。
我做了一下性能測試，總的來這個改進後的版本效率比以前的版本略有提高，但是最關鍵的是大大減少了空間的存儲，因此也算是對程序進行的大優化把我想。這兩天看這個帖子似乎看的人比較多哈，也願我的想法能給大家一些啟發。