點(diǎn)擊上方藍(lán)色字體，選擇“標(biāo)星公眾號”

優(yōu)質(zhì)文章，第一時間送達(dá)

? 作者?|? 未夏

來源 |? urlify.cn/MV3qeq

66套java從入門到精通實(shí)戰(zhàn)課程分享

正文

一、二分查找算法(非遞歸)? ? ? ?

1，遞歸版二分查找算法

https://www.cnblogs.com/bbgs-xc/p/14111312.html

2，非遞歸二分查找算法介紹

　　源碼：二分查找(非遞歸)

• 二分查找法只適用于從有序的數(shù)列中進(jìn)行查找(比如數(shù)字和字母等)，將數(shù)列排序后再進(jìn)行查找

• 二分查找法的運(yùn)行時間為對數(shù)時間?O(㏒?n)?，即查找到需要的目標(biāo)位置最多只需要㏒?n步

3，代碼實(shí)現(xiàn)

public?static?int?search(int[]?arr,?int?val)?{
????int?left?=?0;
????int?right?=?arr.length?-?1;
????while?(left?<=?right)?{
????????int?mid?=?(left?+?right)?/?2;
????????if?(arr[mid]?==?val)?{
????????????return?mid;
????????}?else?if?(arr[mid]?>?val)?{
????????????right?=?mid?-?1;
????????}?else?{
????????????left?=?mid?+?1;
????????}
????}
????return?-1;
}

二、分治算法

1，分治算法介紹

　　分治法是一種很重要的算法。字面上的解釋是“分而治之”，就是把一個復(fù)雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。

　　分治算法求解的經(jīng)典問題：二分搜索、大整數(shù)乘法、歸并排序、快排、漢諾塔等

2，分治算法基本步驟

　　分治法在每一層遞歸上都有三個步驟：

• 分解：將原問題分解為若干個規(guī)模較小，相互獨(dú)立，與原問題形式相同的子問題

• 解決：若子問題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個子問題

• 合并：將各個子問題的解合并為原問題的解。

3，漢諾塔

a)介紹

　　如下圖所示，從左到右有A、B、C三根柱子，其中A柱子上面有從小疊到大的n個圓盤，現(xiàn)要求將A柱子上的圓盤移到C柱子上去，期間只有一個原則：一次只能移到一個盤子且大盤子不能在小盤子上面，求移動的步驟和移動的次數(shù)

? ? ? ? ??

b)思路

• 如果只有一個盤時，A -> C

• 如果有n(大于1)個盤時

• 把n-1個盤? A ->?B?(借助C)

• 把第n個盤?A ->?C

• 把n-1個盤?B ->?C?(借助A)

c)代碼實(shí)現(xiàn)

/**
?*?移動盤子
?*?@param?num??一共有多少個盤子
?*?@param?a????開始的柱子
?*?@param?b????輔助的柱子
?*?@param?c????目標(biāo)柱子
?*/
public?static?void?hanoitower(int?num,?char?a,?char?b,?char?c)?{

????if?(num?==?1)?{
????????System.out.println("第1個盤為:?"?+?a?+?"?->?"?+?c);
????}?else?{
????????hanoitower(num?-?1,?a,?c,?b);
????????System.out.println("第"?+?num?+?"個盤為:?"?+?a?+?"?->?"?+?c);
????????hanoitower(num?-?1,?b,?a,?c);
????}
}

三、動態(tài)規(guī)劃

　　源碼：背包問題

1，介紹

　　小灰版動態(tài)規(guī)劃詳解

• 動態(tài)規(guī)劃(Dynamic Programming)算法的核心思想是：將大問題劃分為小問題進(jìn)行解決，從而一步步獲取最優(yōu)解的處理算法?

• 動態(tài)規(guī)劃算法與分治算法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。

• 與分治法不同的是，適合于用動態(tài)規(guī)劃求解的問題，經(jīng)分解得到子問題往往不是互相獨(dú)立的。( 即下一個子階段的求解是建立在上一個子階段的解的基礎(chǔ)上，進(jìn)行進(jìn)一步的求解 )

• 動態(tài)規(guī)劃可以通過填表的方式來逐步推進(jìn)，得到最優(yōu)解

2，背包問題

　　背包問題主要是指一個給定容量的背包、若干具有一定價值和重量的物品，如何選擇物品放入背包使物品的價值最大。其中又分?01 背包和完全背包(完全背包指的是：每種物品都有無限件可用)

3，案例

　　背包問題：有一個背包，容量為 4 磅 ， 現(xiàn)有如下物品

? ??

• 要求達(dá)到的目標(biāo)為裝入的背包的總價值最大，并且重量不超出

• 要求裝入的物品不能重復(fù)

4，案例分析與求解

　　代碼實(shí)現(xiàn)

/**
?*?求解01背包問題
?*
?*?@param?v?商品的價值
?*?@param?w?商品的重量(體積)
?*?@param?c?商品的最大容量
?*/
public?static?void?knapsackDim(int[]?v,?int[]?w,?int?c)?{
????//初始化二維數(shù)組，行表示商品的體積w?列表示容量從0->c
????int?size?=?w.length;
????int[][]?dp?=?new?int[size?+?1][c?+?1];
????for?(int?i?=?1;?i?<=?size;?i++)?{
????????for?(int?j?=?0;?j?<=?c;?j++)?{
????????????//當(dāng)前商品的體積?大于?容量j?時?直接取上一行的數(shù)據(jù)
????????????dp[i][j]?=?dp[i?-?1][j];
????????????if?(w[i-1]?<=?j)?{
????????????????//①dp[i?-?1][j?-?w[i?-?1]]為上一行的當(dāng)前可用體積-當(dāng)前商品體積??得到減去當(dāng)前商品重量之后的最大價值?+?v[i-1]
????????????????//②dp[i][j]實(shí)則為上一行的數(shù)據(jù)??與①直接比較大小
????????????????dp[i][j]?=?Math.max(dp[i][j],?v[i?-?1]?+?dp[i?-?1][j?-?w[i?-?1]]);
????????????}
????????}
????}
}

　　優(yōu)化為一維數(shù)組

/**
?*?背包問題優(yōu)化??使用一維數(shù)組
?*
?*?@param?v?商品的價值
?*?@param?w?商品的重量(體積)
?*?@param?c?商品的最大容量
?*/
public?static?void?knapsackSingle(int[]?v,?int[]?w,?int?c)?{
????int[]?dp?=?new?int[c?+?1];
????//第一次初始化dp
????for?(int?i?=?0;?i?????????dp[i]?=?w[0]?>?i????0?:?v[0];
????}

????for?(int?i?=?1;?i?????????//防止前面數(shù)據(jù)被覆蓋，從后往前進(jìn)行遍歷
????????for?(int?j?=?c;?j?>=0;?j--)?{
????????????if?(w[i]?<=?j)?{
????????????????dp[j]?=?Math.max(dp[j],?v[i]?+?dp[j?-?w[i]]);
????????????}
????????}
????}
}

四、KMP算法

1，暴力匹配算法

　　源碼：暴力匹配

https://gitee.com/xiaocheng0902/structures-and-algorithm/blob/master/src/main/java/com/xcc/dataStructures/demo14_algapplication/Demo04_ViolenceMatch.java

a)思路

如果用暴力匹配的思路，并假設(shè)現(xiàn)在 str1 匹配到 i 位置，子串 str2 匹配到 j 位置，則有:
1) 如果當(dāng)前字符匹配成功（即 str1[i] == str2[j]），則 i++，j++，繼續(xù)匹配下一個字符 
2) 如果失配（即 str1[i]! = str2[j]），令 i = i - (j - 1)，j = 0。相當(dāng)于每次匹配失敗時，i 回溯，j 被置為 0。
3) 用暴力方法解決的話就會有大量的回溯，每次只移動一位，若是不匹配，移動到下一位接著判斷，浪費(fèi)了大量 的時間。

b)代碼實(shí)現(xiàn)

/**
?*?暴力匹配
?*?@param?str1??原始字符串
?*?@param?str2??匹配字符串
?*/
public?static?int?violenceMatch(String?str1,String?str2)?{
????//表示字符串str2的匹配的索引位置
????int?j;
????for?(int?i?=?0;?i?????????j?=?0;
????????while?(i?????????????i++;
????????????j++;
????????}
????????//將j匹配到最后一個字符
????????if?(j==str2.length())?{
????????????return?i-j;
????????}
????????i?=?i?-?j?+?1;
????}
????return?-1;
}

2，KMP算法

　　源碼：KMP算法

https://gitee.com/xiaocheng0902/structures-and-algorithm/blob/master/src/main/java/com/xcc/dataStructures/demo14_algapplication/Demo04_KMP.java

a)思路

• 尋找最長前綴后綴“ABCDABD”

? ? ? ? ?

• ?獲取next數(shù)組

? ? ? ? ?

• 
  

• 將next 數(shù)組相當(dāng)于“最大長度值”?整體向右移動一位，然后初始值賦為-1

• 若p[k] == p[j]，則next[j + 1 ] = next [j] + 1 = k + 1；

• 若p[k ] ≠ p[j]，如果此時p[ next[k]?] == p[j ]，則next[ j + 1 ] = ?next[k]?+ 1，否則繼續(xù)遞歸前綴索引k = next[k]，而后重復(fù)此過程。

• 解釋為：?如下圖所示，假定給定模式串ABCDABCE，且已知next [j] = k（相當(dāng)于“p0 pk-1” = “pj-k pj-1” = AB，可以看出k為2），現(xiàn)要求next [j + 1]等于多少？因為pk = pj = C，所以next[j + 1] = next[j] + 1 = k + 1（可以看出next[j + 1] = 3）。代表字符E前的模式串中，有長度k+1 的相同前綴后綴。

• 

• 但如果pk != pj?呢？說明“p0 pk-1 pk” ?≠ “pj-k pj-1 pj”。換言之，當(dāng)pk != pj后，字符E前有多大長度的相同前綴后綴呢？很明顯，因為C不同于D，所以ABC 跟 ABD不相同，即字符E前的模式串沒有長度為k+1的相同前綴后綴，也就不能再簡單的令：next[j + 1] = next[j] + 1 。所以，咱們只能去尋找長度更短一點(diǎn)的相同前綴后綴。

• 

• /**
  ?*?求出一個字符數(shù)組的next數(shù)組
  ?*
  ?*?@param?p?字符數(shù)組
  ?*?@return?next數(shù)組
  ?*/
  public?static?int[]?getNextArray(char[]?p)?{
  ????int[]?next?=?new?int[p.length];
  ????next[0]?=?-1;
  ????int?k?=?-1;
  ????int?j?=?0;
  ????while?(j?????????//p[k]表示前綴?p[j]表示后綴
  ????????if?(k?==?-1?||?p[j]?==?p[k])?{
  //????????????????k++;
  //????????????????j++;
  ????????????next[++j]?=?++k;
  ????????}?else?{
  ????????????k?=?next[k];
  ????????}
  ????}
  ????return?next;
  }
  

• 

• 基于next數(shù)組開始進(jìn)行匹配

• P[0]跟S[0]匹配失敗。所以執(zhí)行“如果j != -1，且當(dāng)前字符匹配失?。碨[i] != P[j]），則令 i 不變，j = next[j]”，所以j = -1，故轉(zhuǎn)而執(zhí)行“如果j = -1，或者當(dāng)前字符匹配成功（即S[i] == P[j]），都令i++，j++”，得到i = 1，j = 0，即P[0]繼續(xù)跟S[1]匹配。

• P[0]跟S[1]又失配，j再次等于-1，i、j繼續(xù)自增，從而P[0]跟S[2]匹配。

• 直到P[0]跟S[4]匹配成功，開始執(zhí)行此條指令的后半段：“如果j = -1，或者當(dāng)前字符匹配成功（即S[i] == P[j]），都令i++，j++”。

• 

• P[1]跟S[5]匹配成功，P[2]跟S[6]也匹配成功, ...，直到當(dāng)匹配到P[6]處的字符D時失配（即S[10] != P[6]），由于P[6]處的D對應(yīng)的next 值為2，所以下一步用P[2]處的字符C繼續(xù)跟S[10]匹配，相當(dāng)于向右移動：j - next[j] = 6 - 2 =4 位。

• 

• 向右移動4位后，P[2]處的C再次失配，由于C對應(yīng)的next值為0，所以下一步用P[0]處的字符繼續(xù)跟S[10]匹配，相當(dāng)于向右移動：j - next[j] = 2 - 0 = 2 位。

• 

• ?移動兩位之后，A 跟空格不匹配，模式串后移1 位。

• 

• P[6]處的D再次失配，因為P[6]對應(yīng)的next值為2，故下一步用P[2]字符C繼續(xù)跟文本串匹配，相當(dāng)于模式串向右移動 j - next[j] = 6 - 2 = 4 位。

• 

• 匹配成功，過程結(jié)束。

• 

• 匹配過程一模一樣。也從側(cè)面佐證了，next 數(shù)組確實(shí)是只要將各個最大前綴后綴的公共元素的長度值右移一位，且把初值賦為-1 即可。

• /**
  ?*?對主串s和模式串t進(jìn)行KMP模式匹配
  ?*
  ?*?@param?s?主串
  ?*?@param?t?模式串
  ?*?@return?若匹配成功，返回t在s中的位置（第一個相同字符對應(yīng)的位置），若匹配失敗，返回-1
  ?*/
  public?static?int?kmpMatch(String?s,?String?t)?{
  ????char[]?s_arr?=?s.toCharArray();
  ????char[]?t_arr?=?t.toCharArray();
  ????int[]?next?=?getNextArray(t_arr);
  ????int?i?=?0,?j?=?0;
  ????while?(i?????????if?(j?==?-1?||?s_arr[i]?==?t_arr[j])?{
  ????????????i++;
  ????????????j++;
  ????????}?else
  ????????????j?=?next[j];
  ????}
  ????if?(j?==?t_arr.length)
  ????????return?i?-?j;
  ????else
  ????????return?-1;
  }

五、貪心算法

1，應(yīng)用場景

　　假設(shè)存在下面需要付費(fèi)的廣播臺，以及廣播臺信號可以覆蓋的地區(qū)。如何選擇最少的廣播臺，讓所有的地區(qū)都可以接收到信號。

2，貪心算法介紹

• 貪婪算法(貪心算法)是指在對問題進(jìn)行求解時，在每一步選擇中都采取最好或者最優(yōu)(即最有利)的選擇，從而希望能夠?qū)е陆Y(jié)果是最好或者最優(yōu)的算法

• 貪婪算法所得到的結(jié)果不一定是最優(yōu)的結(jié)果(有時候會是最優(yōu)解)，但是都是相對近似(接近)最優(yōu)解的結(jié)果

3，問題求解

a）思路分析

• 使用窮舉法實(shí)現(xiàn),列出每個可能的廣播臺的集合，這被稱為冪集。假設(shè)總的有 n 個廣播臺，則廣播臺的組合總共有2? -1

• 使用貪婪算法，效率高

• 遍歷所有的廣播電臺，找到一個覆蓋了最多未覆蓋的地區(qū)的電臺(采用retainAll方法，將當(dāng)前集合與選擇集合的交集賦值給當(dāng)前集合)

• 將這個電臺加入到集合中，去除該電臺覆蓋的地區(qū)

• 重復(fù)以上，直至覆蓋所有的地區(qū)

b）代碼實(shí)現(xiàn)

public?static?void?main(String[]?args)?{
????Map>?map?=?new?HashMap<>();
????Set?set1?=?new?HashSet<>();
????set1.add("北京");
????set1.add("上海");
????set1.add("天津");

????Set?set2?=?new?HashSet<>();
????set2.add("廣州");
????set2.add("北京");
????set2.add("深圳");

????Set?set3?=?new?HashSet<>();
????set3.add("成都");
????set3.add("上海");
????set3.add("杭州");

????Set?set4?=?new?HashSet<>();
????set4.add("上海");
????set4.add("天津");

????Set?set5?=?new?HashSet<>();
????set5.add("杭州");
????set5.add("大連");

????map.put("K1",?set1);
????map.put("K2",?set2);
????map.put("K3",?set3);
????map.put("K4",?set4);
????map.put("K5",?set5);

????Set?allAreas?=?new?HashSet<>();
????allAreas.addAll(set1);
????allAreas.addAll(set2);
????allAreas.addAll(set3);
????allAreas.addAll(set4);
????allAreas.addAll(set5);

????//存儲選擇的key
????List?selects?=?new?ArrayList<>();

????//定義此時最大的key
????String?maxKey;
????//臨時存儲的set集合
????Set?tempSet?=?new?HashSet<>();
????//如果allArea不為空則一直刪除
????while?(allAreas.size()?!=?0)?{
????????//清空臨時set
????????tempSet.clear();
//????????????maxSize?=?0;
????????maxKey?=?null;
????????for?(Map.Entry>?entry?:?map.entrySet())?{
????????????tempSet?=?entry.getValue();
????????????tempSet.retainAll(allAreas);
????????????if?(tempSet.size()?>?0?&&?(maxKey?==?null?||?tempSet.size()?>?map.get(maxKey).size()))?{
????????????????maxKey?=?entry.getKey();
????????????}
????????}
????????if?(maxKey?!=?null)?{
????????????tempSet?=?map.get(maxKey);
????????????selects.add(maxKey);
????????????allAreas.removeAll(tempSet);
????????????//此時可以將對應(yīng)的key去除，這樣能在遍歷map的時候提高效率
????????????map.remove(maxKey);
????????}
????}

????System.out.println(selects);
}

粉絲福利：Java從入門到入土學(xué)習(xí)路線圖

??????

??長按上方微信二維碼?2 秒

感謝點(diǎn)贊支持下哈?