本文關(guān)鍵詞：算法，由筆耕文化傳播整理發(fā)布。

隨筆分類 - 經(jīng)典算法專題

經(jīng)典算法題每日演練——第二十五題 塊狀鏈表

摘要: 在數(shù)據(jù)結(jié)構(gòu)的世界里，我們會(huì)認(rèn)識(shí)各種各樣的數(shù)據(jù)結(jié)構(gòu)，每一種數(shù)據(jù)結(jié)構(gòu)都能解決相應(yīng)領(lǐng)域的問題，每一種數(shù)據(jù)結(jié)構(gòu)都像是降龍十八掌中的某一掌，掌掌斃命。。。 當(dāng)然每個(gè)數(shù)據(jù)結(jié)構(gòu)，有他的優(yōu)點(diǎn)，必然就有它的缺點(diǎn)，那么如何創(chuàng)造一種數(shù)據(jù)結(jié)構(gòu)來將某兩種數(shù)據(jù)結(jié)構(gòu)進(jìn)行揚(yáng)長(zhǎng)避短，那就非常完美了。這樣的數(shù)據(jù)結(jié)構(gòu)也有很多，比如：雙端隊(duì)列，還有就是今天講的 塊狀鏈表， 我們都知道 數(shù)組 具有 O(1)的查詢時(shí)間，O(N)的刪除，O(N)的插入。。。 鏈表 具有 O(N)的查詢時(shí)間，O(1)的刪除，O(1)的插入。。。 那么現(xiàn)在我們就有想法了，何不讓“鏈表”和“數(shù)組”結(jié)合起來，來一起均攤CURD的時(shí)間，做法將數(shù)...閱讀全文

posted @ 2014-03-04 22:26 一線碼農(nóng) 閱讀(4942) | 編輯

經(jīng)典算法題每日演練——第二十四題 梳排序

摘要: 這篇再看看一個(gè)經(jīng)典的排序，梳排序，為什么取名為梳，可能每個(gè)梳都有自己的gap吧，大梳子gap大一點(diǎn)，小梳子gap小一點(diǎn)。上一篇我們看到雞尾酒排序是在冒泡排序上做了一些優(yōu)化，將單向的比較變成了雙向，同樣這里的梳排序也是在冒泡排序上做了一些優(yōu)化。冒泡排序上我們的選擇是相鄰的兩個(gè)數(shù)做比較，就是他們的gap為1，其實(shí)梳排序提出了不同的觀點(diǎn)，如果將這里的gap設(shè)置為一定的大小，效率反而必gap=1要高效的多�！∠旅嫖覀兛纯淳唧w思想，梳排序有這樣一個(gè)1.3的比率值，每趟比較完后，都會(huì)用這個(gè)1.3去遞減gap，直到gap=1時(shí)變成冒泡排序，這種算法比冒泡排序的效率要高效的多，時(shí)間復(fù)雜度為O(N2/2...閱讀全文

posted @ 2014-03-02 23:59 一線碼農(nóng) 閱讀(2587) | 編輯

經(jīng)典算法題每日演練——第二十三題 雞尾酒排序

摘要: 這篇我們繼續(xù)扯淡一下雞尾酒排序，為了知道為啥取名為雞尾酒，特意看了下百科，見框框的話，也只能勉強(qiáng)這么說了。要是文藝點(diǎn)的話，可以說是攪拌排序，通俗易懂點(diǎn)的話，就叫“雙向冒泡排序”，我想作為碼農(nóng)的話，不可能不知道冒泡排序，冒泡是一個(gè)單向的從小到大或者從大到小的交換排序，而雞尾酒排序是雙向的，從一端進(jìn)行從小到大排序，從另一端進(jìn)行從大到小排序。從圖中可以看到，第一次正向比較，我們找到了最大值9. 第一次反向比較，我們找到了最小值1. 第二次正向比較，我們找到了次大值8. 第二次反向比較，我們找到了次小值2 。。。 ...閱讀全文

posted @ 2014-03-02 11:54 一線碼農(nóng) 閱讀(2905) | 編輯

經(jīng)典算法題每日演練——第二十二題 奇偶排序

摘要: 這個(gè)專題因?yàn)楦鞣N原因好久沒有繼續(xù)下去了，MM吧。。。你懂的，嘿嘿，不過還得繼續(xù)寫下去，好長(zhǎng)時(shí)間不寫，有些東西有點(diǎn)生疏了，這篇就從簡(jiǎn)單一點(diǎn)的一個(gè)“奇偶排序”說起吧，不過這個(gè)排序還是蠻有意思的，嚴(yán)格來說復(fù)雜度是O(N2)，不過在多核的情況下，可以做到N2 /(m/2)的效率，這里的m就是待排序的個(gè)數(shù)，當(dāng)m=100，復(fù)雜度為N2 /50，還行把，比冒泡要好點(diǎn)，因?yàn)橹攸c(diǎn)是解決問題的奇思妙想。 下面我們看看這個(gè)算法是怎么描述的，既然是奇偶，肯定跟位數(shù)有關(guān)了1：先將待排序數(shù)組的所有奇數(shù)位與自己身后相鄰的偶數(shù)位相比較，如果前者大于后者，則進(jìn)行交換，直到這一趟結(jié)束。2：然后將偶數(shù)位與自己身后相鄰的奇數(shù)位相..閱讀全文

posted @ 2014-02-27 01:25 一線碼農(nóng) 閱讀(2949) | 編輯

經(jīng)典算法題每日演練——第二十一題 十字鏈表

摘要: 上一篇我們看了矩陣的順序存儲(chǔ)，這篇我們?cè)倏纯匆环N鏈?zhǔn)酱鎯?chǔ)方法“十字鏈表”，當(dāng)然目的都是一樣，壓縮空間。一：概念 既然要用鏈表節(jié)點(diǎn)來模擬矩陣中的非零元素，肯定需要如下5個(gè)元素(row,col,val,down,right)，其中：row:矩陣中的行。col:矩陣中的列。val:矩陣中的值。right:指向右側(cè)的一個(gè)非零元素。down：指向下側(cè)的一個(gè)非零元素�，F(xiàn)在我們知道單個(gè)節(jié)點(diǎn)該如何表示了，那么矩陣中同行的非零元素的表示不就是一個(gè)單鏈表嗎？比如如下：那么進(jìn)一步來說一個(gè)多行的非零元素的表示不就是多個(gè)單鏈表嗎，是的，這里我把單鏈表做成循環(huán)鏈表，我們來看看如何用十字鏈表來表示稀疏矩陣。從上面的十...閱讀全文

posted @ 2013-04-02 13:44 一線碼農(nóng) 閱讀(11495) | 編輯

經(jīng)典算法題每日演練——第二十題 三元組

摘要: 我們知道矩陣是一個(gè)非常強(qiáng)大的數(shù)據(jù)結(jié)構(gòu)，在動(dòng)態(tài)規(guī)劃以及各種圖論算法上都有廣泛的應(yīng)用，當(dāng)然矩陣有著不足的地方就是空間和時(shí)間復(fù)雜度都維持在N2上，比如1w個(gè)數(shù)字建立一個(gè)矩陣，在內(nèi)存中會(huì)占用1w*1w=1億的類型空間，這時(shí)就會(huì)遇到outofmemory。。。那么面臨的一個(gè)問題就是如何來壓縮矩陣，當(dāng)然壓縮的方式有很多種，這里就介紹一個(gè)順序表的壓縮方式：三元組。一：三元組 有時(shí)候我們的矩陣中只有零星的一些非零元素，其余的都是零元素，那么我們稱之為稀疏矩陣，當(dāng)然沒有絕對(duì)的說有多少個(gè)零元素才算稀疏。針對(duì)上面的這個(gè)無規(guī)律的存放非零元素，三元組提出了一種方法，就是僅僅記錄矩陣中的非零元素以及它的行，列以及...閱讀全文

posted @ 2013-03-28 19:02 一線碼農(nóng) 閱讀(3228) | 編輯

經(jīng)典算法題每日演練——第十九題 雙端隊(duì)列

摘要: 話說大學(xué)的時(shí)候老師說妹子比工作重要~，工作可以再換，妹子這個(gè)。。。所以。。。這兩個(gè)月也就一直忙著Fall in love，嗨，慢慢調(diào)整心態(tài)吧，這篇就選一個(gè)簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)聊一聊，話說有很多數(shù)據(jù)結(jié)構(gòu)都在玩組合拳，比如說：塊狀鏈表，塊狀數(shù)組，當(dāng)然還有本篇的雙端隊(duì)列，是的，它就是棧和隊(duì)列的組合體。一：概念我們知道普通隊(duì)列是限制級(jí)的一端進(jìn)，另一端出的FIFO形式，棧是一端進(jìn)出的LIFO形式，而雙端隊(duì)列就沒有這樣的限制級(jí)，也就是我們可以在隊(duì)列兩端進(jìn)行插入或者刪除操作。二：編碼1：定義結(jié)構(gòu)體通常情況下，隊(duì)列的內(nèi)部都是采用數(shù)組來實(shí)現(xiàn)，而且?guī)в袃蓚�(gè)指針head和tail來指向數(shù)組的區(qū)間段，為了充分利用數(shù)組空間.閱讀全文

posted @ 2013-03-20 18:09 一線碼農(nóng) 閱讀(3769) | 編輯

經(jīng)典算法題每日演練——第十八題 外排序

摘要: 說到排序，大家第一反應(yīng)基本上是內(nèi)排序，是的，算法嘛，玩的就是內(nèi)存，然而內(nèi)存是有限制的，總有裝不下的那一天，此時(shí)就可以來玩玩外排序，當(dāng)然在我看來，外排序考驗(yàn)的是一個(gè)程序員的架構(gòu)能力，而不僅僅局限于排序這個(gè)層次。一：N路歸并排序1.概序 我們知道算法中有一種叫做分治思想，一個(gè)大問題我們可以采取分而治之，各個(gè)突破，當(dāng)子問題解決了，大問題也就KO了，還有一點(diǎn)我們知道內(nèi)排序的歸并排序是采用二路歸并的，因?yàn)榉种魏笥蠰ogN層，每層兩路歸并需要N的時(shí)候，最后復(fù)雜度為NlogN，那么外排序我們可以將這個(gè)“二”擴(kuò)大到M，也就是將一個(gè)大文件分成M個(gè)小文件，每個(gè)小文件是有序的，然后對(duì)應(yīng)在內(nèi)存中我們開M個(gè)優(yōu)先隊(duì)...閱讀全文

posted @ 2012-12-19 14:44 一線碼農(nóng) 閱讀(10064) | 編輯

經(jīng)典算法題每日演練——第十七題 Dijkstra算法

摘要: 或許在生活中，經(jīng)常會(huì)碰到針對(duì)某一個(gè)問題，在眾多的限制條件下，如何去尋找一個(gè)最優(yōu)解？可能大家想到了很多諸如“線性規(guī)劃”，“動(dòng)態(tài)規(guī)劃”這些經(jīng)典策略，當(dāng)然有的問題我們可以用貪心來尋求整體最優(yōu)解，在圖論中一個(gè)典型的貪心法求最優(yōu)解的例子就莫過于“最短路徑”的問題。一：概序 從下圖中我要尋找V0到V3的最短路徑，你會(huì)發(fā)現(xiàn)通往他們的兩點(diǎn)路徑有很多：V0->V4->V3，V0->V1->V3，當(dāng)然你會(huì)認(rèn)為前者是你要找的最短路徑，那如果說圖的頂點(diǎn)非常多，你還會(huì)這么輕易的找到嗎？下面我們就要將剛才我們那點(diǎn)貪心的思維系統(tǒng)的整理下。二：構(gòu)建 如果大家已經(jīng)了解Prim算法，那么Dijkstra算閱讀全文

posted @ 2012-12-18 12:14 一線碼農(nóng) 閱讀(6736) | 編輯

經(jīng)典算法題每日演練——第十六題 Kruskal算法

摘要: 這篇我們看看第二種生成樹的Kruskal算法，這個(gè)算法的魅力在于我們可以打一下算法和數(shù)據(jù)結(jié)構(gòu)的組合拳，很有意思的。一：思想 若存在M={0,1,2,3,4,5}這樣6個(gè)節(jié)點(diǎn)，我們知道Prim算法構(gòu)建生成樹是從”頂點(diǎn)”這個(gè)角度來思考的，然后采用“貪心思想”來一步步擴(kuò)大化，最后形成整體最優(yōu)解，而Kruskal算法有點(diǎn)意思，它是站在”邊“這個(gè)角度在思考的，首先我有兩個(gè)集合。1. 頂點(diǎn)集合(vertexs)： 比如M集合中的每個(gè)元素都可以認(rèn)為是一個(gè)獨(dú)根樹（是不是想到了并查集？）。2.邊集合(edges)： 對(duì)圖中的每條邊按照權(quán)值大小進(jìn)行排序。（是不是想到了優(yōu)先隊(duì)列？）好了，下面該如何操作呢？...閱讀全文

posted @ 2012-12-17 00:28 一線碼農(nóng) 閱讀(3865) | 編輯

經(jīng)典算法題每日演練——第十五題 并查集

摘要: 這一篇我們看看經(jīng)典又神奇的并查集，顧名思義就是并起來查，可用于處理一些不相交集合的秒殺。一：場(chǎng)景 有時(shí)候我們會(huì)遇到這樣的場(chǎng)景，比如:M={1,4,6,8},N={2,4,5,7}，我的需求就是判斷{1,2}是否屬于同一個(gè)集合，當(dāng)然實(shí)現(xiàn)方法有很多，一般情況下，普通青年會(huì)做出O(MN)的復(fù)雜度，那么有沒有更輕量級(jí)的復(fù)雜度呢？嘿嘿，并查集就是用來解決這個(gè)問題的。二：操作 從名字可以出來，并查集其實(shí)只有兩種操作，并(Union)和查(Find)，并查集是一種算法，所以我們要給它選擇一個(gè)好的數(shù)據(jù)結(jié)構(gòu)，通常我們用樹來作為它的底層實(shí)現(xiàn)。1.節(jié)點(diǎn)定義 1 #region 樹節(jié)點(diǎn) 2 ...閱讀全文

posted @ 2012-12-16 15:00 一線碼農(nóng) 閱讀(3753) | 編輯

經(jīng)典算法題每日演練——第十四題 Prim算法

摘要: 圖論在數(shù)據(jù)結(jié)構(gòu)中是非常有趣而復(fù)雜的，作為web碼農(nóng)的我，在實(shí)際開發(fā)中一直沒有找到它的使用場(chǎng)景，不像樹那樣的頻繁使用，不過還是準(zhǔn)備仔細(xì)的把圖論全部過一遍。一：最小生成樹 圖中有一個(gè)好玩的東西叫做生成樹，就是用邊來把所有的頂點(diǎn)聯(lián)通起來，前提條件是最后形成的聯(lián)通圖中不能存在回路，所以就形成這樣一個(gè)推理：假設(shè)圖中的頂點(diǎn)有n個(gè)，則生成樹的邊有n-1條，多一條會(huì)存在回路，少一路則不能把所有頂點(diǎn)聯(lián)通起來，如果非要在圖中加上權(quán)重，則生成樹中權(quán)重最小的叫做最小生成樹。對(duì)于上面這個(gè)帶權(quán)無向圖來說，它的生成樹有多個(gè)，同樣最小生成樹也有多個(gè)，因?yàn)槲覀儽鹊氖菣?quán)重的大小。二：Prim算法求最小生成樹的算法有很多...閱讀全文

posted @ 2012-12-12 19:12 一線碼農(nóng) 閱讀(4358) | 編輯

經(jīng)典算法題每日演練——第十三題 赫夫曼樹

摘要: 赫夫曼樹又稱最優(yōu)二叉樹，也就是帶權(quán)路徑最短的樹，，對(duì)于赫夫曼樹，我想大家對(duì)它是非常的熟悉，也知道它的應(yīng)用場(chǎng)景，但是有沒有自己親手寫過，這個(gè)我就不清楚了，不管以前寫沒寫，這一篇我們來玩一把。一：概念赫夫曼樹里面有幾個(gè)概念，也是非常簡(jiǎn)單的，先來看下面的圖：1. 基礎(chǔ)概念<1> 節(jié)點(diǎn)的權(quán)： 節(jié)點(diǎn)中紅色部分就是權(quán)，在實(shí)際應(yīng)用中，我們用“字符”出現(xiàn)的次數(shù)作為權(quán)。<2> 路徑長(zhǎng)度：可以理解成該節(jié)點(diǎn)到根節(jié)點(diǎn)的層數(shù)，比如：“A”到根節(jié)點(diǎn)的路徑長(zhǎng)度為3。<3> 樹的路徑長(zhǎng)度：各個(gè)葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑長(zhǎng)度總和，用WPL標(biāo)記。最后我們要討論的的赫夫曼樹也就是帶權(quán)路徑長(zhǎng)度最小的一棵閱讀全文

posted @ 2012-12-09 14:27 一線碼農(nóng) 閱讀(4998) | 編輯

經(jīng)典算法題每日演練——第十二題 線段樹

摘要: 這一篇我們來看樹狀數(shù)組的加強(qiáng)版線段樹，樹狀數(shù)組能玩的線段樹一樣可以玩，而且能玩的更好，他們?cè)趨^(qū)間求和，最大，平均等經(jīng)典的RMQ問題上有著對(duì)數(shù)時(shí)間的優(yōu)越表現(xiàn)。一：線段樹 線段樹又稱"區(qū)間樹”，在每個(gè)節(jié)點(diǎn)上保存一個(gè)區(qū)間，當(dāng)然區(qū)間的劃分采用折半的思想，葉子節(jié)點(diǎn)只保存一個(gè)值，也叫單元節(jié)點(diǎn)，所以最終的構(gòu)造就是一個(gè)平衡的二叉樹，擁有CURD的O(lgN)的時(shí)間。從圖中我們可以清楚的看到[0-10]被劃分成線段的在樹中的分布情況，針對(duì)區(qū)間[0-N]，最多有2N個(gè)節(jié)點(diǎn)，由于是平衡二叉樹的形式也可以像堆那樣用數(shù)組來玩，不過更加耗費(fèi)空間，為最多4N個(gè)節(jié)點(diǎn)，在針對(duì)RMQ的問題上，我們常常在每個(gè)節(jié)點(diǎn)上增加一閱讀全文

posted @ 2012-12-08 00:37 一線碼農(nóng) 閱讀(3300) | 編輯

經(jīng)典算法題每日演練——第十一題 Bitmap算法

摘要: 在所有具有性能優(yōu)化的數(shù)據(jù)結(jié)構(gòu)中，我想大家使用最多的就是hash表，是的，在具有定位查找上具有O(1)的常量時(shí)間，多么的簡(jiǎn)潔優(yōu)美，但是在特定的場(chǎng)合下：①：對(duì)10億個(gè)不重復(fù)的整數(shù)進(jìn)行排序。②：找出10億個(gè)數(shù)字中重復(fù)的數(shù)字。當(dāng)然我只有普通的服務(wù)器，就算2G的內(nèi)存吧，在這種場(chǎng)景下，我們?cè)撊绾胃玫奶暨x數(shù)據(jù)結(jié)構(gòu)和算法呢？一：?jiǎn)栴}分析 這年頭，大牛們寫的排序算法也就那么幾個(gè)，首先我們算下放在內(nèi)存中要多少G: (10億 * 32)/(1024*1024*1024*8)=3.6G，可憐的2G內(nèi)存直接爆掉，所以各種神馬的數(shù)據(jù)結(jié)構(gòu)都玩不起來了，當(dāng)然使用外排序還是可以解決問題的，由于要走IO所以暫時(shí)剔除，因?yàn)?..閱讀全文

posted @ 2012-12-06 12:59 一線碼農(nóng) 閱讀(12354) | 編輯

經(jīng)典算法題每日演練——第十題 樹狀數(shù)組

摘要: 有一種數(shù)據(jù)結(jié)構(gòu)是神奇的，神秘的，它展現(xiàn)了位運(yùn)算與數(shù)組結(jié)合的神奇魅力，太牛逼的，它就是樹狀數(shù)組，這種數(shù)據(jù)結(jié)構(gòu)不是神人是發(fā)現(xiàn)不了的。一：概序 假如我現(xiàn)在有個(gè)需求，就是要頻繁的求數(shù)組的前n項(xiàng)和，并且存在著數(shù)組中某些數(shù)字的頻繁修改，那么我們?cè)撊绾螌?shí)現(xiàn)這樣的需求？當(dāng)然大家可以往真實(shí)項(xiàng)目上靠一靠。① 傳統(tǒng)方法：根據(jù)索引修改為O(1)，但是求前n項(xiàng)和為O(n)。②空間換時(shí)間方法：我開一個(gè)數(shù)組sum[]，sum[i]=a[1]+....+a[i]，那么有點(diǎn)意思，求n項(xiàng)和為O(1)，但是修改卻成了O(N)，這是因?yàn)槲业腟um[i]中牽 涉的數(shù)據(jù)太多了，那么問題來了，我能不能在相應(yīng)的...閱讀全文

posted @ 2012-12-05 12:50 一線碼農(nóng) 閱讀(5565) | 編輯

經(jīng)典算法題每日演練——第九題 優(yōu)先隊(duì)列

摘要: 前端時(shí)間玩小爬蟲的時(shí)候，我把url都是放在內(nèi)存隊(duì)列里面的，有時(shí)我們?cè)谧トrl的時(shí)候，通過LCS之類的相似度比較，發(fā)現(xiàn)某些url是很重要的，需要后端解析服務(wù)器優(yōu)先處理，針對(duì)這種優(yōu)先級(jí)比較大的url，普通的隊(duì)列還是苦逼的在做FIFO操作，現(xiàn)在我們的需求就是優(yōu)先級(jí)大的優(yōu)先服務(wù)，要做優(yōu)先隊(duì)列，非堆莫屬。一：堆結(jié)構(gòu) 1:性質(zhì) 堆是一種很松散的序結(jié)構(gòu)樹，只保存了父節(jié)點(diǎn)和孩子節(jié)點(diǎn)的大小關(guān)系，并不規(guī)定左右孩子的大小，不像排序樹那樣嚴(yán)格，又因?yàn)槎咽且环N完全二叉樹，設(shè)節(jié)點(diǎn)為i,則i/2是i的父節(jié)點(diǎn)，2i是i的左孩子，2i+1是i的右孩子，所以在實(shí)現(xiàn)方式上可以采用輕量級(jí)的數(shù)組。2：用途 如果大家玩過微...閱讀全文

posted @ 2012-12-03 16:33 一線碼農(nóng) 閱讀(5944) | 編輯

經(jīng)典算法題每日演練——第八題 AC自動(dòng)機(jī)

摘要: 上一篇我們說了單模式匹配算法KMP，現(xiàn)在我們有需求了，我要檢查一篇文章中是否有某些敏感詞，這其實(shí)就是多模式匹配的問題。當(dāng)然你也可以用KMP算法求出，那么它的時(shí)間復(fù)雜度為O(c*(m+n))，c：為模式串的個(gè)數(shù)。m：為模式串的長(zhǎng)度,n:為正文的長(zhǎng)度，那么這個(gè)復(fù)雜度就不再是線性了，我們學(xué)算法就是希望能把要解決的問題優(yōu)化到極致，這不，AC自動(dòng)機(jī)就派上用場(chǎng)了。 其實(shí)AC自動(dòng)機(jī)就是Trie樹的一個(gè)活用，活用點(diǎn)就是灌輸了kmp的思想，從而再次把時(shí)間復(fù)雜度優(yōu)化到線性的O(N)，剛好我前面的文章已經(jīng)說過了Trie樹和KMP，這里還是默認(rèn)大家都懂。一：構(gòu)建AC自動(dòng)機(jī)同樣我也用網(wǎng)上的經(jīng)典例子，現(xiàn)有say sh..閱讀全文

posted @ 2012-12-02 16:11 一線碼農(nóng) 閱讀(6678) | 編輯

經(jīng)典算法題每日演練——第七題 KMP算法

摘要: 在大學(xué)的時(shí)候，應(yīng)該在數(shù)據(jù)結(jié)構(gòu)里面都看過kmp算法吧，不知道有多少老師對(duì)該算法是一筆帶過的，至少我們以前是的，確實(shí)kmp算法還是有點(diǎn)饒人的，如果說紅黑樹是變態(tài)級(jí)的，那么kmp算法比紅黑樹還要變態(tài)，很抱歉，每次打kmp的時(shí)候，輸入法總是提示“看毛片”三個(gè)字,嘿嘿，就叫“看毛片算法”吧。一：BF算法 如果讓你寫字符串的模式匹配，你可能會(huì)很快的寫出樸素的bf算法，至少問題是解決了，我想大家很清楚的知道它的時(shí)間復(fù)雜度為O（MN），原因很簡(jiǎn)單，主串和模式串失配的時(shí)候，我們總是將模式串的第一位與主串的下一個(gè)字符進(jìn)行比較，所以復(fù)雜度高在主串每次失配的時(shí)候都要回溯，圖我就省略了。二：KMP算法 剛才我們...閱讀全文

posted @ 2012-12-01 01:57 一線碼農(nóng) 閱讀(8293) | 編輯

經(jīng)典算法題每日演練——第六題 協(xié)同推薦SlopeOne 算法

摘要: 相信大家對(duì)如下的Category都很熟悉，很多網(wǎng)站都有類似如下的功能，“商品推薦”,"猜你喜歡“，在實(shí)體店中我們有導(dǎo)購來為我們服務(wù)，在網(wǎng)絡(luò)上我們需要同樣的一種替代物，如果簡(jiǎn)簡(jiǎn)單單的在數(shù)據(jù)庫里面去撈，去比較，幾乎是完成不了的,這時(shí)我們就需要一種協(xié)同推薦算法，來高效的推薦瀏覽者喜歡的商品。一：概念 SlopeOne的思想很簡(jiǎn)單，就是用均值化的思想來掩蓋個(gè)體的打分差異，舉個(gè)例子說明一下：在這個(gè)圖中，系統(tǒng)該如何計(jì)算“王五“對(duì)”電冰箱“的打分值呢？剛才我們也說了，slopeone是采用均值化的思想,也就是：R王五=4-{[(5-10)+(4-5)]/2}=7 。下面我們看看多于兩項(xiàng)的商品，如.閱讀全文

posted @ 2012-11-22 14:43 一線碼農(nóng) 閱讀(6691) | 編輯

經(jīng)典算法題每日演練——第五題 字符串相似度

摘要: 這篇我們看看最長(zhǎng)公共子序列的另一個(gè)版本，求字符串相似度(編輯距離)，我也說過了，這是一個(gè)非常實(shí)用的算法，在DNA對(duì)比，網(wǎng)頁聚類等方面都有用武之地。一：概念 對(duì)于兩個(gè)字符串A和B，通過基本的增刪改將字符串A改成B，或者將B改成A，在改變的過程中我們使用的最少步驟稱之為“編輯距離”。比如如下的字符串：我們通過種種操作，痙攣之后編輯距離為3，不知道你看出來了沒有？二：解析 可能大家覺得有點(diǎn)復(fù)雜，不好理解，我們?cè)囍堰@個(gè)大問題拆分掉，將"字符串 vs 字符串“，分解成”字符 vs 字符串“，再分解成”字符 vs 字符“。<1> ”字符“vs”字符“ 這種情況是最簡(jiǎn)單的了，比如”A閱讀全文

posted @ 2012-11-11 23:45 一線碼農(nóng) 閱讀(7510) | 編輯

經(jīng)典算法題每日演練——第四題 最長(zhǎng)公共子序列

摘要: 一： 作用 最長(zhǎng)公共子序列的問題常用于解決字符串的相似度，是一個(gè)非常實(shí)用的算法，作為碼農(nóng)，此算法是我們的必備基本功。二：概念 舉個(gè)例子，cnblogs這個(gè)字符串中子序列有多少個(gè)呢？很顯然有27個(gè)，比如其中的cb,cgs等等都是其子序列，我們可以看出子序列不見得一定是連續(xù)的，連續(xù)的那是子串。 我想大家已經(jīng)了解了子序列的概念，那現(xiàn)在可以延伸到兩個(gè)字符串了，那么大家能夠看出：cnblogs和belong的公共子序列嗎？在你找出的公共子序列中，你能找出最長(zhǎng)的公共子序列嗎？從圖中我們看到了最長(zhǎng)公共子序列為blog，仔細(xì)想想我們可以發(fā)現(xiàn)其實(shí)最長(zhǎng)公共子序列的個(gè)數(shù)不是唯一的，可能會(huì)有兩個(gè)以上，但是長(zhǎng)度...閱讀全文

posted @ 2012-11-11 00:55 一線碼農(nóng) 閱讀(40037) | 編輯

經(jīng)典算法題每日演練——第三題 猴子吃桃

摘要: 猴子第一天摘下若干個(gè)桃子，當(dāng)即吃了一半，還不過癮就多吃了一個(gè)。第二天早上又將剩下的桃子吃了一半，還是不過癮又多吃了一個(gè)。以后每天都吃前一天剩下的一半再加一個(gè)。到第10天剛好剩一個(gè)。問猴子第一天摘了多少個(gè)桃子？分析: 這是一套非常經(jīng)典的算法題，這個(gè)題目體現(xiàn)了算法思想中的遞推思想，遞歸有兩種形式，順推和逆推，針對(duì)遞推，只要 我們找到遞推公式，問題就迎刃而解了。 令S10=1，容易看出S9=2(S10+1)，簡(jiǎn)化一下 S9=2S10+2 S8=2S9+2 ..... Sn=2Sn+1+2遙想公瑾當(dāng)年，老師說遞歸是最...閱讀全文

posted @ 2012-08-08 12:40 一線碼農(nóng) 閱讀(13464) | 編輯

經(jīng)典算法題每日演練——第二題 五家共井

摘要: 古代數(shù)學(xué)巨著《九章算數(shù)》中有這么一道題叫“五家共井，甲二綆（汲水用的井繩）不足，如（接上）乙一綆；乙三綆不足，如丙一綆；丙四綆不足，如丁一綆；丁五綆不足，如戊一綆；戊六綆不足，如甲一綆，皆及。意思就是說五家人共用一口井，甲家的繩子用兩條不夠，還要再用乙家的繩子一條才能打到井水；乙家的繩子用三條不夠，還要再用丙家的繩子一條才能打到井水；丙家的繩子用四條不夠，還要再用丁家的繩子一條才能打到井水；丁家的繩子用五條不夠，還要再用戊家的繩子一條才能打到井水；戊家的繩子用六條不夠，還要再用甲家的繩子一條才能打到井水。最后問：井有多深？每家的繩子各有多長(zhǎng)？分析：同樣這套題也是屬于不定方程，拿這個(gè)題...閱讀全文

posted @ 2012-08-06 16:57 一線碼農(nóng) 閱讀(10715) | 編輯

經(jīng)典算法題每日演練——第一題 百錢買百雞

摘要: 百錢買百雞的問題算是一套非常經(jīng)典的不定方程的問題，題目很簡(jiǎn)單：公雞5文錢一只，母雞3文錢一只，小雞3只一文錢，用100文錢買一百只雞,其中公雞，母雞，小雞都必須要有，問公雞，母雞，小雞要買多少只剛好湊足100文錢。分析：估計(jì)現(xiàn)在小學(xué)生都能手工推算這套題，只不過我們用計(jì)算機(jī)來推算，我們可以設(shè)公雞為x，母雞為y，小雞為z，那么我們 可以得出如下的不定方程， x+y+z=100, 5x+3y+z/3=100， 下面再看看x，y，z的取值范圍。 由于只有100文錢，則5x<100 => 0<x<20, 同理 0<y<33,那么z=100-x-y， 好，我們...閱讀全文

posted @ 2012-08-05 20:22 一線碼農(nóng) 閱讀(28091) | 編輯

  本文關(guān)鍵詞：算法，由筆耕文化傳播整理發(fā)布。