|
話雖如此，我決定在CSDN新星計劃挑戰(zhàn)期間將我所了解的數(shù)據(jù)結(jié)構(gòu)和算法集中起來,。本文旨在使 DSA 看起來不像人們認為的那樣令人生畏。它包括 15 個最有用的數(shù)據(jù)結(jié)構(gòu)和 15 個最重要的算法，可以幫助您在學習中和面試中取得好成績并提高您的編程競爭力,。后面等我還會繼續(xù)對這些數(shù)據(jù)結(jié)構(gòu)和算法進行進一步詳細地研究講解,。 目錄一、數(shù)據(jù)結(jié)構(gòu)1. 數(shù)組（Arrays）
數(shù)組是最簡單也是最常見的數(shù)據(jù)結(jié)構(gòu),。它們的特點是可以通過索引（位置）輕松訪問元素,。 它們是做什么用的？ 想象一下有一排劇院椅。每把椅子都分配了一個位置（從左到右），因此每個觀眾都會從他將要坐的椅子上分配一個號碼,。這是一個數(shù)組,。將問題擴展到整個劇院（椅子的行和列），您將擁有一個二維數(shù)組（矩陣）！ 特性
2. 鏈表（Linked Lists）
鏈表是線性數(shù)據(jù)結(jié)構(gòu)，就像數(shù)組一樣,。鏈表和數(shù)組的主要區(qū)別在于鏈表的元素不存儲在連續(xù)的內(nèi)存位置,。它由節(jié)點組成——實體存儲當前元素的值和下一個元素的地址引用。這樣，元素通過指針鏈接,。 它們是做什么用的？ 鏈表的一個相關(guān)應用是瀏覽器的上一頁和下一頁的實現(xiàn),。雙鏈表是存儲用戶搜索顯示的頁面的完美數(shù)據(jù)結(jié)構(gòu)。 特性
3. 堆棧（Stacks）
堆棧是一種抽象數(shù)據(jù)類型，它形式化了受限訪問集合的概念。該限制遵循 LIFO（后進先出）規(guī)則,。因此，添加到堆棧中的最后一個元素是您從中刪除的第一個元素,。 堆?？梢允褂脭?shù)組或鏈表來實現(xiàn)。 它們是做什么用的？ 現(xiàn)實生活中最常見的例子是在食堂中將盤子疊放在一起,。位于頂部的板首先被移除,。放置在最底部的盤子是在堆棧中保留時間最長的盤子。 堆棧最有用的一種情況是您需要獲取給定元素的相反順序,。只需將它們?nèi)客迫攵褩?#xff0c;然后彈出它們,。 另一個有趣的應用是有效括號問題。給定一串括號，您可以使用堆棧檢查它們是否匹配,。 特性
4. 隊列（Queues）
它們是做什么用的？ 這種抽象數(shù)據(jù)類型 (ADT) 的最佳用途當然是模擬現(xiàn)實生活中的隊列,。例如，在呼叫中心應用程序中，隊列用于保存等待從顧問那里獲得幫助的客戶——這些客戶應該按照他們呼叫的順序獲得幫助,。 一種特殊且非常重要的隊列類型是優(yōu)先級隊列。元素根據(jù)與它們關(guān)聯(lián)的“優(yōu)先級”被引入隊列：具有最高優(yōu)先級的元素首先被引入隊列,。這個 ADT 在許多圖算法（Dijkstra 算法,、BFS、Prim 算法,、霍夫曼編碼 - 更多關(guān)于它們的信息）中是必不可少的,。它是使用堆實現(xiàn)的。 另一種特殊類型的隊列是deque 隊列（雙關(guān)語它的發(fā)音是“deck”）,?？梢詮年犃械膬啥瞬迦?刪除元素。 特性
5. Map 和 哈希表（Hash Table）
Maps （dictionaries）是包含鍵集合和值集合的抽象數(shù)據(jù)類型。每個鍵都有一個與之關(guān)聯(lián)的值,。 哈希表是一種特殊類型的映射,。它使用散列函數(shù)生成一個散列碼，放入一個桶或槽數(shù)組：鍵被散列，結(jié)果散列指示值的存儲位置。 最常見的散列函數(shù)（在眾多散列函數(shù)中）是模常數(shù)函數(shù),。例如，如果常量是 6，則鍵 x 的值是x%6,。 理想情況下，散列函數(shù)會將每個鍵分配給一個唯一的桶，但他們的大多數(shù)設計都采用了不完善的函數(shù)，這可能會導致具有相同生成值的鍵之間發(fā)生沖突。這種碰撞總是以某種方式適應的,。 它們是做什么用的？ Maps 最著名的應用是語言詞典,。語言中的每個詞都為其指定了定義。它是使用有序映射實現(xiàn)的（其鍵按字母順序排列）。 通訊錄也是一張Map,。每個名字都有一個分配給它的電話號碼,。 另一個有用的應用是值的標準化。假設我們要為一天中的每一分鐘（24 小時 = 1440 分鐘）分配一個從 0 到 1439 的索引,。哈希函數(shù)將為h(x) = x.小時*60+x.分鐘,。 特性
術(shù)語：
因為maps 是使用自平衡紅黑樹實現(xiàn)的（文章后面會解釋），所以所有操作都在 O(log n) 內(nèi)完成；所有哈希表操作都是常量,。 6. 圖表（Graphs）
圖是表示一對兩個集合的非線性數(shù)據(jù)結(jié)構(gòu)：G={V, E}，其中 V 是頂點（節(jié)點）的集合，而 E 是邊（箭頭）的集合,。節(jié)點是由邊互連的值 - 描述兩個節(jié)點之間的依賴關(guān)系（有時與成本/距離相關(guān)聯(lián)）的線,。 圖有兩種主要類型：有向圖和無向圖,。在無向圖中，邊(x, y)在兩個方向上都可用：(x, y)和(y, x)。在有向圖中，邊(x, y)稱為箭頭，方向由其名稱中頂點的順序給出：箭頭(x, y)與箭頭(y, x) 不同,。 它們是做什么用的？ 圖是各種類型網(wǎng)絡的基礎：社交網(wǎng)絡（如 weixin,、csdn、weibo），甚至是城市街道網(wǎng)絡,。社交媒體平臺的每個用戶都是一個包含他/她的所有個人數(shù)據(jù)的結(jié)構(gòu)——它代表網(wǎng)絡的一個節(jié)點,。weixin 上的好友關(guān)系是無向圖中的邊（因為它是互惠的），而在 CSDN 或 weibo上，帳戶與其關(guān)注者/關(guān)注帳戶之間的關(guān)系是有向圖中的箭頭（非互惠）。 特性 圖論是一個廣闊的領域，但我們將重點介紹一些最知名的概念：
7. 樹（Trees）
一棵樹是一個無向圖，在連通性方面最小（如果我們消除一條邊，圖將不再連接）和在無環(huán)方面最大（如果我們添加一條邊，圖將不再是無環(huán)的） . 所以任何無環(huán)連通無向圖都是一棵樹，但為了簡單起見，我們將有根樹稱為樹,。 根是一個固定節(jié)點，它確定樹中邊的方向，所以這就是一切“開始”的地方。葉子是樹的終端節(jié)點——這就是一切“結(jié)束”的地方,。 它們是做什么用的？ 我們在任何需要描繪層次結(jié)構(gòu)的時候都使用樹,。我們自己的家譜樹就是一個完美的例子。你最古老的祖先是樹的根,。最年輕的一代代表葉子的集合,。 樹也可以代表你工作的公司中的上下級關(guān)系,。這樣您就可以找出誰是您的上級以及您應該管理誰,。 特性
8. 二叉樹（Binary Trees）和二叉搜索樹（Binary Search Trees）
二叉樹是一種特殊類型的樹：每個頂點最多可以有兩個子節(jié)點,。在嚴格二叉樹中，除了葉子之外，每個節(jié)點都有兩個孩子,。具有 n 層的完整二叉樹具有所有2?-1 個可能的節(jié)點,。 二叉搜索樹是一棵二叉樹，其中節(jié)點的值屬于一個完全有序的集合——任何任意選擇的節(jié)點的值都大于左子樹中的所有值，而小于右子樹中的所有值,。 它們是做什么用的？ BT 的一項重要應用是邏輯表達式的表示和評估,。每個表達式都可以分解為變量/常量和運算符,。這種表達式書寫方法稱為逆波蘭表示法 (RPN),。這樣，它們就可以形成一個二叉樹，其中內(nèi)部節(jié)點是運算符，葉子是變量/常量——它被稱為抽象語法樹（AST）,。 BST 經(jīng)常使用，因為它們可以快速搜索鍵屬性,。AVL 樹,、紅黑樹,、有序集和映射是使用 BST 實現(xiàn)的。 特性 BST 有三種類型的 DFS 遍歷：
9. AVL樹（Adelson-Velsky and Landis Trees ）
所有這些類型的樹都是自平衡二叉搜索樹,。不同之處在于它們以對數(shù)時間平衡高度的方式,。 AVL 樹在每次插入/刪除后都是自平衡的，因為節(jié)點的左子樹和右子樹的高度之間的模塊差異最大為 1,。 AVL 以其發(fā)明者的名字命名：Adelson-Velsky 和 ??Landis,。 在紅黑樹中，每個節(jié)點存儲一個額外的代表顏色的位，用于確保每次插入/刪除操作后的平衡。 在 Splay 樹中，最近訪問的節(jié)點可以快速再次訪問，因此任何操作的攤銷時間復雜度仍然是 O(log n)。 它們是做什么用的？ AVL 似乎是數(shù)據(jù)庫理論中最好的數(shù)據(jù)結(jié)構(gòu)。 RBT（紅黑樹） 用于組織可比較的數(shù)據(jù)片段，例如文本片段或數(shù)字,。在 Java 8 版本中，HashMap 是使用 RBT 實現(xiàn)的。計算幾何和函數(shù)式編程中的數(shù)據(jù)結(jié)構(gòu)也是用 RBT 構(gòu)建的,。 在 Windows NT 中（在虛擬內(nèi)存、網(wǎng)絡和文件系統(tǒng)代碼中），Splay 樹用于緩存、內(nèi)存分配器,、垃圾收集器,、數(shù)據(jù)壓縮,、繩索（替換用于長文本字符串的字符串）。 特性
10.堆（Heaps）
最小堆是一棵二叉樹，其中每個節(jié)點的值都大于或等于其父節(jié)點的值： 還有一個實現(xiàn)相反關(guān)系的最大堆。 二叉堆是一棵完整的二叉樹（它的所有層都被填充，除了最后一層）,。 它們是做什么用的？ 正如我們幾天前討論過的，優(yōu)先隊列可以使用二叉堆有效地實現(xiàn)，因為它支持 O(log n) 時間內(nèi)的 任何時候您需要快速訪問最大/最小項目，堆都是最好的選擇。 堆也是堆排序算法的基礎,。 特性
11.字典樹（Tries）
trie 是一種高效的信息檢索數(shù)據(jù)結(jié)構(gòu)。也稱為前綴樹，它是一種搜索樹，允許以 O(L) 時間復雜度插入和搜索，其中 L 是鍵的長度,。 如果我們將密鑰存儲在一個平衡良好的 BST 中，它將需要與 L * log n 成正比的時間，其中 n 是樹中的密鑰數(shù)量,。這樣，與 BST 相比，trie 是一種更快的數(shù)據(jù)結(jié)構(gòu)（使用 O(L)），但代價是 trie 存儲要求,。 它們是做什么用的？ 樹主要用于存儲字符串及其值。它最酷的應用程序之一是在 Google 搜索欄中鍵入自動完成和自動建議,。特里是最好的選擇，因為它是最快的選擇：如果我們不使用特里，更快的搜索比節(jié)省的存儲更有價值,。 通過在字典中查找單詞或在同一文本中查找該單詞的其他實例，也可以使用 trie 來完成鍵入單詞的正字法自動更正。 特性
空間復雜度實際上是一個缺點： 12. 段樹（Segment Trees）
段樹是一個完整的二叉樹，可以有效地回答查詢，同時仍然可以輕松修改其元素,。 給定數(shù)組中索引 i 上的每個元素代表一個用[i, i]間隔標記的葉子。將其子節(jié)點分別標記為[x, y]或[y, z]的節(jié)點將具有[x, z]區(qū)間作為標簽,。因此，給定 n 個元素（0-indexed），線段樹的根將被標記為[0, n-1],。 它們是做什么用的？ 它們在可以使用分而治之（我們將要討論的第一個算法概念）解決的任務中非常有用，并且還可能需要更新其元素。這樣，在更新元素時??，包含它的任何區(qū)間也會被修改，因此復雜度是對數(shù)的,。例如，n 個給定元素的總和/最大值/最小值是線段樹最常見的應用,。如果元素更新正在發(fā)生，二分搜索也可以使用段樹。 特性
13. 樹狀數(shù)組（Fenwick Trees）
fenwick 樹，也稱為二叉索引樹 (BIT)，是一種也用于高效更新和查詢的數(shù)據(jù)結(jié)構(gòu),。與 Segment Trees 相比，BITs 需要更少的空間并且更容易實現(xiàn)。 它們是做什么用的？ BIT 用于計算前綴和——第 i 個位置的元素的前綴和是從第一個位置到第 i 個元素的總和,。它們使用數(shù)組表示，其中每個索引都以二進制系統(tǒng)表示,。例如，索引 10 相當于十進制系統(tǒng)中的索引 2。 特性
14. 并查集（Disjoint Set Union）
我們有 n 個元素，每個元素代表一個單獨的集合,。并查集 (DSU) 允許我們做兩個操作： 1.UNION — 組合任意兩個集合（或者統(tǒng)一兩個不同元素的集合，如果它們不是來自同一個集合）； 它們是做什么用的？ 并查集（DSU） 在圖論中非常重要,。您可以檢查兩個頂點是否來自同一個連接組件，或者甚至可以統(tǒng)一兩個連接組件,。 讓我們以城市和城鎮(zhèn)為例。由于人口和經(jīng)濟增長的鄰近城市正在擴張，它們可以輕松創(chuàng)建大都市,。因此，兩個城市合并在一起，他們的居民住在同一個大都市,。我們還可以通過調(diào)用 FIND 函數(shù)來檢查一個人居住在哪個城市。 特性
15. 最小生成樹（Minimum Spanning Trees）
給定一個連通圖和無向圖，該圖的生成樹是一個子圖，它是一棵樹并將所有節(jié)點連接在一起,。單個圖可以有許多不同的生成樹。加權(quán),、連通和無向圖的最小生成樹 (MST) 是權(quán)重（成本）小于或等于其他所有生成樹權(quán)重的生成樹。生成樹的權(quán)重是賦予生成樹每條邊的權(quán)重之和,。 它們是做什么用的？ 最小生成樹（MST ）問題是一個優(yōu)化問題，一個最小成本問題,。有了路線網(wǎng)，我們可以認為影響n個城市之間建立國道的因素之一是相鄰兩個城市之間的最小距離。 國家路線就是這樣，由道路網(wǎng)絡圖的 MST 表示,。 特性 作為一棵樹，具有
二,、算法1.分治算法（Divide and Conquer）分而治之（DAC）本身并不是一個特定的算法，而是在深入研究其他主題之前需要了解的重要算法類別。它用于解決可以劃分為與原始問題相似但規(guī)模較小的子問題的問題,。然后 DAC 遞歸地求解它們，最后合并結(jié)果以找到問題的解決方案,。 它分為三個階段：
它是干什么用的？ 分治算法（DAC） 的一種實際應用是使用多個處理器進行并行編程，因此子問題在不同的機器上執(zhí)行,。 DAC 是許多算法的基礎，例如快速排序,、合并排序、二分搜索或快速乘法算法,。 特性
2. 排序算法（Sorting Algorithms）排序算法用于根據(jù)元素上的比較運算符重新排列給定元素（來自數(shù)組或列表）。當我們提到一個排序數(shù)組時，我們通常會想到升序（比較運算符是“<”）,。排序有多種類型，具有不同的時間和空間復雜度,。其中一些是基于比較的，有些則不是。以下是最流行/最有效的排序方法： 冒泡排序（Bubble Sort）冒泡排序是最簡單的排序算法之一,。它基于相鄰元素之間的重復交換（如果它們的順序錯誤）,。它是穩(wěn)定的，它的時間復雜度是 O(n2) 并且它需要 O(1) 輔助空間。 計數(shù)排序（Counting Sort）計數(shù)排序不是基于比較的排序,。它基本上是使用每個元素的頻率（一種散列），確定最小值和最大值，然后在它們之間迭代以根據(jù)其頻率放置每個元素,。它在 O(n) 中完成，空間與數(shù)據(jù)范圍成正比。如果輸入范圍不明顯大于元素數(shù)量，則它是有效的,。 快速排序（Quick Sort）快速排序是分而治之的一個應用,。它基于選擇一個元素作為樞軸（第一個、最后一個或中間值），然后交換元素以將樞軸放置在所有小于它的元素和所有大于它的元素之間,。它沒有額外的空間和 O(n*log n) 時間復雜度——基于比較的方法的最佳復雜度,。 歸并排序（Merge Sort）歸并排序也是一個分而治之的應用程序。它將數(shù)組分成兩半，對每一半進行排序，然后合并它們,。它的時間復雜度也是 O(n*log n)，所以它也像 Quick Sort 一樣超快，但不幸的是它需要 O(n) 額外空間來同時存儲兩個子數(shù)組，最后合并它們,。 基數(shù)排序（Radix Sort）基數(shù)排序使用計數(shù)排序作為子程序，因此它不是基于比較的算法。我們怎么知道CS是不夠的？假設我們必須對[1, n2] 中的元素進行排序,。使用 CS，我們需要 O(n2),。我們需要一個線性算法——O(n+k)，其中元素在[1, k]范圍內(nèi)。它從最不重要的一個（單位）開始，到最重要的（十,、百等）對元素進行逐位排序,。額外空間（來自 CS）：O(n)。 3. 搜索算法（Searching Algorithms）搜索算法旨在檢查數(shù)據(jù)結(jié)構(gòu)中元素的存在，甚至返回它,。有幾種搜索方法，但這里是最受歡迎的兩種： 線性搜索（Linear Search）該算法的方法非常簡單：您從數(shù)據(jù)結(jié)構(gòu)的第一個索引開始搜索您的值,。您將它們一一比較，直到您的值和當前元素相等。如果該特定值不在 DS 中，則返回 -1。 時間復雜度： 二分查找（Binary Search）BS 是一種基于分而治之的高效搜索算法,。不幸的是，它只適用于排序的數(shù)據(jù)結(jié)構(gòu),。作為一種 DAC 方法，您連續(xù)將 DS 分成兩半，并將搜索中的值與中間元素的值進行比較。如果它們相等，則搜索結(jié)束,。無論哪種方式，如果您的值大于/小于它，搜索應該繼續(xù)在右/左半部分,。 時間復雜度： 4. 埃氏篩法（Sieve of Eratosthenes）給定一個整數(shù) n，打印所有小于或等于 n 的素數(shù)。 該方法使用頻率列表/映射來標記[0, n]范圍內(nèi)每個數(shù)字的素數(shù)：如果 x 是素數(shù)，則ok[x]=0，否則ok[x]=1,。 我們開始從列表中選擇每個素數(shù)，并用 1 標記列表中的倍數(shù)——這樣，我們選擇未標記的 (0) 數(shù)。最后，我們可以在 O(1) 中輕松回答任意數(shù)量的查詢,。 經(jīng)典算法在許多應用中都是必不可少的，但我們可以進行一些優(yōu)化,。首先，我們很容易注意到 2 是唯一的偶素數(shù)，因此我們可以單獨檢查它的倍數(shù)，然后在范圍內(nèi)迭代以找到從 2 到 2 的素數(shù)。其次，很明顯，對于數(shù)字 x，我們之前在迭代 2,、3 等時已經(jīng)檢查了 2x,、3x、4x 等,。這樣，我們的乘數(shù)檢查 for 循環(huán)每次都可以從 x2 開始,。最后，即使這些倍數(shù)中有一半是偶數(shù)，而且我們也在迭代奇素數(shù)，因此我們可以在倍數(shù)檢查循環(huán)中輕松地從 2x 迭代到 2x。 空間復雜度：O(n) 5. 字符串匹配算法（Knuth-Morris-Pratt）給定長度為 n 的文本和長度為 m 的模式，找出文本中所有出現(xiàn)的模式,。 Knuth-Morris-Pratt 算法 (KMP) 是解決模式匹配問題的有效方法。 KMP 是對樸素解決方案的優(yōu)化：它在 O(n) 中完成，并且當模式具有許多重復的子模式時效果最佳。因此，它也使用滑動窗口，但不是將所有字符與子字符串進行比較，而是不斷尋找當前子模式的最長后綴，這也是它的前綴,。換句話說，每當我們在某些匹配后檢測到不匹配時，我們就已經(jīng)知道下一個窗口文本中的某些字符,。因此，再次匹配它們是沒有用的，因此我們重新開始匹配文本中具有該前綴后的字符的相同字符。我們怎么知道我們應該跳過多少個字符？好吧，我們應該構(gòu)建一個預處理數(shù)組，告訴我們應該跳過多少個字符,。 6.貪婪算法（Greedy）Greedy 方法多用于需要優(yōu)化且局部最優(yōu)解導致全局最優(yōu)解的問題,。 也就是說，當使用 Greedy 時，每一步的最優(yōu)解都會導致整體最優(yōu)解。然而，在大多數(shù)情況下，我們在一個步驟中做出的決定會影響下一步的決定列表,。在這種情況下，必須用數(shù)學方法證明算法,。Greedy 也會在一些數(shù)學問題上產(chǎn)生很好的解決方案，但不是全部（可能無法保證最佳解決方案）！ 貪心算法通常有五個組成部分：
分數(shù)背包問題 給定n個物品的重量和價值，我們需要將這些物品放入容量為W的背包中，以獲得背包中的最大總價值（允許取件物品：一件物品的價值與其重量成正比）,。 貪心方法的基本思想是根據(jù)它們的價值/重量比對所有項目進行排序,。然后，我們可以添加盡可能多的整個項目。當我們發(fā)現(xiàn)一件比背包中剩余重量 (w1) 重 (w2) 的物品時，我們將對其進行分割：僅取出w2-w1以最大化我們的利潤,。保證這個貪心的解決方案是正確的,。 7. 動態(tài)規(guī)劃（Dynamic Programming）動態(tài)規(guī)劃 (DP) 是一種類似于分而治之的方法。它還將問題分解為類似的子問題，但它們實際上是重疊和相互依賴的——它們不是獨立解決的。 每個子問題的結(jié)果都可以在以后隨時使用，它是使用記憶（預先計算）構(gòu)建的,。DP 主要用于（時間和空間）優(yōu)化，它基于尋找循環(huán)。 DP 應用包括斐波那契數(shù)列,、河內(nèi)塔,、Roy-Floyd-Warshall、Dijkstra 等,。 下面我們將討論 0-1 背包問題的 DP 解決方案,。 0–1 背包問題給定n個物品的重量和價值，我們需要將這些物品放入容量為W的背包中，以獲得背包中的最大總值（不允許像貪婪解決方案中的那樣分割物品）。 我們稍微分析一下,。
答案存入 8. 最長公共子序列（Longest Common Subsequence）給定兩個序列，找出它們中存在的最長子序列的長度。子序列是以相同的相對順序出現(xiàn)的序列，但不一定是連續(xù)的,。例如，“ 這是動態(tài)規(guī)劃的另一個應用,。LCS 算法使用 DP 來解決上述問題。 實際的子問題是要分別從序列 A 中的索引 i 開始，分別從序列 B 中的索引 j 中找到最長公共子序列,。 接下來，我們將構(gòu)建 DP 結(jié)構(gòu) 遞推關(guān)系非常簡單直觀,。為簡單起見，我們將考慮兩個序列都是 1 索引的。首先，我們將初始化 時間復雜度： 9. 最長遞增子序列（Longest Increasing Subsequence）給定一個包含 n 個元素的序列 A，找到最長子序列的長度，使其所有元素按遞增順序排序,。子序列是以相同的相對順序出現(xiàn)的序列，但不一定是連續(xù)的,。例如，“ LIS 是另一個可以使用動態(tài)規(guī)劃解決的經(jīng)典問題,。 使用數(shù)組l[ ]作為 DP 結(jié)構(gòu)來尋找遞增子序列的最大長度，其中l(wèi)[i]是包含A[i]的遞增子序列的最大長度，其元素來自 在搜索當前元素之后的所有元素之間的最大值時出現(xiàn)了一個優(yōu)化問題,。我們能做的最好的事情是二分搜索最大元素。 為了找到現(xiàn)在已知的最大長度的子序列，我們只需要使用一個額外的數(shù)組 時間復雜度： 10.凸包算法（Convex Hull）給定同一平面中的一組 n 個點，找到包含所有給定點（位于多邊形內(nèi)部或其邊上）的最小面積凸多邊形,。這種多邊形稱為凸包。凸包問題是一個經(jīng)典的幾何，在現(xiàn)實生活中有很多應用,。例如，碰撞避免：如果汽車的凸包避免碰撞，那么汽車也能避免碰撞,。路徑的計算是使用汽車的凸表示完成的。形狀分析也是在凸包的幫助下完成的,。這樣，圖像處理很容易通過匹配模型的凸缺陷樹來完成,。 有一些算法用于尋找凸包，如 Jarvis 算法、Graham 掃描等,。今天我們將討論 Graham 掃描和一些有用的優(yōu)化,。 格雷厄姆掃描按極角對點進行排序——由某個點和其他選定點確定的線的斜率。然后用一個棧來存儲當前時刻的凸包,。當一個點 x 被壓入堆棧時，其他點會被彈出堆棧，直到 x 與最后兩個點所確定的線形成小于 180° 的角度,。最后，引入堆棧的最后一個點關(guān)閉多邊形。由于排序，這種方法的時間復雜度為 O(n*log n),。但是，這種方法在計算斜率時會產(chǎn)生精度誤差,。 一種改進的解決方案具有相同的時間復雜度，但誤差較小，按坐標（x，然后是 y）對點進行排序。然后我們考慮由最左邊和最右邊的點形成的線，并將問題分為兩個子問題,。最后，我們在這條線的每一邊找到了凸包,。所有給定點的凸包是兩個包的重聚。 11. 圖遍歷（Graph Traversals）遍歷圖的問題是指以特定順序訪問所有節(jié)點，通常沿途計算其他有用信息,。 廣度優(yōu)先搜索（Breadth-First Search）廣度優(yōu)先搜索 (BFS) 算法是確定圖是否連通的最常用方法之一——或者換句話說，查找 BFS 源節(jié)點的連通分量,。 BFS 還用于計算源節(jié)點和所有其他節(jié)點之間的最短距離。BFS 的另一個版本是 Lee 算法，用于計算網(wǎng)格中兩個單元格之間的最短路徑,。 該算法首先訪問源節(jié)點，然后訪問將被推入隊列的鄰居,。隊列中的第一個元素被彈出。我們將訪問它的所有鄰居，并將之前未訪問的鄰居推入隊列,。重復該過程直到隊列為空,。當隊列為空時，表示所有可達頂點都已訪問完畢，算法結(jié)束,。 深度優(yōu)先搜索（Depth-First Search）深度優(yōu)先搜索 (DFS) 算法是另一種常見的遍歷方法。在檢查圖形的連通性時，它實際上是最好的選擇,。 首先，我們訪問根節(jié)點并將其壓入堆棧,。雖然堆棧不為空，但我們檢查頂部的節(jié)點。如果該節(jié)點有未訪問的鄰居，則選擇其中一個并將其壓入堆棧,。否則，如果它的所有鄰居都被訪問過，我們就會彈出這個節(jié)點,。當堆棧變空時，算法結(jié)束。 經(jīng)過這樣的遍歷，就形成了一個DFS樹,。DFS 樹有很多應用；最常見的一種是存儲每個節(jié)點的“開始”和“結(jié)束”時間——它進入堆棧的時刻，分別是它從堆棧中彈出的時刻。 12. 弗洛依德算法（Floyd-Warshall）Floyd-Warshall / Roy-Floyd 算法解決了所有對最短路徑問題：找到給定邊加權(quán)有向圖中每對頂點之間的最短距離,。 FW 是一個動態(tài)規(guī)劃應用程序,。DP 結(jié)構(gòu)（矩陣） 時間復雜度： 13. Dijkstra 算法和 Bellman-Ford 算法迪杰斯特拉（Dijkstra） 算法給定一個圖和圖中的一個源頂點，找出從源到給定圖中所有頂點的最短路徑,。 Dijkstra 算法用于在加權(quán)圖中找到這樣的路徑，其中所有的權(quán)重都是正的,。 Dijkstra 是一種貪心算法，它使用以源節(jié)點為根的最短路徑樹（SPT）。SPT 是一種自平衡二叉樹，但該算法可以使用堆（或優(yōu)先級隊列）來實現(xiàn),。我們將討論堆解決方案，因為它的時間復雜度是 O(|E|*log |V|),。這個想法是使用圖形的鄰接列表表示。這樣，節(jié)點將使用 BFS （廣度優(yōu)先搜索）在 O(|V|+|E|) 時間內(nèi)遍歷,。 所有頂點都用 BFS 遍歷，那些最短距離尚未最終確定的頂點被存儲到最小堆（優(yōu)先隊列）中,。 創(chuàng)建最小堆并將每個節(jié)點連同它們的距離值一起推入其中。然后，源成為距離為 0 的堆的根,。其他節(jié)點將無限分配為距離,。當堆不為空時，我們提取最小距離值節(jié)點 x。對于與 x 相鄰的每個頂點 y，我們檢查 y 是否在最小堆中,。在這種情況下，如果距離值大于 (x, y) 的權(quán)重加上 x 的距離值，那么我們更新 y 的距離值,。 貝爾曼-福特（Bellman-Ford）算法正如我們之前所說，Dijkstra 僅適用于正加權(quán)圖。貝爾曼解決了這個問題,。給定一個加權(quán)圖，我們可以檢查它是否包含負循環(huán),。如果沒有，那么我們還可以找到從我們的源到其他源的最小距離（可能為負權(quán)重）。 Bellman-Ford 非常適合分布式系統(tǒng)，盡管它的時間復雜度是 O(|V| |E|),。 我們初始化一個 dist[] 就像在 Dijkstra 中一樣,。對于 *|V|-1次，對于每個(x, y)邊，如果dist[y] > dist[x] + (x, y) 的權(quán)重，那么我們用它更新dist[y]。 我們重復最后一步以可能找到負循環(huán),。這個想法是，如果沒有負循環(huán)，最后一步保證最小距離,。如果有任何節(jié)點在當前步驟中的距離比上一步中的距離短，則檢測到負循環(huán),。 14.克魯斯卡爾算法（Kruskal’s Algorithm）我們之前已經(jīng)討論過什么是最小生成樹。 有兩種算法可以找到圖的 MST：Prim（適用于密集圖）和 Kruskal（適用于大多數(shù)圖）?，F(xiàn)在我們將討論 Kruskal 算法,。 Kruskal 開發(fā)了一種貪心算法來尋找 MST。它在稀有圖上很有效，因為它的時間復雜度是 該算法的方法如下：我們按權(quán)重的遞增順序?qū)λ羞呥M行排序,。然后，選取最小的邊。如果它不與當前 MST 形成循環(huán)，我們將其包括在內(nèi),。否則，丟棄它,。重復最后一步，直到 MST 中有 將邊包含到 MST 中是使用 15. 拓撲排序（Topological Sorting）有向無環(huán)圖 (DAG) 只是一個不包含循環(huán)的有向圖,。 DAG 中的拓撲排序是頂點的線性排序，使得對于每個拱形(x, y)，節(jié)點 x 出現(xiàn)在節(jié)點 y 之前。 顯然，拓撲排序中的第一個頂點是一個入度為 0 的頂點（沒有拱形指向它）,。 另一個特殊屬性是 DAG 沒有唯一的拓撲排序,。 BFS （廣度優(yōu)先搜索）實現(xiàn)遵循此例程：找到一個入度為 0 的節(jié)點并將第一個推入排序。該頂點已從圖中刪除,。由于新圖也是一個 DAG，我們可以重復這個過程,。 在 DFS 期間的任何時候，節(jié)點都可以屬于以下三個類別之一：
如果在 DAG 中的 DFS 期間，節(jié)點 x 具有到節(jié)點 y 的輸出邊，則 y 屬于第一類或第三類,。如果 y 在堆棧上，則(x, y)將結(jié)束一個循環(huán)，這與 DAG 定義相矛盾,。 這個屬性實際上告訴我們一個頂點在它的所有傳出鄰居都被彈出后從堆棧中彈出。因此，要對圖進行拓撲排序，我們需要跟蹤彈出頂點的逆序列表,。 哇，你已經(jīng)到讀了文章的結(jié)尾,。感謝您的閱覽！文章篇幅較長，如果有些出錯的地方還請大家批評指正，可在評論區(qū)留言或者私信我。 關(guān)注作者公眾號【海擁】回復【進群】，免費下載CSDN資源和百度文庫資源 整理不易，最后，不要忘了?或📑支持一下哦 |
|
|
