代碼一道，源遠流長，短短幾句代碼中，往往蘊含著完美的邏輯和精妙的算法！這正是我們程序員追求的東西。我們程序員就應該外修語言，內修算法，數據為根基，算天算地算自己~
二分查找法是查找算法里面，經典又比較簡單的一種。它適用于從有序的數列中進行查找(比如數字和字母等)，將數列排序后再查找。
二分查找法的運行時間為對數時間O(㏒?n)，即查找到需要的目標位置最多只需要㏒?n 步。假設從[0, 99]的隊列(100 個數，即 n=100)中尋到目標數 30，則需要查找步數為㏒?100 , 即最多需要查找 7 次( 26 < 100 < 27)。
因為比較簡單，話不多說直接擼代碼
現有一組有序集合：[1, 3, 8, 10, 11, 67, 100]。要求寫出通過二分法（非遞歸）查找 67 的完整代碼
Java代碼實現：
/** * @description: * @date: 2021/11/22 22:13 */ public class AlgorithmUtils { public static void main(String[] args) { int[] array = new int[]{1, 3, 8, 10, 11, 67, 100}; int target = 67; System.out.println(AlgorithmUtils.binarySearch(array, target)); // 5 } /** * 非遞歸二分法查找 * @param array 待查找的數組(升序) * @param target 目標值 * @return 目標值下標，找不到則返回-1 */ public static int binarySearch(int[] array, int target) { int left = 0; int right = array.length - 1; while (left <= right) { int middle = (left + right) / 2; if (target == array[middle]) { return middle; } else if (target > array[middle]) { left = middle + 1; } else { right = middle - 1; } } return -1; } }
JavaScript代碼實現：
let array = new Array(1, 3, 8, 10, 11, 67, 100); let target = 67; console.log(binarySearch(array, target)); function binarySearch(array, target) { if (Array.isArray(array)) { let left = 0; let right = array.length - 1; while (left <= right) { let middle = (left + right) / 2; if (target === array[middle]) { return middle; } else if (target > array[middle]) { left = middle + 1; } else { right = middle - 1; } } return -1; } else { return -1; } }
Python代碼實現：
def binary_search(list, target): left = 0 right = len(list) - 1 while left <= right: middle = int((left + right) / 2) if target == list[middle]: return middle elif target > list[middle]: left = middle + 1 else: right = middle - 1 return -1 if __name__ == '__main__': number_list = [1, 3, 8, 10, 11, 67, 100] target = 67 print(binary_search(number_list, target))
分治法（Divide-and-Conquer）是一種很重要的算法。字面上的解釋是'分而治之'，就是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。
這個技巧是很多高效算法的基礎，如排序算法(快速排序，歸并排序)，傅立葉變換(快速傅立葉變換)…
分治算法的基本實現步驟（分治法在每一層遞歸上都有三個步驟）：
分治算法經典問題：漢諾塔問題
漢諾塔的傳說
??漢諾塔：漢諾塔（又稱河內塔）問題是源于印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著 64 片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。
??假如每秒鐘一次，共需多長時間呢？移完這些金片需要 5845.54 億年以上，太陽系的預期壽命據說也就是數百億年。真的過了 5845.54 億年，地球上的一切生命，連同梵塔、廟宇等，都早已經灰飛煙滅。
OK先來在線體驗下傳說中的漢諾塔游戲：http://www.7k7k.com/swf/201271.htm
體驗完后，我們來整理下移動盤子的思路（假設有A、B、C柱子）：
1、如果只有一個盤，直接可以A->C
2、如果盤子的數量 n >= 2，我就可以看做是兩個盤子。。
因此就可以走三部曲
/** * 漢諾塔問題解決 * @param discNum 盤子數量 * @param a A柱子 * @param b B柱子 * @param c C柱子 */ public static void towerOfHanoi(int discNum, char a, char b, char c) { // 如果只有一個盤 if (discNum == 1) { System.out.println('第1個盤' + a + '->' + c); } else { // 盤的數量 >= 2 // 1.上盤A->B towerOfHanoi(discNum - 1, a, c, b); // 2.下盤A->C System.out.println('第' + discNum + '個盤' + a + '->' + c); // 3.把B柱子的所有盤子移至C柱子 towerOfHanoi(discNum - 1, b, a, c); } }
JavaScript代碼實現：
function towerOfHanoi(discNum, a, b , c) { if (discNum === 1) { console.log('第1個盤' + a + '->' + c); } else { towerOfHanoi(discNum - 1, a, c, b); console.log('第' + discNum + '個盤' + a + '->' + c); towerOfHanoi(discNum - 1, b, a ,c); } } towerOfHanoi(3, 'A', 'B', 'C');
Python代碼實現：
def tower_of_hanoi(disc_num, a, b, c): if disc_num == 1: print('第1個盤' + a + '->' + c) else: # 上盤 A->B tower_of_hanoi(disc_num - 1, a, c, b) # 下盤 A->C print('第' + str(disc_num) + '個盤' + a + '->' + c) # B柱子所有盤 B->C tower_of_hanoi(disc_num - 1, b, a, c) if __name__ == '__main__': tower_of_hanoi(3, 'A', 'B', 'C')
背包問題：現有一個背包，容量為4磅。現有如下物品：
| 物品 | 重量 | 價格 |
|---|---|---|
| 吉他(G) | 1 | 1500 |
| 音響(S) | 4 | 3000 |
| 電腦(D) | 3 | 2000 |
1、要求達到的目標為裝入的背包的總價值最大，并且重量不超出
2、要求裝入的物品不能重復
1、動態規劃(Dynamic Programming)算法（簡稱DP算法）的核心思想是：將大問題劃分為小問題進行解決，從而一步步獲取最優解的處理算法
2、動態規劃算法與分治算法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解
3、與分治法不同的是，適合于用動態規劃求解的問題，經分解得到子問題往往不是互相獨立的。 ( 即下一個子階段的求解是建立在上一個子階段的解的基礎上，進行進一步的求解 )
4、動態規劃可以通過填表的方式來逐步推進，得到最優解
1、背包問題主要是指一個給定容量的背包、若干具有一定價值和重量的物品，如何選擇物品放入背包使物品的價值最大。其中又分 01 背包和完全背包(完全背包指的是：每種物品都有無限件可用)
2、這里的問題屬于 01 背包，即每個物品最多放一個。而無限背包可以轉化為 01 背包。
3、算法的主要思想：利用動態規劃來解決。每次遍歷到的第 i 個物品，根據w[i] 和 v[i] 來確定是否需要將該物品放入背包中。即對于給定的 n 個物品，設 v[i]、w[i]分別為第 i 個物品的價值和重量，C 為背包的容量。再令 v[i][j]表示在前 i 個物品中能夠裝入容量為 j 的背包中的最大價值。
基于以上設定我們得出：
/* (1) v[i][0]=v[0][j]=0; //表示 填入表 第一行和第一列是 0 (2) 當 w[i]> j時：v[i][j]=v[i-1][j] // 當準備加入新增的商品的容量大于 當前背包的容量時，就直接使用上一個單元格的裝入策略 (3) 當 j>=w[i]時： v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]} // 當準備加入的新增的商品的容量小于等于當前背包的容量,裝入的方式: 1. v[i-1][j]： 就是上一個單元格的裝入的最大值 2. v[i]: 表示當前商品的價值 3. v[i-1][j-w[i]]： 裝入 i-1 商品，到剩余空間 j-w[i]的最大值 4. 當 j>=w[i]時： v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]} */
圖解：
Java代碼實現：
public static void main(String[] args) { int[] wight = new int[]{1, 4, 3}; // 物品的重量 int[] price = new int[]{1500, 3000, 2000}; // 物品的價格 int m = 4; // 背包的容量 int n = price.length; // 物品的個數 // 創建一個二維數組 // v[i][j] 表示在前i個物品中能夠裝入容量為j的背包中的最大價值 int[][] v = new int[n + 1][m + 1]; // 初始化第一行和第一列，這里在本程序中，可以不去處理，因為默認就是0 for (int i = 0; i < v.length; i++) { v[i][0] = 0; // 將第一列設置為0 } for (int i = 0; i < v.length; i++) { v[0][i] = 0; // 將第一行設置為0 } // 為了記錄放入商品的情況，我們定一個二維數組 int[][] path = new int[n + 1][m + 1]; // 動態規劃處理背包問題 // i和j初始都等于1，目的是不處理第一行第一列 for (int i = 1; i < v.length; i++) { for (int j = 1; j < v[i].length; j++) { // 公式 if (wight[i - 1] > j) { // 因為我們程序i是從1開始的，因此原理公式中的w[i]修改成[i-1] v[i][j] = v[i - 1][j]; } else { // 因為 i 是從1開始的，因此公式需要做出調整，如下所示 // v[i][j] = Math.max(v[i - 1][j], price[i - 1] + v[i - 1][j - wight[i - 1]]); if (v[i - 1][j] < price[i - 1] + v[i - 1][j - wight[i - 1]]) { v[i][j] = price[i - 1] + v[i - 1][j - wight[i - 1]]; // 把當前的情況記錄到path path[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[i].length; j++) { System.out.print(v[i][j] + ' '); } System.out.println(); } // 輸出放入的商品情況 int i = path.length - 1; // 行的最大下標 int j = path[0].length - 1; // 列的最大下標 while (i > 0 && j > 0) { if (path[i][j] == 1) { System.out.printf('第%d個商品放入到背包\n', i); j -= wight[i - 1]; } i--; } }
KMP是Knuth、Morris和Pratt首字母的縮寫，KMP也是由這三位學者發明（1977年聯合發表論文）。
KMP主要應用在字符串的匹配，是一個解決模式串在文本串是否出現過，如果出現過，得出最早出現的位置的經典算法。其主要思想是：當出現字符串不匹配時，可以知道之前已經匹配的文本內容，可以利用這些信息避免從頭再去匹配，從而提高匹配效率。
因此如何記錄已經匹配的文本內容，才是KMP的重點~這也使得next數組派上了用場。
KMP算法就利用之前判斷過信息，通過一個 next 數組，保存模式串中前后最長公共子序列的長度，每次回溯時，通過 next 數組找到前面匹配過的位置，省去了大量的計算時間。
現給出一段字符串str1：'硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好'，和一段子字符串str2：'尚硅谷你'。
要求寫出判斷str1是否含有str2的代碼，如果存在就返回第一次出現的位置，如果沒有則返回-1。
說到字符串匹配，我們第一時間想到的是直接遍歷字符串，看看是否存在。這種方法稱為暴力匹配，拋開效率不說，這種方式是最直接，最簡單的方式。
然而暴力匹配也是一種算法，一種解決方案，針對上述問題，我們可以得出暴力匹配算法的思路（假設現在 str1 匹配到 i 位置，子串 str2 匹配到 j 位置）：
Java代碼實現：
/** * 暴力匹配算法 * @param str1 * @param str2 * @return 返回str2首次出現在str1的位置，匹配不到則返回-1 */ public static int violenceMatch(String str1, String str2) { char[] s1 = str1.toCharArray(); char[] s2 = str2.toCharArray(); int i = 0; // 指向s1 int j = 0; // 指向s2 while (i < s1.length && j < s2.length) { if (s1[i] == s2[j]) { i++; j++; } else { // 只要有一個沒有匹配上 i = i - (j - 1); j = 0; } } // 判斷是否匹配成功 if (j == s2.length) { return i - j; } return -1; }
在main方法中測試暴力匹配：
public class AlgorithmUtils { public static void main(String[] args) { String str1 = '硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好'; String str2 = '尚硅谷你'; int index = AlgorithmUtils.violenceMatch(str1, str2); if (index != -1) { System.out.printf('第一次出現的位置是%d', index); } } }
Python代碼實現：
def violence_match(str1, str2): s1 = list(str1) s2 = list(str2) i, j = 0, 0 while i < len(s1) and j < len(s2): if s1[i] == s2[j]: i += 1 j += 1 else: i = i - (j - 1) j = 0 if j == len(s2): return i - j return -1 if __name__ == '__main__': str1 = '硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好' str2 = '尚硅谷你' print(violence_match(str1, str2)) # 4
JavaScript代碼實現：
function violenceMatch(str1, str2) { let s1 = Array.from(str1); let s2 = Array.from(str2); let i = 0; let j = 0; while (i < s1.length && j < s2.length) { if (s1[i] === s2[j]) { i++; j++; } else { i = i - (j - 1); j = 0; } } if (j === s2.length) { return i - j; } return -1; } function main() { let str1 = '硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好'; let str2 = '尚硅谷你'; console.log(violenceMatch(str1, str2)); } main();
前面呢我們已經使用暴力匹配算法，完成了上述問題的求解！也知道了暴力匹配存在效率問題，那么KMP算法又是怎樣實現呢？
為方便闡述，這里我們換個案例：現有兩組字符串
str1 = 'BBC ABCDAB ABCDABCDABDE';
str2 = 'ABCDABD';
要求使用 KMP算法 完成判斷，str1 是否含有 str2，如果存在，就返回第一次出現的位置，如果沒有，則返回-1。
備注：不能使用簡單的暴力匹配算法！！！
思路與圖解（視頻講解地址）：https://www.bilibili.com/video/BV1E4411H73v?p=161
