Java常用的算法有哪些

本文小編為大家詳細介紹“Java常用的算法有哪些”，內容詳細，步驟清晰，細節處理妥當，希望這篇“Java常用的算法有哪些”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。

貪心算法（greedy algorithm）  

經典的應用：比如霍夫曼編碼（Huffman Coding）、Prim 和 Kruskal 最小生成樹算法、還有 Dijkstra 單源最短路徑算法。  

貪心算法解決問題的步驟  

第一步，當我們看到這類問題的時候，首先要聯想到貪心算法：針對一組數據，我們定義了限制值和期望值，希望從中選出幾個數據，在滿足限制值的情況下，期望值最大。  

類比到剛剛的例子，限制值就是重量不能超過 100kg，期望值就是物品的總價值。這組數據就是 5 種豆子。我們從中選出一部分，滿足重量不超過 100kg，并且總價值最大。  

第二步，我們嘗試看下這個問題是否可以用貪心算法解決：每次選擇當前情況下，在對限制值同等貢獻量的情況下，對期望值貢獻最大的數據。  

類比到剛剛的例子，我們每次都從剩下的豆子里面，選擇單價最高的，也就是重量相同的情況下，對價值貢獻最大的豆子。  

第三步，我們舉幾個例子看下貪心算法產生的結果是否是最優的。大部分情況下，舉幾個例子驗證一下就可以了。嚴格地證明貪心算法的正確性，是非常復雜的，需要涉及比較多的數學推理。  

貪心算法不工作的主要原因是，前面的選擇，會影響后面的選擇。  

貪心算法實戰分析  

1. 分糖果  

我們有 m 個糖果和 n 個孩子。我們現在要把糖果分給這些孩子吃，但是糖果少，孩子多（m<n），所以糖果只能分配給一部分孩子。每個糖果的大小不等，這 m 個糖果的大小分別是 s1，s2，s3，……，sm。除此之外，每個孩子對糖果大小的需求也是不一樣的，只有糖果的大小大于等于孩子的對糖果大小的需求的時候，孩子才得到滿足。假設這 n 個孩子對糖果大小的需求分別是 g1，g2，g3，……，gn。如何分配糖果，能盡可能滿足最多數量的孩子？  

我們可以把這個問題抽象成，從 n 個孩子中，抽取一部分孩子分配糖果，讓滿足的孩子的個數（期望值）是最大的。這個問題的限制值就是糖果個數 m。  

我們每次從剩下的孩子中，找出對糖果大小需求最小的，然后發給他剩下的糖果中能滿足他的最小的糖果，這樣得到的分配方案，也就是滿足的孩子個數最多的方案。  

2. 錢幣找零  

這個問題在我們的日常生活中更加普遍。假設我們有 1 元、2 元、5 元、10 元、20 元、50 元、100 元這些面額的紙幣，它們的張數分別是 c1、c2、c5、c10、c20、c50、c100。我們現在要用這些錢來支付 K 元，最少要用多少張紙幣呢？  

生活中，我們肯定是先用面值最大的來支付，如果不夠，就繼續用更小一點面值的，以此類推，最后剩下的用 1 元來補齊。在貢獻相同期望值（紙幣數目）的情況下，我們希望多貢獻點金額，這樣就可以讓紙幣數更少，這就是一種貪心算法的解決思路。  

3. 區間覆蓋  

假設我們有 n 個區間，區間的起始端點和結束端點分別是 [l1, r1]，[l2, r2]，[l3, r3]，……，[ln, rn]。我們從這 n 個區間中選出一部分區間，這部分區間滿足兩兩不相交（端點相交的情況不算相交），最多能選出多少個區間呢？  

這個處理思想在很多貪心算法問題中都有用到，比如任務調度、教師排課等等問題。  

這個問題的解決思路是這樣的：我們假設這 n 個區間中最左端點是 lmin，最右端點是 rmax。這個問題就相當于，我們選擇幾個不相交的區間，從左到右將 [lmin, rmax] 覆蓋上。我們按照起始端點從小到大的順序對這 n 個區間排序。  

我們每次選擇的時候，左端點跟前面的已經覆蓋的區間不重合的，右端點又盡量小的，這樣可以讓剩下的未覆蓋區間盡可能的大，就可以放置更多的區間。這實際上就是一種貪心的選擇方法。  

如何用貪心算法實現霍夫曼編碼？  

霍夫曼編碼用這種不等長的編碼方法，編碼字符。要求各個字符的編碼之間，不會出現某個編碼是另一個編碼前綴的情況。把出現頻率比較多的字符，用稍微短一些的編碼；出現頻率比較少的字符，用稍微長一些的編碼。  

假設我有一個包含 1000 個字符的文件，每個字符占 1 個 byte（1byte=8bits），存儲這 1000 個字符就一共需要 8000bits，那有沒有更加節省空間的存儲方式呢？  

假設我們通過統計分析發現，這 1000 個字符中只包含 6 種不同字符，假設它們分別是 a、b、c、d、e、f。而 3 個二進制位（bit）就可以表示 8 個不同的字符，所以，為了盡量減少存儲空間，每個字符我們用 3 個二進制位來表示。那存儲這 1000 個字符只需要 3000bits 就可以了，比原來的存儲方式節省了很多空間。不過，還有沒有更加節省空間的存儲方式呢？  

a(000)、b(001)、c(010)、d(011)、e(100)、f(101)  

霍夫曼編碼是一種十分有效的編碼方法，廣泛用于數據壓縮中，其壓縮率通常在 20%～90% 之間。  

霍夫曼編碼不僅會考察文本中有多少個不同字符，還會考察每個字符出現的頻率，根據頻率的不同，選擇不同長度的編碼。霍夫曼編碼試圖用這種不等長的編碼方法，來進一步增加壓縮的效率。如何給不同頻率的字符選擇不同長度的編碼呢？根據貪心的思想，我們可以把出現頻率比較多的字符，用稍微短一些的編碼；出現頻率比較少的字符，用稍微長一些的編碼。  

編碼不等長，如何讀出來解析？  

對于等長的編碼來說，我們解壓縮起來很簡單。比如剛才那個例子中，我們用 3 個 bit 表示一個字符。在解壓縮的時候，我們每次從文本中讀取 3 位二進制碼，然后翻譯成對應的字符。但是，霍夫曼編碼是不等長的，每次應該讀取 1 位還是 2 位、3 位等等來解壓縮呢？這個問題就導致霍夫曼編碼解壓縮起來比較復雜。為了避免解壓縮過程中的歧義，霍夫曼編碼要求各個字符的編碼之間，不會出現某個編碼是另一個編碼前綴的情況。  

假設這 6 個字符出現的頻率從高到低依次是 a、b、c、d、e、f。我們把它們編碼下面這個樣子，任何一個字符的編碼都不是另一個的前綴，在解壓縮的時候，我們每次會讀取盡可能長的可解壓的二進制串，所以在解壓縮的時候也不會歧義。經過這種編碼壓縮之后，這 1000 個字符只需要 2100bits 就可以了。  

盡管霍夫曼編碼的思想并不難理解，但是如何根據字符出現頻率的不同，給不同的字符進行不同長度的編碼呢？  

利用大頂堆，根據頻率放字符。  

分治算法  

分治算法（divide and conquer）的核心思想其實就是四個字，分而治之 ，也就是將原問題劃分成 n 個規模較小，并且結構與原問題相似的子問題，遞歸地解決這些子問題，然后再合并其結果，就得到原問題的解。  

分治算法是一種處理問題的思想，遞歸是一種編程技巧。實際上，分治算法一般都比較適合用遞歸來實現。分治算法的遞歸實現中，每一層遞歸都會涉及這樣三個操作：  

• 分解：將原問題分解成一系列子問題；

• 解決：遞歸地求解各個子問題，若子問題足夠小，則直接求解；

• 合并：將子問題的結果合并成原問題。

分治算法能解決的問題，一般需要滿足下面這幾個條件：  

• 原問題與分解成的小問題具有相同的模式；

• 原問題分解成的子問題可以獨立求解，子問題之間沒有相關性

• 具有分解終止條件，也就是說，當問題足夠小時，可以直接求解；

• 可以將子問題合并成原問題，而這個合并操作的復雜度不能太高，否則就起不到減小算法總體復雜度的效果了。

分治算法應用舉例分析  

如何編程求出一組數據的有序對個數或者逆序對個數呢？  

拿每個數字跟它后面的數字比較，看有幾個比它小的。我們把比它小的數字個數記作 k，通過這樣的方式，把每個數字都考察一遍之后，然后對每個數字對應的 k 值求和，最后得到的總和就是逆序對個數。不過，這樣操作的時間復雜度是 O(n^2)。  

我們可以將數組分成前后兩半 A1 和 A2，分別計算 A1 和 A2 的逆序對個數 K1 和 K2，然后再計算 A1 與 A2 之間的逆序對個數 K3。那數組 A 的逆序對個數就等于 K1+K2+K3。借助歸并排序算法  

給 10GB 的訂單文件按照金額排序這樣一個需求？  

我們就可以先掃描一遍訂單，根據訂單的金額，將 10GB 的文件劃分為幾個金額區間。比如訂單金額為 1 到 100 元的放到一個小文件，101 到 200 之間的放到另一個文件，以此類推。這樣每個小文件都可以單獨加載到內存排序，最后將這些有序的小文件合并，就是最終有序的 10GB 訂單數據了。  

回溯算法  

應用場景：深度優先搜索，正則表達式匹配、編譯原理中的語法分析。很多經典的數學問題都可以用回溯算法解決，比如數獨、八皇后、0-1 背包、圖的著色、旅行商問題、全排列等等  

回溯的處理思想，有點類似枚舉搜索。我們枚舉所有的解，找到滿足期望的解。為了有規律地枚舉所有可能的解，避免遺漏和重復，我們把問題求解的過程分為多個階段。每個階段，我們都會面對一個岔路口，我們先隨意選一條路走，當發現這條路走不通的時候（不符合期望的解），就回退到上一個岔路口，另選一種走法繼續走。  

八皇后問題  

我們有一個 8x8 的棋盤，希望往里放 8 個棋子（皇后），每個棋子所在的行、列、對角線都不能有另一個棋子。  

1.0-1 背包  

很多場景都可以抽象成這個問題模型。這個問題的經典解法是動態規劃，不過還有一種簡單但沒有那么高效的解法，那就是今天講的回溯算法。  

我們有一個背包，背包總的承載重量是 Wkg。現在我們有 n 個物品，每個物品的重量不等，并且不可分割。我們現在期望選擇幾件物品，裝載到背包中。在不超過背包所能裝載重量的前提下，如何讓背包中物品的總重量最大？  

對于每個物品來說，都有兩種選擇，裝進背包或者不裝進背包。對于 n 個物品來說，總的裝法就有 2^n 種，去掉總重量超過 Wkg 的，從剩下的裝法中選擇總重量最接近 Wkg 的。不過，我們如何才能不重復地窮舉出這 2^n 種裝法呢？  

回溯方法：我們可以把物品依次排列，整個問題就分解為了 n 個階段，每個階段對應一個物品怎么選擇。先對第一個物品進行處理，選擇裝進去或者不裝進去，然后再遞歸地處理剩下的物品。  

動態規劃  

動態規劃比較適合用來求解最優問題，比如求最大值、最小值等等。它可以非常顯著地降低時間復雜度，提高代碼的執行效率。  

0-1 背包問題  

對于一組不同重量、不可分割的物品，我們需要選擇一些裝入背包，在滿足背包最大重量限制的前提下，背包中物品總重量的最大值是多少呢？  

思路：  

（1）把整個求解過程分為 n 個階段，每個階段會決策一個物品是否放到背包中。每個物品決策（放入或者不放入背包）完之后，背包中的物品的重量會有多種情況，也就是說，會達到多種不同的狀態，對應到遞歸樹中，就是有很多不同的節點。  

（2）我們把每一層重復的狀態（節點）合并，只記錄不同的狀態，然后基于上一層的狀態集合，來推導下一層的狀態集合。我們可以通過合并每一層重復的狀態，這樣就保證每一層不同狀態的個數都不會超過 w 個（w 表示背包的承載重量），也就是例子中的 9。  

劃分n個階段，每一個階段基于上一個階段推導，動態地往前推進，就避免了重復計算。  

用回溯算法解決這個問題的時間復雜度 O(2^n)，是指數級的。那動態規劃解決方案的時間復雜度是多少呢？  

耗時最多的部分就是代碼中的兩層 for 循環，所以時間復雜度是 O(n*w)。n 表示物品個數，w 表示背包可以承載的總重量。我們需要額外申請一個 n 乘以 w+1 的二維數組，對空間的消耗比較多。所以，有時候，我們會說，動態規劃是一種空間換時間的解決思路。  

0-1 背包問題升級版  

對于一組不同重量、不同價值、不可分割的物品，我們選擇將某些物品裝入背包，在滿足背包最大重量限制的前提下，背包中可裝入物品的總價值最大是多少呢？  

什么樣的問題適合用動態規劃來解決呢？  

一個模型三個特征  

一個模型：多階段決策最優解模型  

三個特征：  

• 最優子結構，問題的最優解包含子問題的最優解

• 無后效性，第一層含義是，在推導后面階段的狀態的時候，我們只關心前面階段的狀態值，不關心這個狀態是怎么一步一步推導出來的。第二層含義是，某階段狀態一旦確定，就不受之后階段的決策影響。（后面的不影響前面的。）

• 重復子問題，不同的決策序列，到達某個相同的階段時，可能會產生重復的狀態。

兩種動態規劃解題思路總結  

1. 狀態轉移表法  

一般能用動態規劃解決的問題，都可以使用回溯算法的暴力搜索解決。畫出遞歸樹。從遞歸樹中，我們很容易可以看出來，是否存在重復子問題，以及重復子問題是如何產生的  

找到重復子問題之后，接下來，我們有兩種處理思路，第一種是直接用回溯加“備忘錄”的方法，來避免重復子問題。從執行效率上來講，這跟動態規劃的解決思路沒有差別。第二種是使用動態規劃的解決方法，狀態轉移表法。  

我們先畫出一個狀態表。狀態表一般都是二維的，所以你可以把它想象成二維數組。其中，每個狀態包含三個變量，行、列、數組值。我們根據決策的先后過程，從前往后，根據遞推關系，分階段填充狀態表中的每個狀態。最后，我們將這個遞推填表的過程，翻譯成代碼，就是動態規劃代碼了。  

需要很多變量來表示，那對應的狀態表可能就是高維的，比如三維、四維。那這個時候，我們就不適合用狀態轉移表法來解決了。一方面是因為高維狀態轉移表不好畫圖表示，另一方面是因為人腦確實很不擅長思考高維的東西。  

2. 狀態轉移方程法  

我們需要分析，某個問題如何通過子問題來遞歸求解，也就是所謂的最優子結構。根據最優子結構，寫出遞歸公式，也就是所謂的狀態轉移方程。有了狀態轉移方程，代碼實現就非常簡單了。一般情況下，我們有兩種代碼實現方法，一種是遞歸加“備忘錄”，另一種是迭代遞推。  

min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))  

我要強調一點，不是每個問題都同時適合這兩種解題思路。有的問題可能用第一種思路更清晰，而有的問題可能用第二種思路更清晰，所以，你要結合具體的題目來看，到底選擇用哪種解題思路。

狀態轉移表法解題思路大致可以概括為，回溯算法實現 - 定義狀態 - 畫遞歸樹 - 找重復子問題 - 畫狀態轉移表 - 根據遞推關系填表 - 將填表過程翻譯成代碼。狀態轉移方程法的大致思路可以概括為，找最優子結構 - 寫狀態轉移方程 - 將狀態轉移方程翻譯成代碼。

如何量化兩個字符串的相似度？

編輯距離指的就是，將一個字符串轉化成另一個字符串，需要的最少編輯操作次數（比如增加一個字符、刪除一個字符、替換一個字符）。編輯距離越大，說明兩個字符串的相似程度越小；相反，編輯距離就越小，說明兩個字符串的相似程度越大。對于兩個完全相同的字符串來說，編輯距離就是 0。

編輯距離有多種不同的計算方式，比較著名的有萊文斯坦距離（Levenshtein distance）和最長公共子串長度（Longest common substring length）。其中，萊文斯坦距離允許增加、刪除、替換字符這三個編輯操作，最長公共子串長度只允許增加、刪除字符這兩個編輯操作。

萊文斯坦距離和最長公共子串長度，從兩個截然相反的角度，分析字符串的相似程度。萊文斯坦距離的大小，表示兩個字符串差異的大小；而最長公共子串的大小，表示兩個字符串相似程度的大小。

兩個字符串 mitcmu 和 mtacnu 的萊文斯坦距離是 3，最長公共子串長度是 4。

如何編程計算萊文斯坦距離？

這個問題是求把一個字符串變成另一個字符串，需要的最少編輯次數。整個求解過程，涉及多個決策階段，我們需要依次考察一個字符串中的每個字符，跟另一個字符串中的字符是否匹配，匹配的話如何處理，不匹配的話又如何處理。所以，這個問題符合多階段決策最優解模型。

推薦算法

利用向量的距離，求相似成度。

搜索：如何用A*搜索算法實現游戲中的尋路功能？

那如何快速找出一條接近于最短路線的次優路線呢？

這個快速的路徑規劃算法，就是我們今天要學習的A* 算法。實際上，A* 算法是對 Dijkstra 算法的優化和改造。

通過這個頂點跟終點之間的直線距離，也就是歐幾里得距離來近似地估計這個頂點跟終點的路徑長度（注意：路徑長度跟直線距離是兩個概念）

這個距離記作 h(i)（i 表示這個頂點的編號），專業的叫法是啟發函數（heuristic function）

因為歐幾里得距離的計算公式，會涉及比較耗時的開根號計算，所以，我們一般通過另外一個更加簡單的距離計算公式，那就是曼哈頓距離（Manhattan distance）

曼哈頓距離是兩點之間橫縱坐標的距離之和。計算的過程只涉及加減法、符號位反轉，所以比歐幾里得距離更加高效。

int hManhattan(Vertex v1, Vertex v2) { // Vertex 表示頂點，后面有定義  

    return Math.abs(v1.x - v2.x) + Math.abs(v1.y - v2.y);  

}  

f(i)=g(i)+h(i)，頂點與起點之間的路徑長度 g(i)，頂點到終點的路徑長度估計值h(i). f(i) 的專業叫法是估價函數（evaluation function）。

A* 算法就是對 Dijkstra 算法的簡單改造, f(i) 最小的先出列。

它跟 Dijkstra 算法的代碼實現，主要有 3 點區別：

• 優先級隊列構建的方式不同。A* 算法是根據 f 值（也就是剛剛講到的 f(i)=g(i)+h(i)）來構建優先級隊列，而 Dijkstra 算法是根據 dist 值（也就是剛剛講到的 g(i)）來構建優先級隊列；

• A* 算法在更新頂點 dist 值的時候，會同步更新 f 值；

• 循環結束的條件也不一樣。Dijkstra 算法是在終點出隊列的時候才結束，A* 算法是一旦遍歷到終點就結束。

讀到這里，這篇“Java常用的算法有哪些”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。