码农常用10种算法
碼農常用10種算法
二分查找算法(非遞歸)
查看前面筆記：查找算法中的非遞歸二分查找
分治算法
分治算法介紹
分治法是一種很重要的算法。字面上的解釋是“分而治之”，就是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。這個技巧是很多高效算法的基礎，如排序算法(快速排序，歸并排序)，傅立葉變換(快速傅立葉變換)……
分治算法可以求解的一些經典問題
- 二分搜索
- 大整數乘法
- 棋盤覆蓋
- 合并排序
- 快速排序
- 線性時間選擇
- 最接近點對問題
- 循環賽日程表
- 漢諾塔
分治算法的基本步驟
分治法在每一層遞歸上都有三個步驟：
分治(Divide-and-Conquer§)算法設計模式如下：
說明：其中|P|表示問題P的規模；n0為一閾值，表示當問題P的規模不超過n0時，問題已容易直接解出，不必再繼續分解。ADHOC§是該分治法中的基本子算法，用于直接解小規模的問題P。因此，當P的規模不超過n0時直接用算法ADHOC§求解。算法MERGE(y1,y2,…,yk)是該分治法中的合并子算法，用于將P的子問題P1 ,P2 ,…,Pk的相應的解y1,y2,…,yk合并為P的解
分治算法最佳實踐-漢諾塔
漢諾塔的傳說
漢諾塔：漢諾塔（又稱河內塔）問題是源于印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子中從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。
漢諾塔游戲的演示和思路分析:
如果是有一個盤， A->C
如果有 n >= 2 情況，則總是可以看做是兩個盤 1.最下邊的盤 2. 上面的所有盤
- 先把 最上面的盤 A->B
- 再把最下邊的盤 A->C
- 最后把B塔的所有盤 從 B->C
代碼實現
package com.atguigu.dac;/*** @author ysxstart* @create 2022-04-24 13:18*/ public class HanoiTower {/*** 漢諾塔的移動的方法,使用分治算法** @param num 盤的個數* @param a 第一根柱子* @param b 第二根柱子* @param c 第三根柱子*/public static void hanoiTower(int num, char a, char b, char c) {//如果只有 1個盤if (num == 1) {System.out.println("第1個盤從" + a + "->" + c);} else {//如果有 num >= 2情況，則總是可以看做是兩個盤： 1.最下邊的一個盤 2. 上面的所有盤//1.先把最上面的所有盤 a->b， 移動過程會使用到 chanoiTower(num - 1, a, c, b);//2.把最下邊的盤 a->cSystem.out.println("第" + num + "個盤從" + a + "->" + c);//3.把 b塔的所有盤從 b->c , 移動過程使用到 a塔hanoiTower(num - 1, b, a, c);}}public static void main(String[] args) {hanoiTower(3, 'A', 'B', 'C');} }動態規劃算法
動態規劃算法介紹
- 動態規劃(Dynamic Programming)算法的核心思想是：將大問題劃分為小問題進行解決，從而一步步獲取最優解的處理算法
- 動態規劃算法與分治算法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。
- 與分治法不同的是，適合于用動態規劃求解的問題，經分解得到子問題往往不是互相獨立的。 ( 即下一個子階段的求解是建立在上一個子階段的解的基礎上，進行進一步的求解 )
- 動態規劃可以通過填表的方式來逐步推進，得到最優解.
動態規劃算法最佳實踐-背包問題
背包問題：有一個背包，容量為4磅 ， 現有如下物品
背包問題主要是指一個給定容量的背包、若干具有一定價值和重量的物品，如何選擇物品放入背包使物品的價值最大。其中又分01背包和完全背包(完全背包指的是：每種物品都有無限件可用)
這里的問題屬于01背包，即每個物品最多放一個。而無限背包可以轉化為01背包。
思路分析：
算法的主要思想，利用動態規劃來解決。每次遍歷到的第i個物品，根據w[i]和val[i]來確定是否需要將該物品放入背包中。即對于給定的n個物品，設val[i]、w[i]分別為第i個物品的價值和重量，C為背包的容量。再令v[i][j]表示前i個物品中能夠裝入容量為j的背包中的最大價值。則有下面的結果：
代碼實現：
package com.atguigu.dynamicprogramming;/*** @author ysxstart* @create 2022-04-24 16:43*/ public class KnapsackProblem {public static void main(String[] args) {int[] w = {1, 4, 3}; //物品的重量int[] val = {1500, 3000, 2000}; //物品的價值int m = 4; //背包的容量int n = val.length; //物品的個數//創建二維數組//v[i][j] 表示在前 i個物品中能夠裝入容量為j的背包中的最大價值int[][] v = new int[n + 1][m + 1];//為了記錄放入商品的情況，定一個二維數組int[][] path = new int[n + 1][m + 1];//初始化第一行和第一列, 這里可以不去處理，因為默認就是0for (int i = 0; i < v.length; i++) {v[i][0] = 0; //將第一列設置為0}for (int i = 0; i < v[0].length; i++) {v[0][i] = 0; //將第一行設置0}//根據前面得到公式來動態規劃處理for (int i = 1; i < v.length; i++) {for (int j = 1; j < v[0].length; j++) {//公式if (w[i - 1] > j) { //因為 i是從1開始的，因此原來公式中的 w[i]修改成 w[i-1]v[i][j] = v[i - 1][j];} else { //背包容量大于等于當前商品的容量//因為 i從1開始的，因此公式需要調整成：//v[i][j] = max{v[i-1][j], val[i] + v[i-1][j-w[i]]}//v[i][j] = Math.max(v[i-1][j], val[i-1]+v[i-1][j-w[i-1]]);//為了記錄商品存放到背包的情況，不能直接的使用上面的公式，需要使用if-else來體現公式if (v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]]) {v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];//把當前的情況記錄到pathpath[i][j] = 1;} else {v[i][j] = v[i - 1][j];}}}}//輸出一下 v看看目前的情況for (int i = 0; i < v.length; i++) {for (int j = 0; j < v[0].length; j++) {System.out.print(v[i][j] + " ");}System.out.println();}System.out.println();//輸出最后是哪些商品被放入，從后往前遍歷int i = path.length - 1; //行的最大下標int j = path[0].length - 1; //列的最大下標while (i > 0 && j > 0) { //從path的最后開始找if (path[i][j] == 1) {System.out.printf("第%d個商品放入到背包\n", i);j -= w[i - 1];}i--;}} }運行結果：
KMP算法
應用場景-字符串匹配問題
字符串匹配問題：
有一個字符串 str1= ““硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好””，和一個子串 str2=“尚硅谷你尚硅你”?，F在要判斷 str1 是否含有 str2, 如果存在，就返回第一次出現的位置, 如果沒有，則返回-1
BF暴力匹配算法
如果用暴力匹配的思路，并假設現在str1匹配到 i 位置，子串str2匹配到 j 位置，則有:
- 如果當前字符匹配成功（即str1[i] == str2[j]），則i++，j++，繼續匹配下一個字符
- 如果失配（即str1[i]! = str2[j]），令i = i - (j - 1)，j = 0。相當于每次匹配失敗時，i 回溯，j 被置為0。
- 用暴力方法解決的話就會有大量的回溯，每次只移動一位，若是不匹配，移動到下一位接著判斷，浪費了大量的時間。(不可行!)
代碼實現：
package com.atguigu.kmp;/*** @author ysxstart* @create 2022-04-24 23:03*/ public class ViolenceMatch {/*** 暴力匹配算法實現** @param str1 主串* @param str2 子串* @return 匹配到則返回索引，沒有匹配到則返回-1*/public static int violenceMatch(String str1, String str2) {char[] s1 = str1.toCharArray();char[] s2 = str2.toCharArray();int s1Len = s1.length;int s2Len = s2.length;int i = 0; // i索引指向s1int j = 0; // j索引指向s2while (i < s1Len && j < s2Len) {if (s1[i] == s2[j]) { //匹配oki++;j++;} else { //匹配 no ok!//主串回溯，重新匹配子串；i等于匹配ok的i的下一個索引;若程序剛開始就沒有匹配ok,則i每次加1繼續循環i = i - (j - 1);j = 0;}}if (j == s2Len) {return i - j;} else {return -1;}}public static void main(String[] args) {//測試暴力匹配算法String str1 = "硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好";String str2 = "尚硅谷你尚硅你";int index = violenceMatch(str1, str2);System.out.println("index = " + index);} }KMP算法最佳應用-字符串匹配問題
字符串匹配問題：：
有一個字符串 str1= “BBC ABCDAB ABCDABCDABDE”，和一個子串 str2=“ABCDABD”
現在要判斷 str1 是否含有 str2, 如果存在，就返回第一次出現的位置, 如果沒有，則返回-1
要求：使用KMP算法完成判斷，不能使用簡單的暴力匹配算法.
KMP算法思路圖解分析：
舉例來說，有一個字符串 Str1 = “BBC ABCDAB ABCDABCDABDE”，判斷，里面是否包含另一個字符串 Str2 = “ABCDABD”？
- 移動位數 = 已匹配的字符數 - 對應的部分匹配值
- 因為 6 - 2 等于4，所以將搜索詞向后移動 4 位。
- 先介紹前綴，后綴是什么
- “部分匹配值”就是”前綴”和”后綴”的最長的共有元素的長度。以”ABCDABD”為例，
- －”A”的前綴和后綴都為空集，共有元素的長度為0；
- －”AB”的前綴為[A]，后綴為[B]，共有元素的長度為0；
- －”ABC”的前綴為[A, AB]，后綴為[BC, C]，共有元素的長度0；
- －”ABCD”的前綴為[A, AB, ABC]，后綴為[BCD, CD, D]，共有元素的長度為0；
- －”ABCDA”的前綴為[A, AB, ABC, ABCD]，后綴為[BCDA, CDA, DA, A]，共有元素為”A”，長度為1；
- －”ABCDAB”的前綴為[A, AB, ABC, ABCD, ABCDA]，后綴為[BCDAB, CDAB, DAB, AB, B]，共有元素為”AB”，長度為2；
- －”ABCDABD”的前綴為[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后綴為[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的長度為0。
到此KMP算法思想分析完畢!
代碼實現：
package com.atguigu.kmp;import java.util.Arrays;/*** @author ysxstart* @create 2022-04-25 13:10*/ public class KMPAlgorithm2 {/*** kmp算法實現** @param str1 主串* @param str2 子串* @param next 子串的部分匹配值表* @return 不返回-1表示找到*/public static int kmpSearch(String str1, String str2, int[] next) {for (int i = 0, j = 0; i < str1.length(); i++) {//需要處理 str1.charAt(i) != str2.charAt(j), 去調整j的大小//KMP算法核心點while (j > 0 && str1.charAt(i) != str2.charAt(j)) {j = next[j - 1]; //獲取需移動的位數}if (str1.charAt(i) == str2.charAt(j)) {j++;}if (j == str2.length()) {return i - (j - 1); //j要減1，因 j=str2.length}}return -1;}//生成部分匹配值表,dest搜索詞private static int[] kmpNext(String dest) {//next數組保存部分匹配值；索引表示字符，數組值表示部分匹配值int[] next = new int[dest.length()];//字符串長度為1，部分匹配值就是0next[0] = 0;for (int i = 1, j = 0; i < dest.length(); i++) {//當dest.charAt(i) != dest.charAt(j) ，需要從next[j-1]獲取新的jwhile (j > 0 && dest.charAt(i) != dest.charAt(j)) {// 1.第一次進入while循環時，j=2,i=6即'C'和'D'不同，則取子串ABC的前一個子串AB的部分匹配值，即0。// 2.j = 0; i =6 和j=0相比較，即'D'和'A',首尾不同。即ABCDABD串的前綴和后綴沒有公共元素，部分匹配值為0；next[6] = 0;j = next[j - 1];}//當dest.charAt(i) == dest.charAt(j)滿足時，部分匹配值就是 +1if (dest.charAt(i) == dest.charAt(j)) {j++;}next[i] = j;}return next;}public static void main(String[] args) {String str1 = "BBC ABCDAB ABCDABCDABDE";String str2 = "ABCDABD";int[] next = kmpNext(str2);System.out.println("搜索詞 " + str2 + " 的部分匹配表：" + Arrays.toString(next));int index = kmpSearch(str1, str2, next);System.out.println("找到的子串開始索引：" + index);} }運行結果：
貪心算法
貪心算法介紹
- 貪婪算法(貪心算法)是指在對問題進行求解時，在每一步選擇中都采取最好或者最優(即最有利)的選擇，從而希望能夠導致結果是最好或者最優的算法
- 貪婪算法所得到的結果不一定是最優的結果(有時候會是最優解)，但是都是相對近似(接近)最優解的結果
貪心算法最佳應用-集合覆蓋
假設存在如下表的需要付費的廣播臺，以及廣播臺信號可以覆蓋的地區。 如何選擇最少的廣播臺，讓所有的地區都可以接收到信號!
| K1 | “北京”, “上?！? “天津” |
| K2 | “廣州”, “北京”, “深圳” |
| K3 | “成都”, “上?！? “杭州” |
| K4 | “上?！? “天津” |
| K5 | “杭州”, “大連” |
思路分析:
如何找出覆蓋所有地區的廣播臺的集合呢，使用窮舉法實現,列出每個可能的廣播臺的集合，這被稱為冪集。假設總的有n個廣播臺，則廣播臺的組合總共有2? -1 個,假設每秒可以計算10個子集， 如圖:
使用貪婪算法，效率高:
目前并沒有算法可以快速計算得到準備的值， 使用貪婪算法，則可以得到非常接近的解，并且效率高。選擇策略上，因為需要覆蓋全部地區的最小集合:
代碼實現
package com.atguigu.greedy;import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet; import java.util.List;/*** @author ysxstart* @create 2022-04-25 22:41*/ public class GreedyAlgorithm2 {public static void main(String[] args) {//創建廣播電臺,放入到MapHashMap<String, HashSet<String>> broadcasts = new HashMap<>();//創建每個電臺對應的覆蓋的地區HashSet<String> hashSet1 = new HashSet<>();hashSet1.add("北京");hashSet1.add("上海");hashSet1.add("天津");HashSet<String> hashSet2 = new HashSet<>();hashSet2.add("廣州");hashSet2.add("北京");hashSet2.add("深圳");HashSet<String> hashSet3 = new HashSet<>();hashSet3.add("成都");hashSet3.add("上海");hashSet3.add("杭州");HashSet<String> hashSet4 = new HashSet<>();hashSet4.add("上海");hashSet4.add("天津");HashSet<String> hashSet5 = new HashSet<>();hashSet5.add("杭州");hashSet5.add("大連");//加入到map,將各個電臺放入到broadcastsbroadcasts.put("K1", hashSet1);broadcasts.put("K2", hashSet2);broadcasts.put("K3", hashSet3);broadcasts.put("K4", hashSet4);broadcasts.put("K5", hashSet5);//allAreas存放所有的地區,即未覆蓋的地區HashSet<String> allAreas = new HashSet<>();for (HashSet<String> value : broadcasts.values()) {allAreas.addAll(value);}List<String> selectList = greedy(broadcasts, allAreas);System.out.println("得到的選擇結果是：" + selectList);}public static List<String> greedy(HashMap<String, HashSet<String>> broadcasts, HashSet<String> allAreas) {//存放選擇的電臺集合ArrayList<String> selects = new ArrayList<>();/*臨時集合tempSet，存放遍歷過程中該電臺覆蓋的地區 和當前還沒有覆蓋的地區(allAreas)的交集；臨時集合maxTempSet，（上一個maxKey）maxKey和allAreas集合的交集，用于后面與當前的key和allAreas的交集的數量作比較*/HashSet<String> tempSet = new HashSet<>();HashSet<String> maxTempSet = new HashSet<>();/*定義maxKey，保存在一次遍歷過程中，能夠覆蓋最大 未覆蓋的地區對應的電臺的key如果maxKey不為null,則會加入到selects*/String maxKey = null;//開始循環，如果allAreas不為0,則表示還沒有覆蓋完所有的地區while (allAreas.size() > 0) {//每進行一次while,需要重置maxKeymaxKey = null;//遍歷 broadcasts,取出對應key,得到maxKeyfor (String key : broadcasts.keySet()) {//每進行一次for重置臨時集合tempSet,maxTempSet不用重置tempSet.clear();//當前這個key能夠覆蓋的地區HashSet<String> areas = broadcasts.get(key);tempSet.addAll(areas);//求出tempSet和allAreas集合的交集,交集結果會賦給tempSettempSet.retainAll(allAreas);/*如果當前這個集合包含的未覆蓋地區的數量，比maxKey指向的集合地區還多,就需要重置maxKey體現出貪心算法的特點,每次都選擇最優的：tempSet.size() > maxTempSet.size(); maxTempSet.size()是上一個maxKey和allAreas集合的交集的數量簡單點：就是比較每一輪中每一個key中和allAreas集合的交集的數量大小，最大的即為maxKey。即被選擇加入selects集合的電臺*/if (tempSet.size() > 0 && (maxKey == null ||tempSet.size() > maxTempSet.size())) {maxKey = key;maxTempSet.addAll(broadcasts.get(maxKey));maxTempSet.retainAll(allAreas);}}//maxKey != null,就應該將maxKey加入selectsif (maxKey != null) {selects.add(maxKey);//將maxKey指向的廣播電臺覆蓋的地區，從allAreas去掉allAreas.removeAll(broadcasts.get(maxKey));}}//循環結束之后就得到了貪心算法的最優的一種解法（可能也不是最優的，看具體需求情況）return selects;} }運行結果：
貪心算法注意事項和細節
貪婪算法所得到的結果不一定是最優的結果(有時候會是最優解)，但是都是相對近似(接近)最優解的結果。
比如上題的算法選出的是K1, K2, K3, K5，符合覆蓋了全部的地區,但是我們發現 K2, K3,K4,K5 也可以覆蓋全部地區，如果K2 的使用成本低于K1,那么我們上題的 K1, K2, K3, K5 雖然是滿足條件，但是并不是最優的.
普里姆算法
應用場景-修路問題
有勝利鄉有7個村莊(A, B, C, D, E, F, G) ，現在需要修路把7個村莊連通,各個村莊的距離用邊線表示(權) ，比如 A – B 距離 5公里
問：如何修路保證各個村莊都能連通，并且總的修建公路總里程最短?
思路: 將10條邊，連接即可，但是總的里程數不是最小.
正確的思路: 就是盡可能的選擇少的路線，并且每條路線最小，保證總里程數最少
最小生成樹
修路問題本質就是就是最小生成樹問題， 先介紹一下最小生成樹(Minimum Cost Spanning Tree)，簡稱MST。
普里姆算法介紹
普利姆(Prim)算法求最小生成樹，也就是在包含n個頂點的連通圖中，找出只有(n-1)條邊包含所有n個頂點的連通子圖，也就是所謂的極小連通子圖
普利姆的算法如下:
代碼實現：
package com.atguigu.prim;import java.util.Arrays;/*** @author ysxstart* @create 2022-04-26 19:54*/ public class PrimAlgorithm {public static void main(String[] args) {//測試圖是否創建okchar[] data = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};int verxs = data.length;//鄰接矩陣的關系使用二維數組表示,10000這個大數，表示兩個點不聯通int[][] weight = new int[][]{{10000, 5, 7, 10000, 10000, 10000, 2},{5, 10000, 10000, 9, 10000, 10000, 3},{7, 10000, 10000, 10000, 8, 10000, 10000},{10000, 9, 10000, 10000, 10000, 4, 10000},{10000, 10000, 8, 10000, 10000, 5, 4},{10000, 10000, 10000, 4, 5, 10000, 6},{2, 3, 10000, 10000, 4, 6, 10000}};//創建MGraph對象MGraph graph = new MGraph(verxs);//創建一個MinTree對象MinTree minTree = new MinTree();minTree.createGraphMatrix(graph, verxs, data, weight);//輸出minTree.showGraph(graph);//測試普利姆算法int weightNum = minTree.prim(graph, 0);System.out.println("權值：" + weightNum);} }//創建最小生成樹->村莊的圖（連通網） class MinTree {/*** 創建圖的鄰接矩陣** @param graph 圖對象* @param verxs 圖對應的頂點個數* @param data 圖的各個頂點的值* @param weight 圖的鄰接矩陣*/public void createGraphMatrix(MGraph graph, int verxs, char[] data, int[][] weight) {int i, j;for (i = 0; i < verxs; i++) {graph.data[i] = data[i];for (j = 0; j < verxs; j++) {graph.weight[i][j] = weight[i][j];}}}//顯示圖的鄰接矩陣public void showGraph(MGraph graph) {for (int[] row : graph.weight) {System.out.println(Arrays.toString(row));}}/*** 編寫prim算法，得到最小生成樹** @param graph 圖* @param v 表示從圖的第幾個頂點開始生成'A'->0 'B'->1...* @return 返回權值大小*/public int prim(MGraph graph, int v) {//visited[] 標記頂點是否被訪問過,默認元素的值都是0,表示沒有訪問過int[] visited = new int[graph.verxs];//把當前這個結點標記為已訪問visited[v] = 1;//h1和h2記錄每個子圖中 邊的權值最小的兩個頂點的下標int h1 = -1;int h2 = -1;//將minWeight初始成一個大數(頂點之間不存在邊)，后面在遍歷過程中，會被替換int minWeight = 10000;//最短路徑的邊的權值的總和int weightSum = 0;//graph.verxs頂點，普利姆算法結束后，有 graph.verxs-1條邊for (int k = 1; k < graph.verxs; k++) {//這是確定每一次生成的子圖 eg:<A,G,B>中，和哪個未訪問過的結點的距離最近。//簡單點說就是：判斷頂點與頂點之間的距離大小，將距離小的加入最小生成樹for (int i = 0; i < graph.verxs; i++) { //i結點表示被訪問過的結點for (int j = 0; j < graph.verxs; j++) { //j結點表示還沒有訪問過的結點if (visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) {//替換minWeight(尋找已經訪問過的結點和未訪問過的結點間的權值最小的邊)minWeight = graph.weight[i][j];h1 = i;h2 = j;}}}//找到一條邊是最小System.out.println("邊<" + graph.data[h1] + "," + graph.data[h2] + "> 權值：" + minWeight);//將當前這個結點標記為已經訪問visited[h2] = 1;//記錄權值和weightSum += minWeight;//minWeight 重新設置為最大值10000minWeight = 10000;}return weightSum;} }//創建圖，表示連通網 class MGraph {int verxs; //表示圖的節點個數char[] data; //存放結點數據int[][] weight; //存放邊(權值)，就是鄰接矩陣public MGraph(int verxs) {this.verxs = verxs;data = new char[verxs];weight = new int[verxs][verxs];} }運行結果：
克魯斯卡爾算法
應用場景-公交站問題
某城市新增7個站點(A, B, C, D, E, F, G) ，現在需要修路把7個站點連通。各個站點的距離用邊線表示(權) ，比如 A – B 距離 12公里。問：如何修路保證各個站點都能連通，并且總的修建公路總里程最短?
克魯斯卡爾算法介紹
- 克魯斯卡爾(Kruskal)算法，是用來求加權連通圖的最小生成樹的算法。
- 基本思想：按照權值從小到大的順序選擇n-1條邊，并保證這n-1條邊不構成回路
- 具體做法：首先構造一個只含n個頂點的森林，然后依權值從小到大從連通網中選擇邊加入到森林中，并使森林中不產生回路，直至森林變成一棵樹為止
以城市公交站問題來圖解說明 克魯斯卡爾算法的原理和步驟：
在含有n個頂點的連通圖中選擇n-1條邊，構成一棵極小連通子圖，并使該連通子圖中n-1條邊上權值之和達到最小，則稱其為連通網的最小生成樹。
例如，對于如上圖G4所示的連通網可以有多棵權值總和不相同的生成樹。
克魯斯卡爾算法圖解
以上圖G4為例，來對克魯斯卡爾進行演示(假設，用數組R保存最小生成樹結果)。
第1步：將邊<E,F>加入R中。邊<E,F>的權值最小，因此將它加入到最小生成樹結果R中。
第2步：將邊<C,D>加入R中。上一步操作之后，邊<C,D>的權值最小，因此將它加入到最小生成樹結果R中。
第3步：將邊<D,E>加入R中。上一步操作之后，邊<D,E>的權值最小，因此將它加入到最小生成樹結果R中。
第4步：將邊<B,F>加入R中。上一步操作之后，邊<C,E>的權值最小，但<C,E>會和已有的邊構成回路；因此，跳過邊<C,E>。同理，跳過邊<C,F>。將邊<B,F>加入到最小生成樹結果R中。
第5步：將邊<E,G>加入R中。上一步操作之后，邊<E,G>的權值最小，因此將它加入到最小生成樹結果R中。
第6步：將邊<A,B>加入R中。上一步操作之后，邊<F,G>的權值最小，但<F,G>會和已有的邊構成回路；因此，跳過邊<F,G>。同理，跳過邊<B,C>。將邊<A,B>加入到最小生成樹結果R中。
此時，最小生成樹構造完成！它包括的邊依次是：<E,F> <C,D> <D,E> <B,F> <E,G> <A,B>。
克魯斯卡爾算法分析
根據前面介紹的克魯斯卡爾算法的基本思想和做法，能夠了解到，克魯斯卡爾算法重點需要解決的以下兩個問題：
- 問題一： 對圖的所有邊按照權值大小進行排序。
- 問題二： 將邊添加到最小生成樹中時，怎么樣判斷是否形成了回路。
- 問題一很好解決，采用排序算法進行排序即可。
- 問題二，處理方式是：記錄頂點在"最小生成樹"中的終點，頂點的終點是"在最小生成樹中與它連通的最大頂點"。然后每次需要將一條邊添加到最小生存樹時，判斷該邊的兩個頂點的終點是否重合，重合的話則會構成回路。
如何判斷是否構成回路-舉例說明(如圖)
在將<E,F> <C,D> <D,E>加入到最小生成樹R中之后，這幾條邊的頂點就都有了終點：
(01) C的終點是F。
(02) D的終點是F。
(03) E的終點是F。
(04) F的終點是F。
關于終點的說明：
代碼實現：
package com.atguigu.kruskal;import java.util.Arrays;/*** @author ysxstart* @create 2022-04-27 23:04*/ public class KruskalCase2 {private int edgeNum; //邊的數量private char[] vertxs; //頂點數組private int[][] matrix; //鄰接矩陣//INF表示兩個頂點不連通private static final int INF = Integer.MAX_VALUE;//構造器public KruskalCase2(char[] vertxs, int[][] matrix) {int vlen = vertxs.length;//初始化頂點數組和鄰接矩陣//初始化頂點,復制拷貝的方式this.vertxs = new char[vlen];for (int i = 0; i < vlen; i++) {this.vertxs[i] = vertxs[i];}//初始化邊,復制拷貝的方式this.matrix = new int[vlen][vlen];for (int i = 0; i < vlen; i++) {for (int j = 0; j < vlen; j++) {this.matrix[i][j] = matrix[i][j];}}//初始化邊的數量for (int i = 0; i < vlen; i++) {for (int j = i + 1; j < vlen; j++) {if (this.matrix[i][j] != INF) {edgeNum++;}}}}//打印鄰接矩陣private void print() {System.out.println("鄰接矩陣：");for (int i = 0; i < vertxs.length; i++) {for (int j = 0; j < vertxs.length; j++) {System.out.printf("%12d", matrix[i][j]);}System.out.println();}}//克魯斯卡爾算法所需方法:/*** 獲取圖中的邊（通過matrix鄰接矩陣來獲取），放到EData[]數組中，后面需要遍歷該數組* EData[]形式： [EData{<A, B> =12}, EData{<A, F> =16}],toString()方法** @return 返回邊的數組*/private EData2[] getEdges() {int index = 0;EData2[] edges = new EData2[edgeNum];for (int i = 0; i < vertxs.length; i++) {for (int j = i + 1; j < vertxs.length; j++) {if (matrix[i][j] != INF) {edges[index++] = new EData2(vertxs[i], vertxs[j], matrix[i][j]);}}}return edges;}/*** 對邊進行排序處理, 冒泡排序** @param edges 邊的集合*/private void sortEdges(EData2[] edges) {for (int i = 0; i < edges.length - 1; i++) {for (int j = 0; j < edges.length - 1 - i; j++) {if (edges[j].weight > edges[j + 1].weight) {EData2 temp = edges[j];edges[j] = edges[j + 1];edges[j + 1] = temp;}}}}/*** 獲取頂點的下標** @param ch 頂點的值，比如'A','B'* @return 返回 ch頂點對應的下標，如果找不到，返回-1*/private int getPosition(char ch) {for (int i = 0; i < vertxs.length; i++) {if (ch == vertxs[i]) {return i;}}return -1;}/*** 獲取下標為 i的頂點的終點()的下標, 用于后面判斷兩個頂點的終點是否相同** @param ends 數組記錄了各個頂點對應的終點,ends數組是在遍歷過程中，逐步形成(動態的)* @param i 表示頂點對應的下標* @return 返回下標為 i的這個頂點對應的終點的下標*/private int getEnds(int[] ends, int i) {while (ends[i] != 0) {i = ends[i];}return i;}//克魯斯卡爾算法實現public void kruskal() {//表示最后結果數組的索引int index = 0;//用于保存 "已有最小生成樹"中的每個頂點在最小生成樹中的{終點}int[] ends = new int[edgeNum];//創建結果數組, 保存最后的最小生成樹EData2[] rets = new EData2[edgeNum];//獲取圖中所有的邊的集合，一共有12邊EData2[] edges = getEdges();System.out.println("排序前邊的集合：" + Arrays.toString(edges));//按照邊的權值大小進行排序(從小到大)sortEdges(edges);System.out.println("排序后邊的集合：" + Arrays.toString(edges));/*遍歷edges數組，將邊添加到最小生成樹中時，判斷準備加入的邊是否形成了回路，如果沒有，就加入 rets, 否則不能加入*/for (int i = 0; i < edges.length; i++) {//獲取到第 i條邊的第一個頂點(起點)int p1 = getPosition(edges[i].start);//獲取到第 i條邊的第二個頂點int p2 = getPosition(edges[i].end);//獲取 p1這個頂點在已有最小生成樹中的終點的下標int m = getEnds(ends, p1);//獲取 p2這個頂點在已有最小生成樹中的終點的下標int n = getEnds(ends, p2);//判斷是否構成回路if (m != n) {//設置 m在"已有最小生成樹"中的終點 <E,F> [0,0,0,0,5,0,0,0,0,0,0,0]ends[m] = n;//有一條邊加入到rets數組rets[index++] = edges[i];}}//<E,F> <C,D> <D,E> <B,F> <E,G> <A,B>。//統計并打印 "最小生成樹", 輸出 retsSystem.out.println("最小生成樹為：");for (int i = 0; i < index; i++) {System.out.println(rets[i]);}}public static void main(String[] args) {char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};//克魯斯卡爾算法的鄰接矩陣int[][] matrix = {/*A*//*B*//*C*//*D*//*E*//*F*//*G*//*A*/ {0, 12, INF, INF, INF, 16, 14},/*B*/ {12, 0, 10, INF, INF, 7, INF},/*C*/ {INF, 10, 0, 3, 5, 6, INF},/*D*/ {INF, INF, 3, 0, 4, INF, INF},/*E*/ {INF, INF, 5, 4, 0, 2, 8},/*F*/ {16, 7, 6, INF, 2, 0, 9},/*G*/ {14, INF, INF, INF, 8, 9, 0}};KruskalCase2 kruskalCase2 = new KruskalCase2(vertexs, matrix);kruskalCase2.print();kruskalCase2.kruskal();} }//創建一個類 EData ，它的對象實例就表示一條邊 class EData2 {char start; //邊的一個點char end; //邊的另外一個點int weight; //邊的權值public EData2(char start, char end, int weight) {this.start = start;this.end = end;this.weight = weight;}@Overridepublic String toString() {return "EData2{<" + start + ", " + end + "> =" + weight + '}';} }運行結果：
迪杰斯特拉算法
應用場景-最短路徑問題
- 戰爭時期，勝利鄉有7個村莊(A, B, C, D, E, F, G) ，現在有六個郵差，從G點出發，需要- 分別把郵件分別送到 A, B, C , D, E, F 六個村莊
- 各個村莊的距離用邊線表示(權) ，比如 A – B 距離 5公里
- 問：如何計算出G村莊到 其它各個村莊的最短距離?
- 如果從其它點出發到各個點的最短距離又是多少?
迪杰斯特拉(Dijkstra)算法介紹
迪杰斯特拉(Dijkstra)算法是典型最短路徑算法，用于計算一個結點到其他結點的最短路徑。 它的主要特點是以起始點為中心向外層層擴展(廣度優先搜索思想)，直到擴展到終點為止。
迪杰斯特拉(Dijkstra)算法過程
設置出發頂點為v，頂點集合V{v1,v2,vi…}，v到V中各頂點的距離構成距離集合Dis，Dis{d1,d2,di…}，Dis集合記錄著v到圖中各頂點的距離(到自身可以看作0，v到vi距離對應為di)
思路圖解
代碼實現：
package com.atguigu.dijkstra;import java.util.Arrays;/*** @author Mustang* @create 2022-04-29 9:37*/ public class DijkstraAlgorithm2 {public static void main(String[] args) {char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};int[][] matrix = new int[vertex.length][vertex.length];//表示不可以連接final int N = 65535;matrix[0] = new int[]{N, 5, 7, N, N, N, 2};matrix[1] = new int[]{5, N, N, 9, N, N, 3};matrix[2] = new int[]{7, N, N, N, 8, N, N};matrix[3] = new int[]{N, 9, N, N, N, 4, N};matrix[4] = new int[]{N, N, 8, N, N, 5, 4};matrix[5] = new int[]{N, N, N, 4, 5, N, 6};matrix[6] = new int[]{2, 3, N, N, 4, 6, N};Graph2 graph2 = new Graph2(vertex, matrix);//測試圖的鄰接矩陣是否okgraph2.showGraph();//測試迪杰斯特拉算法graph2.dijkstra(6);graph2.showDijkstra();} }//圖，村莊 class Graph2 {private char[] vertex; //頂點數組private int[][] matrix; //鄰接矩陣private VisitedVertex2 vv; //已經訪問的頂點的集合//構造器public Graph2(char[] vertex, int[][] matrix) {int len = vertex.length;this.vertex = new char[len];for (int i = 0; i < len; i++) {this.vertex[i] = vertex[i];}this.matrix = new int[len][len];for (int i = 0; i < len; i++) {for (int j = 0; j < len; j++) {this.matrix[i][j] = matrix[i][j];}}}//顯示圖public void showGraph() {for (int[] row : matrix) {System.out.println(Arrays.toString(row));}}//顯示迪杰斯特拉算法結果public void showDijkstra() {vv.show();}/*** 迪杰斯特拉算法實現** @param index 出發的頂點*/public void dijkstra(int index) {vv = new VisitedVertex2(vertex.length, index);for (int i = 0; i < vertex.length; i++) {update(index); //更新index頂點到周圍頂點的距離和周圍頂點的前驅頂點index = vv.updateArr(); //更新訪問頂點}}//更新 index下標頂點到周圍頂點的距離和周圍頂點的前驅頂點.G->A,G->B;前驅：G<-B，B的前驅是Gprivate void update(int index) {int len = 0;//根據出發頂點index 遍歷鄰接矩陣的matrix[index]行for (int i = 0; i < matrix[index].length; i++) {//len含義是: 出發頂點到index頂點的距離 + 從index頂點到i頂點的距離的和.G->G + G-Alen = vv.getDis(index) + matrix[index][i];// i頂點沒有被訪問過，并且 len小于出發頂點到i頂點的距離，就需要更新if (!vv.isVisited(i) && len < vv.getDis(i)) {vv.updateDis(i, len); //更新出發頂點到 i頂點的距離vv.updatePre(i, index); //更新 i頂點的前驅為index頂點}}} }//已訪問頂點集合 class VisitedVertex2 {//記錄各個頂點是否訪問過 1表示訪問過,0未訪問,會動態更新public int[] already_arr;//每個頂點下標對應的前一個頂點下標（頂點的前驅頂點）,會動態更新public int[] pre_visited;//記錄出發頂點到其他所有頂點的距離,//比如G為出發頂點，就會記錄G到其它頂點的距離，會動態更新，求的最短距離就會存放到dispublic int[] dis;/*** 構造器** @param length 頂點的個數* @param index 出發頂點的下標, 比如G頂點，下標就是6*/public VisitedVertex2(int length, int index) {this.already_arr = new int[length];this.pre_visited = new int[length];this.dis = new int[length];//初始化 dis數組Arrays.fill(dis, 65535);//設置出發頂點被訪問過this.already_arr[index] = 1;//設置出發頂點的到它自己的距離為 0this.dis[index] = 0;}//迪杰斯特拉算法所需方法:/*** 返回出發頂點到 index頂點的距離** @param index* @return*/public int getDis(int index) {return dis[index];}/*** 判斷index頂點是否被訪問過** @param index* @return 如果訪問過, 就返回true, 否則訪問false*/public boolean isVisited(int index) {return already_arr[index] == 1;}/*** 更新出發頂點到 index頂點的距離** @param index 更新的頂點* @param len 更新的距離*/public void updateDis(int index, int len) {dis[index] = len;}/*** 更新 pre頂點的前驅頂點為 index頂點** @param pre* @param index*/public void updatePre(int pre, int index) {pre_visited[pre] = index;}/*** 繼續選擇頂點并返回新的訪問頂點，比如這里的 G完后，* 就是 A點作為新的訪問頂點(注意不是出發頂點)** @return 返回新的訪問頂點*/public int updateArr() {int min = 65535, index = 0;for (int i = 0; i < already_arr.length; i++) {//沒有訪問過且距離最小if (already_arr[i] == 0 && dis[i] < min) {min = dis[i];index = i;}}//更新 index頂點被訪問過already_arr[index] = 1;return index;}//顯示最后的結果public void show() {System.out.println("====================================================");//輸出already_arrSystem.out.print("already_arr: ");for (int i : already_arr) {System.out.print(i + " ");}System.out.println();//輸出pre_visitedSystem.out.print("pre_visited: ");for (int i : pre_visited) {System.out.print(i + " ");}System.out.println();//輸出disSystem.out.print("dis: ");for (int i : dis) {System.out.print(i + " ");}System.out.println();System.out.println("====================================================");char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};int count = 0;for (int i : dis) {if (i != 65535) {System.out.print(vertex[count] + "(" + i + ") ");} else {System.out.print("N ");}count++;}} }運行結果：
弗洛伊德算法
弗洛伊德(Floyd)算法介紹
- 和Dijkstra算法一樣，弗洛伊德(Floyd)算法也是一種用于尋找給定的加權圖中頂點間最短路徑的算法。該算法名稱以創始人之一、1978年圖靈獎獲得者、斯坦福大學計算機科學系教授羅伯特·弗洛伊德命名
- 弗洛伊德算法(Floyd)計算圖中各個頂點之間的最短路徑
- 迪杰斯特拉算法用于計算圖中某一個頂點到其他頂點的最短路徑。
- 弗洛伊德算法 VS 迪杰斯特拉算法：迪杰斯特拉算法通過選定的被訪問頂點，求出從出發訪問頂點到其他頂點的最短路徑；弗洛伊德算法中每一個頂點都是出發訪問點，所以需要將每一個頂點看做被訪問頂點，求出從每一個頂點到其他頂點的最短路徑。
弗洛伊德(Floyd)算法圖解分析
第一輪循環中，以A(下標為：0)作為中間頂點，距離表和前驅關系更新為：
分析如下：
弗洛伊德(Floyd)算法最佳應用-最短路徑
勝利鄉有7個村莊(A, B, C, D, E, F, G)，各個村莊的距離用邊線表示(權) ，比如 A – B 距離 5公里。問：如何計算出各村莊到 其它各村莊的最短距離?
代碼實現：
package com.atguigu.floyd;import java.util.Arrays;/*** @author Mustang* @create 2022-04-30 10:42*/ public class FloydAlgorithm {public static void main(String[] args) {char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};int[][] matrix = new int[vertex.length][vertex.length];final int N = 65535;matrix[0] = new int[]{0, 5, 7, N, N, N, 2};matrix[1] = new int[]{5, 0, N, 9, N, N, 3};matrix[2] = new int[]{7, N, 0, N, 8, N, N};matrix[3] = new int[]{N, 9, N, 0, N, 4, N};matrix[4] = new int[]{N, N, 8, N, 0, 5, 4};matrix[5] = new int[]{N, N, N, 4, 5, 0, 6};matrix[6] = new int[]{2, 3, N, N, 4, 6, 0};Graph graph = new Graph(vertex, matrix);graph.floyd();graph.show();} }//創建圖 class Graph {//存放頂點的數組private char[] vertex;//保存從各個頂點出發到其它頂點的距離，最后的結果也是保留在該數組private int[][] dis;//保存到達目標頂點的前驅頂點private int[][] pre;/*** 構造器** @param matrix 鄰接矩陣* @param vertex 頂點數組*/public Graph(char[] vertex, int[][] matrix) {int len = vertex.length;//初始化頂點數組和鄰接矩陣this.vertex = new char[len];for (int i = 0; i < len; i++) {this.vertex[i] = vertex[i];}this.dis = new int[len][len];for (int i = 0; i < len; i++) {for (int j = 0; j < len; j++) {this.dis[i][j] = matrix[i][j];}}//對pre數組初始化, 注意存放的是前驅頂點的下標this.pre = new int[len][len];for (int i = 0; i < len; i++) {Arrays.fill(pre[i], i);}}//顯示pre數組和dis數組public void show() {char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};for (int k = 0; k < dis.length; k++) {System.out.print("前驅關系--> ");for (int i = 0; i < dis.length; i++) {System.out.print(vertex[pre[k][i]] + " ");}System.out.println();for (int i = 0; i < dis.length; i++) {System.out.print("(" + vertex[k] + "到" + vertex[i] + "的最短路徑是" + dis[k][i] + ") ");}System.out.println();}}//弗洛伊德算法實現，3層for循環public void floyd() {int len = 0; //保存距離//對中間頂點遍歷，k就是中間頂點的下標 [A, B, C, D, E, F, G]for (int k = 0; k < dis.length; k++) {//從i頂點開始出發 [A, B, C, D, E, F, G]for (int i = 0; i < dis.length; i++) {//到達j頂點 [A, B, C, D, E, F, G]for (int j = 0; j < dis.length; j++) {//求出從 i頂點出發，經過 k中間頂點，到達 j頂點距離len = dis[i][k] + dis[k][j];//如果len小于 dis[i][j]if (len < dis[i][j]){dis[i][j] = len; //更新距離pre[i][j] = pre[k][j]; //更新前驅頂點}}}}} }運行結果：
馬踏棋盤算法
馬踏棋盤算法介紹和游戲演示
馬踏棋盤算法也被稱為騎士周游問題
將馬隨機放在國際象棋的8×8棋盤Board[0～7][0～7]的某個方格中，馬按走棋規則(馬走日字)進行移動。要求每個方格只進入一次，走遍棋盤上全部64個方格
馬踏棋盤游戲代碼實現
- 馬踏棋盤問題(騎士周游問題)實際上是圖的深度優先搜索(DFS)的應用。
- 如果使用回溯（就是深度優先搜索）來解決，假如馬兒踏了53個點，如圖：走到了第53個，坐標（1,0），發現已經走到盡頭，沒辦法，那就只能回退了，查看其他的路徑，就在棋盤上不停的回溯……
- 分析第一種方式的問題，并使用貪心算法（greedyalgorithm）進行優化。解決馬踏棋盤問題.
思路圖解：
代碼實現：
package com.atguigu.horse;import java.awt.*; import java.util.ArrayList; import java.util.Comparator;/*** @author Mustang* @create 2022-05-04 13:50*/ public class HorseChessboard2 {private static int X; //棋盤的列數private static int Y; //棋盤的行數//標記棋盤的各個位置是否被訪問過private static boolean[] visited;//標記棋盤的所有位置是否都被訪問,如果為true,表示成功private static boolean finished;public static void main(String[] args) {System.out.println("馬踏棋盤算法 Begining~");X = 8;Y = 8;int row = 1;int column = 1;int[][] chessboard = new int[X][Y];visited = new boolean[X * Y];//測試耗時long start = System.currentTimeMillis();traversalChessboard(chessboard, row - 1, column - 1, 1);long end = System.currentTimeMillis();System.out.println("共耗時：" + (end - start) + "毫秒");//輸出棋盤的最后情況for (int[] rows : chessboard) {for (int step : rows) {System.out.print(step + "\t");}System.out.println();}}/*** 完成騎士周游問題算法** @param chessboard 棋盤* @param row 馬兒當前的位置的行 從0開始* @param column 馬兒當前的位置的列 從0開始* @param step 是第幾步 ,初始位置就是第1步*/public static void traversalChessboard(int[][] chessboard, int row, int column, int step) {chessboard[row][column] = step;//標記該位置已經訪問visited[row * X + column] = true;//獲取當前位置可以走的下一個位置的集合ArrayList<Point> ps = next(new Point(column, row));//對ps進行排序,排序的規則就是對ps的所有的Point對象的下一步的位置的數目，進行非遞減排序sort(ps);while (!ps.isEmpty()) {//取出下一個可以走的位置Point p = ps.remove(0);//判斷該點是否已經訪問過if (!visited[p.y * X + p.x]) { //說明還沒有訪問過traversalChessboard(chessboard, p.y, p.x, step + 1);}}//判斷馬兒是否完成了任務，使用 step和應該走的步數比較。如果沒有達到數量，則表示沒有完成任務，將整個棋盤置 0//說明: step < X * Y 成立的情況有兩種：1.馬兒到達目標位置,仍然沒有走完 2.棋盤處于一個回溯過程if (step < X * Y && !finished) {//當前這步沒有走過，用于回溯之后再走chessboard[row][column] = 0;visited[row * X + column] = false;} else {finished = true;}}/*** 根據當前位置(Point對象)，計算馬兒還能走哪些位置(Point)，* 并放入到一個集合中(ArrayList), 最多有8個位置** @param curPoint 當前位置* @return 返回位置集合*/public static ArrayList<Point> next(Point curPoint) {//位置集合ArrayList<Point> ps = new ArrayList<>();//創建一個Point位置Point p1 = new Point();if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {ps.add(new Point(p1));}//判斷馬兒可以走6這個位置if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {ps.add(new Point(p1));}//判斷馬兒可以走7這個位置if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {ps.add(new Point(p1));}//判斷馬兒可以走0這個位置if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {ps.add(new Point(p1));}//判斷馬兒可以走1這個位置if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {ps.add(new Point(p1));}//判斷馬兒可以走2這個位置if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {ps.add(new Point(p1));}//判斷馬兒可以走3這個位置if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {ps.add(new Point(p1));}//判斷馬兒可以走4這個位置if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {ps.add(new Point(p1));}return ps;}//根據當前這一步的所有的下一步的選擇位置，進行非遞減排序, 減少回溯的次數public static void sort(ArrayList<Point> ps) {ps.sort(new Comparator<Point>() {@Overridepublic int compare(Point o1, Point o2) {int count1 = next(o1).size();int count2 = next(o2).size();if (count1 < count2) {return -1;} else if (count1 == count2) {return 0;} else {return 1;}}});} }運行結果：
沒有使用貪心算法時運行時間：
總結
- 上一篇： STS安装lombok插件
- 下一篇： IE6下实现Width:auto