摘要：
定義 BM 算法是由 Boyer 和 Moore 兩人提出的一種高效的字符串匹配算法，被認為是一種亞線性算法（即平均的時間復雜度低于線性級別），其時間效率在一般情況下甚至比 KMP 還要快 3 ~ 5 倍。 原理 BM 算法跟其他的字符串匹配算法相比，其中一個不同之處是在比對字符的時候，掃描的順序不 閱讀全文
摘要：
定義 Dijkstra（讀音：/'da?kstr?/）算法，是用來求解一個邊帶權圖中從某個頂點出發到達其余各個頂點的最短距離的算法。（為表達簡便，下文中“起點（源點）到某個頂點的距離”簡稱為“某個頂點的距離”） 限制條件：各個邊的權不能為負。 原理 假設s，v1，v2，...，vn（以下簡稱P1）為 閱讀全文
摘要：
相信不少人在學數據結構的時候都被KMP算法搞的迷迷糊糊的，原理看的似懂非懂，代碼寫不出來，或者寫出來了也不知道為什么就可以這么寫。本文力求盡可能通俗詳細的講解KMP算法，讓你不再受到KMP算法的困擾。 暴力匹配的痛點 所謂暴力匹配，就是從文本串的首端開始依次檢查子串是否與模式串匹配，如果不匹配就將模 閱讀全文
摘要：
閱讀本文前，請確保您已經了解了二叉搜索樹的相關內容（如定義、增刪查改的方法以及效率等）。否則，建議您先學習二叉搜索樹。本文假定您對二叉搜索樹有了足夠的了解。 效率？ 眾所周知，在平衡條件下，對二叉搜索樹中的元素進行增刪查改，時間效率為$O(log(n))$。 然而，理想很豐滿，現實很骨感，實際上，二 閱讀全文
摘要：
在有向圖的拓撲排序——BFS這篇文章中，介紹了有向圖的拓撲排序的定義以及使用廣度優先搜索（BFS）對有向圖進行拓撲排序的方法，這里再介紹另一種方法：深度優先搜索（DFS）。 算法 考慮下面這張圖： 首先，我們需要維護一個棧，用來存放DFS到的節點。另外規定每個節點有兩個狀態：已訪問（這里用藍綠色表示 閱讀全文
摘要：
定義 如果在一個圖中，刪除某個節點連同與之關聯的邊，會導致整個圖的連通分支數增加，那么這個節點叫做 割點（Articulation Point, Cut Vertex） 如下圖： 整個圖的連通分支數為1，但是刪除節點3后，整個圖就“分裂”成了2個連通分支： 因此，節點3是整個圖的割點。 方法 一個很 閱讀全文
摘要：
假設你有n個任務要做，其中某些任務需要在另外一些任務之前完成，你該如何規劃你的任務，使得按照你的規劃依次做下去就能完成你的所有任務？ 定義 拓撲排序（Topological sorting, toposort）：給定一個有向無環圖，將所有節點排成一個線性序列，在這個序列中只有從前面的節點指向后面的節 閱讀全文
摘要：
背景 假如我們要傳輸一段文本，比如“hello”，怎么辦？最容易想到的方法是，直接依次傳輸每個字符的Unicode，每個字符都用8個比特或以上來傳輸。這樣就需要5*8=40個比特來傳輸。但是如果我們要傳輸一段很長的文本怎么辦呢？產生的數據量是非常大的，為了節省成本，我們必須要把數據壓縮，并且能保證對 閱讀全文
摘要：
二叉樹的前序、中序、后序遍歷的遞歸版本非常好理解，在這里就不在贅述了。這里主要講迭代版本。 事實上，計算機在進行遞歸調用時，會隱式的維護一個棧（叫做調用棧，Call Stack）， 調用函數就把局部變量、入參、返回地址（合起來叫做棧幀，Stack Frame）一同入棧，從函數返回就出棧。 而迭代版本 閱讀全文
摘要：
定義 迭代器模式（Iterator pattern）：用于順序訪問集合對象里的每一個元素，不用暴露集合是怎樣存儲元素的。 舉例 某個班級有若干個學生，現在需要統計這些學生的平均分數。假設所有學生的分數是用數組存儲的： int totalScore(int *array, int n) { int s 閱讀全文