廢話不多說，喊一句號子鼓勵自己：程序員永不失業(yè)，程序員走向架構！本篇Blog的主題是【】，使用【】這個基本的數據結構來實現，這個高頻題的站點是：CodeTop，篩選條件為：目標公司+最近一年+出現頻率排序，由高到低的去牛客TOP101去找，只有兩個地方都出現過才做這道題（CodeTop本身匯聚了LeetCode的來源），確保刷的題都是高頻要面試考的題。

名曲目標題后，附上題目鏈接，后期可以依據解題思路反復快速練習，題目按照題干的基本數據結構分類，且每個分類的第一篇必定是對基礎數據結構的介紹。

最長公共子串【MID】

首先來一道最長公共子串，難度還沒有升級，公共字符是連續(xù)的即可

題干

解題思路

求兩個數組或者字符串的最長公共子序列問題，肯定是要用動態(tài)規(guī)劃的。

• 首先，區(qū)分兩個概念：子序列可以是不連續(xù)的；子數組（子字符串）需要是連續(xù)的；
• 另外，單個數組或者字符串要用動態(tài)規(guī)劃時，可以把動態(tài)規(guī)劃 dp[i] 定義為 nums[0:i] 中想要求的結果；當兩個數組或者字符串要用動態(tài)規(guī)劃時，可以把動態(tài)規(guī)劃定義成兩維的 dp[i][j] ，其含義是在 A[0:i] 與 B[0:j] 之間匹配得到的想要的結果。

1. 狀態(tài)定義

對于本題而言，可以定義 dp[i][j] 表示 text1[0:i-1] 和 text2[0:j-1] 的最長公共子序列。 （注：text1[0:i-1] 表示的是 text1 的 第 0 個元素到第 i - 1 個元素，兩端都包含） 之所以 dp[i][j] 的定義不是 text1[0:i] 和 text[0:j] ，是為了方便當 i = 0 或者 j = 0 的時候，dp[i][j]表示空字符串和另外一個字符串的匹配，這樣 dp[i][j] 可以初始化為空字符串

2. 狀態(tài)轉移方程

知道狀態(tài)定義之后，開始寫狀態(tài)轉移方程。

• 當 text1[i - 1] == text2[j - 1] 時，說明兩個子字符串的最后一位相等，所以最長公共子串長度又增加了 1，所以 dp[i][j] = dp[i - 1][j - 1] + text1[i]；
• 當 text1[i - 1] != text2[j - 1] 時，說明兩個子字符串的最后一位不相等，所以不夠成公共子串，不滿足條件

綜上狀態(tài)轉移方程為：

• dp[i][j] = dp[i - 1][j - 1] + s1.charAt(i - 1), 當 text1[i?1]==text2[j?1]

當然我們還需要當前最新下標來輔助記錄子串最新的更新位置

3. 狀態(tài)的初始化

初始化就是要看當 i = 0 與 j = 0 時， dp[i][j] 應該取值為多少。

• 當 i = 0 時，dp[0][j] 表示的是 text1中取空字符串 跟 text2的最長公共子序列，結果肯定為 空字符串.
• 當 j = 0 時，dp[i][0] 表示的是 text2中取空字符串 跟 text1的最長公共子序列，結果肯定為 空字符串.

綜上，當 i = 0 或者 j = 0 時，dp[i][j] 初始化為 空字符串.

4. 遍歷方向與范圍

由于 dp[i][j] 依賴于 dp[i - 1][j - 1] ,，所以 i和 j的遍歷順序肯定是從小到大（自底向上）的。 另外，由于當 i和 j 取值為 0 的時候，dp[i][j] = 0，而 dp 數組本身初始化就是為 空字符串，所以，直接讓 i 和 j 從 1 開始遍歷。遍歷的結束應該是字符串的長度為 len(text1)和 len(text2)。

5. 最終返回結果

由于 dp[i][j] 的含義是 text1[0:i-1] 和 text2[0:j-1] 的最長公共子序列。我們最終希望求的是 text1 和 text2 的最長公共子序列。所以需要返回的結果是 i = len(text1) 并且 j = len(text2) 時的 dp[len(text1)][len(text2)]。

代碼實現

給出代碼實現基本檔案

基本數據結構：字符串
輔助數據結構：無
算法：動態(tài)規(guī)劃
技巧：無

其中數據結構、算法和技巧分別來自：

• 10 個數據結構：數組、鏈表、棧、隊列、散列表、二叉樹、堆、跳表、圖、Trie 樹
• 10 個算法：遞歸、排序、二分查找、搜索、哈希算法、貪心算法、分治算法、回溯算法、動態(tài)規(guī)劃、字符串匹配算法
• 技巧：雙指針、滑動窗口、中心擴散

當然包括但不限于以上

import java.util.*;public class Solution {/*** 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規(guī)定的值即可** longest common substring* @param str1 string字符串 the string* @param str2 string字符串 the string* @return string字符串*/public String LCS (String str1, String str2) {// 入參條件判斷if (str1 == null || str1.length() == 0 || str2 == null || str2.length() == 1) {return null;}// 1 初始化狀態(tài)int ls1 = str1.length();int ls2 = str2.length();// dp表示范圍為0-ls1的str1與0-ls2的str2的最長公共子串長度int[][] dp = new int[ls1 + 1][ls2 + 1];int max = 0;int latestIndex = 0;// 2 遍歷（自底向上）for (int i = 1; i <= ls1; i++) {for (int j = 1; j <= ls2; j++) {// 狀態(tài)轉移方程if (str1.charAt(i - 1) == str2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + 1;// 更新子串最大長度以及當前子串下標if (dp[i][j] > max) {max = dp[i][j];// 公共子串不包含latestIndex位置latestIndex = i;}}}}// 上述循環(huán)i從1開始，這里subString右側為開區(qū)間，剛好適用return str1.substring(latestIndex - max, latestIndex);}
}

復雜度分析

時間復雜度：O(n^2 )，構造輔助數組dp與b，兩層循環(huán)，遞歸是有方向的遞歸，因此只是相當于遍歷了二維數組
空間復雜度：O(n^2 )，輔助二維數組dp與遞歸棧的空間最大為O(n^2 )

最長公共子序列【MID】

難度升級，明確下什么是公共子序列。一個字符串的子序列是指這樣一個新的字符串：它是由原字符串在不改變字符的相對順序的情況下刪除某些字符（也可以不刪除任何字符）后組成的新字符串。

例如，ace是 abcde的子序列，但 aec不是 abcde 的子序列

題干

解題思路

求兩個數組或者字符串的最長公共子序列問題，肯定是要用動態(tài)規(guī)劃的。

• 首先，區(qū)分兩個概念：子序列可以是不連續(xù)的；子數組（子字符串）需要是連續(xù)的；
• 另外，單個數組或者字符串要用動態(tài)規(guī)劃時，可以把動態(tài)規(guī)劃 dp[i] 定義為 nums[0:i] 中想要求的結果；當兩個數組或者字符串要用動態(tài)規(guī)劃時，可以把動態(tài)規(guī)劃定義成兩維的 dp[i][j] ，其含義是在 A[0:i] 與 B[0:j] 之間匹配得到的想要的結果。

1. 狀態(tài)定義

對于本題而言，可以定義 dp[i][j] 表示 text1[0:i-1] 和 text2[0:j-1] 的最長公共子序列。 （注：text1[0:i-1] 表示的是 text1 的 第 0 個元素到第 i - 1 個元素，兩端都包含） 之所以 dp[i][j] 的定義不是 text1[0:i] 和 text[0:j] ，是為了方便當 i = 0 或者 j = 0 的時候，dp[i][j]表示空字符串和另外一個字符串的匹配，這樣 dp[i][j] 可以初始化為空字符串

2. 狀態(tài)轉移方程

知道狀態(tài)定義之后，開始寫狀態(tài)轉移方程。

• 當 text1[i - 1] == text2[j - 1] 時，說明兩個子字符串的最后一位相等，所以最長公共子序列又增加了 1，所以 dp[i][j] = dp[i - 1][j - 1] + text1[i]；舉個例子，比如對于 ac 和 bc 而言，他們的最長公共子序列的長度等于 a 和 b 的最長公共子序列長度 0 + text[1] = c。
• 當 text1[i - 1] != text2[j - 1] 時，說明兩個子字符串的最后一位不相等，那么此時的狀態(tài) dp[i][j] 應該是 dp[i - 1][j] 和 dp[i][j - 1] 的最大值。舉個例子，比如對于 ace 和 bc 而言，他們的最長公共子序列等于 ① ace 和 b 的最長公共子序列:空字符串的長度0 與 ② ac 和 bc 的最長公共子序列c長度1 的最大值，即 1，所以選擇長度大的

綜上狀態(tài)轉移方程為：

• dp[i][j] = dp[i - 1][j - 1] + s1.charAt(i - 1), 當 text1[i?1]==text2[j?1]
• dp[i][j] = dp[i - 1][j].length() > dp[i][j - 1].length() ? dp[i - 1][j] : dp[i][j - 1];, 當 text1[i?1]!=text2[j?1]

3. 狀態(tài)的初始化

初始化就是要看當 i = 0 與 j = 0 時， dp[i][j] 應該取值為多少。

• 當 i = 0 時，dp[0][j] 表示的是 text1中取空字符串 跟 text2的最長公共子序列，結果肯定為 空字符串.
• 當 j = 0 時，dp[i][0] 表示的是 text2中取空字符串 跟 text1的最長公共子序列，結果肯定為 空字符串.

綜上，當 i = 0 或者 j = 0 時，dp[i][j] 初始化為 空字符串.

4. 遍歷方向與范圍

由于 dp[i][j] 依賴于 dp[i - 1][j - 1] ,，所以 i和 j的遍歷順序肯定是從小到大（自底向上）的。 另外，由于當 i和 j 取值為 0 的時候，dp[i][j] = 0，而 dp 數組本身初始化就是為 空字符串，所以，直接讓 i 和 j 從 1 開始遍歷。遍歷的結束應該是字符串的長度為 len(text1)和 len(text2)。

5. 最終返回結果

由于 dp[i][j] 的含義是 text1[0:i-1] 和 text2[0:j-1] 的最長公共子序列。我們最終希望求的是 text1 和 text2 的最長公共子序列。所以需要返回的結果是 i = len(text1) 并且 j = len(text2) 時的 dp[len(text1)][len(text2)]。

代碼實現

給出代碼實現基本檔案

基本數據結構：字符串
輔助數據結構：無
算法：動態(tài)規(guī)劃
技巧：無

其中數據結構、算法和技巧分別來自：

• 10 個數據結構：數組、鏈表、棧、隊列、散列表、二叉樹、堆、跳表、圖、Trie 樹
• 10 個算法：遞歸、排序、二分查找、搜索、哈希算法、貪心算法、分治算法、回溯算法、動態(tài)規(guī)劃、字符串匹配算法
• 技巧：雙指針、滑動窗口、中心擴散

當然包括但不限于以上

import java.util.*;public class Solution {/*** 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規(guī)定的值即可** longest common subsequence* @param s1 string字符串 the string* @param s2 string字符串 the string* @return string字符串*/public String LCS (String s1, String s2) {// 0 入參校驗if (s1 == null || s1.length() == 0 || s2 == null ||s2.length() == 0) return "-1";// 1 狀態(tài)定義及初始化int ls1 = s1.length();int ls2 = s2.length();// 長度為ls1和長度為ls2的最長公共子序列是dpString[][] dp = new String[ls1 + 1][ls2 + 1];// 2 初始化狀態(tài)值，當初始化狀態(tài)時，公共子序列為空字符串for (int i = 0; i <= ls1; i++) {// j為0表示一個長度不為0的s1和一個長度永遠為0的字符串公共子序列一定是空字符串dp[i][0] = "";}for (int j = 0; j <= ls2; j++) {// i為0表示一個長度不為0的s1和一個長度永遠為0的字符串公共子序列一定是空字符串dp[0][j] = "";}// 3 自底向上遍歷for (int i = 1; i <= ls1; i++) {for (int j = 1; j <= ls2; j++) {// 4 狀態(tài)轉移方程if (s1.charAt(i - 1) == s2.charAt(j - 1)) {// 如果s1和s2的字符相等，dp[1][1]表示dp[0][0]+a=a(自底向上)dp[i][j] = dp[i - 1][j - 1] + s1.charAt(i - 1);} else {// 如果s1和s2的字符不相等，取dp[i - 1][j]和dp[i][j - 1]較長的字符作為dp[i][j]dp[i][j] = dp[i - 1][j].length() > dp[i][j - 1].length() ? dp[i - 1][j] :dp[i][j - 1];}}}// 5 返回的是兩個完整s1和s2的公共子序列return dp[ls1][ls2] == "" ? "-1" : dp[ls1][ls2];}
}

復雜度分析

時間復雜度：O(n^2 )，構造輔助數組dp與b，兩層循環(huán)，遞歸是有方向的遞歸，因此只是相當于遍歷了二維數組
空間復雜度：O(n^2 )，輔助二維數組dp與遞歸棧的空間最大為O(n^2 )

拓展知識：動態(tài)規(guī)劃

動態(tài)規(guī)劃基本概念

動態(tài)規(guī)劃（Dynamic Programming，簡稱DP）算法是一種解決復雜問題的算法設計和優(yōu)化技術，常用于解決具有重疊子問題性質和最優(yōu)子結構性質的問題。它的核心思想是將一個大問題分解成一系列相互重疊的子問題，然后將子問題的解存儲起來，以避免重復計算，從而節(jié)省時間。

動態(tài)規(guī)劃算法通常包括以下關鍵步驟：

1. 定義子問題：將原問題分解成若干個子問題，并明確定義每個子問題的輸入和輸出。

2. 構建狀態(tài)轉移方程：確定每個子問題與其他子問題之間的關系，即如何通過已解決的子問題來解決當前子問題。這通常通過遞歸或迭代方式建立狀態(tài)轉移方程。

3. 初始化：初始化基本情況，通常是問題規(guī)模較小或無法再分時的邊界情況。

4. 自底向上求解或使用備忘錄法：根據狀態(tài)轉移方程，從最小的子問題開始解決，逐步構建出更大規(guī)模的問題的解?？梢允褂米缘紫蛏系牡椒ɑ騻渫浄▉肀苊庵貜陀嬎?。

5. 返回結果：根據狀態(tài)轉移方程求解出原問題的解。

動態(tài)規(guī)劃廣泛應用于各種領域，包括算法設計、優(yōu)化問題、路徑規(guī)劃、序列比對、字符串處理、游戲策略等。經典的動態(tài)規(guī)劃問題包括斐波那契數列、背包問題、最長公共子序列、最短路徑問題。

動態(tài)規(guī)劃的優(yōu)點是可以顯著減少重復計算，提高效率，但其缺點是需要合理定義子問題和狀態(tài)轉移方程，有時需要額外的內存空間來存儲中間結果。因此，在解決問題時，需要仔細分析問題的性質，確定是否適合使用動態(tài)規(guī)劃算法。

動態(tài)規(guī)劃、遞歸、分治的區(qū)別

下面是動態(tài)規(guī)劃、遞歸和分治這三種算法的相同點和不同點的表格展示：

特點	動態(tài)規(guī)劃	遞歸	分治
求解方式	自底向上	自頂向下	分而治之
重復計算處理	避免重復計算，通過存儲子問題的解來提高效率	可能重復計算相同的子問題	分解問題并獨立處理子問題
時間復雜度	通常具有較低的時間復雜度	可能具有較高的時間復雜度	通常具有中等的時間復雜度
適用性	適用于具有重疊子問題性質和最優(yōu)子結構性質的問題	適用于結構天然呈遞歸性質的問題	適用于問題可以分解為獨立的子問題
經典問題舉例	背包問題、最短路徑問題、斐波那契數列等	樹形結構的問題、圖遍歷等	快速排序、歸并排序等
記憶化/緩存	通過存儲中間結果，具有記憶化的特點	可以使用記憶化技巧來減少重復計算	分治通常不涉及記憶化
穩(wěn)定性	具有穩(wěn)定性，不受輸入數據順序影響	可能受輸入數據順序影響	通常具有穩(wěn)定性，不受輸入數據順序影響

這個表格概括了動態(tài)規(guī)劃、遞歸和分治算法之間的一些主要相同點和不同點。需要注意的是，這些算法的選擇取決于具體問題的性質和要求，有時候也可以根據問題的特點將它們結合使用，以獲得更好的性能和效果。

高頻算法題歸類

適用于這些算法思想的題目

動態(tài)規(guī)劃處理的高頻算法題

動態(tài)規(guī)劃是一個非常強大的算法技巧，適用于解決各種高頻的算法問題。以下是一些使用動態(tài)規(guī)劃解決的常見高頻算法題目：

1. 斐波那契數列問題：計算斐波那契數列的第n個數，可以使用動態(tài)規(guī)劃來避免指數級的重復計算。

2. 背包問題：如 0-1 背包問題、完全背包問題、多重背包問題等，動態(tài)規(guī)劃可用于優(yōu)化資源分配問題。

3. 最長公共子序列問題：尋找兩個字符串的最長公共子序列，動態(tài)規(guī)劃可用于解決字符串匹配和相似性比較問題。

4. 最長遞增子序列問題：尋找一個數組中最長的遞增子序列，常用于優(yōu)化問題和排序問題。

5. 最短路徑問題：如 Dijkstra 算法、Floyd-Warshall 算法，用于在圖中找到最短路徑或最短距離。

6. 編輯距離問題：計算兩個字符串之間的最小編輯操作數，如插入、刪除和替換操作。

7. 股票買賣問題：尋找股票價格數組中的最佳買賣時機，以獲得最大的利潤。

8. 子集和問題：確定給定集合中是否存在一個子集，其元素之和等于特定目標值。

9. 矩陣鏈乘法問題：在給定一組矩陣的情況下，確定它們相乘的最佳順序以最小化乘法運算的次數。

10. 字符串匹配問題：如正則表達式匹配、通配符匹配等，用于模式匹配和文本搜索。

這些問題只是動態(tài)規(guī)劃可以解決的眾多示例之一。動態(tài)規(guī)劃的思想可以應用于各種優(yōu)化和最優(yōu)化問題，它的關鍵是將問題分解成子問題并找到適當的狀態(tài)轉移規(guī)則。因此，當你面對一個復雜的問題時，考慮是否可以使用動態(tài)規(guī)劃來提高問題求解的效率和準確性。

分治算法處理的高頻算法題

分治算法是一種重要的算法技巧，適用于解決各種高頻的算法問題，特別是分而治之的思想。以下是一些使用分治算法解決的常見高頻算法題目：

1. 歸并排序：分治算法的經典示例之一，用于將一個大數組分割成較小的子數組，排序子數組，然后將它們合并以得到有序數組。

2. 快速排序：另一種基于分治思想的排序算法，通過選擇一個基準元素，將數組劃分成兩個子數組，然后遞歸地對子數組進行排序。

3. 連續(xù)子數組的最大和：給定一個整數數組，查找具有最大和的連續(xù)子數組。分治算法可以用于高效解決這個問題。

4. 求解最近點對問題：給定一個包含多個點的平面，找到最接近的一對點。該問題可以通過分治算法以較低的時間復雜度解決。

5. 矩陣乘法：分治算法可以用于將矩陣分割成子矩陣，然后遞歸地進行矩陣乘法操作，以減少計算次數。

6. 大整數乘法：用于計算兩個大整數的乘積，分治算法可以用于將大整數分解為較小的整數，并遞歸地計算它們的乘積。

7. 眾數問題：查找數組中出現次數超過一半的元素，分治算法可以在線性時間內解決這個問題。

8. 合并K個有序鏈表：將K個有序鏈表合并為一個有序鏈表，分治算法可以用于高效解決這個問題。

9. 尋找第K大/小的元素：在一個未排序的數組中找到第K大或第K小的元素，分治算法可以用于解決這個問題。

10. 求解凸多邊形的最小包圍矩形：給定一個凸多邊形，找到包圍它的最小矩形。分治算法可用于高效計算最小包圍矩形。

這些問題只是分治算法可以解決的眾多示例之一。分治算法的關鍵思想是將問題分解為相互獨立的子問題，然后將子問題的解合并以得到原問題的解。當你面對一個需要分而治之的問題時，考慮是否可以使用分治算法來提高問題求解的效率和準確性。

遞歸算法處理的高頻算法題

遞歸算法是一種常見且強大的算法技巧，適用于解決各種高頻的算法問題。以下是一些使用遞歸算法解決的常見高頻算法題目：

1. 二叉樹遍歷：包括前序遍歷、中序遍歷、后序遍歷等，用于訪問和處理二叉樹的節(jié)點。

2. 分解問題：許多問題可以通過將它們分解為更小的相似子問題來解決，例如斐波那契數列、漢諾塔問題等。

3. 遞歸的數據結構：如鏈表、樹、圖等數據結構的處理通常使用遞歸來實現。

4. 組合和排列問題：生成所有可能的組合或排列，如子集生成、排列生成等。

5. 回溯算法：解決一些組合優(yōu)化問題，如八皇后問題、數獨問題等。

6. 圖的遍歷：深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）是遞歸的常見應用，用于解決圖相關的問題。

7. 遞歸的搜索和查找：二分查找、樹的搜索、圖的最短路徑等問題可以使用遞歸算法解決。

8. 分治算法：分治算法的核心思想就是遞歸，如歸并排序、快速排序等。

9. 遞歸背包問題：解決背包問題的變種，如動態(tài)規(guī)劃中的背包問題。

10. 字符串處理：字符串匹配、編輯距離、正則表達式匹配等問題通?？梢允褂眠f歸來解決。

這些問題只是遞歸算法可以解決的眾多示例之一。遞歸算法的關鍵思想是將問題分解為更小的相似問題，并通過遞歸調用自身來解決這些子問題。當你面對一個需要不斷分解問題的情況時，考慮是否可以使用遞歸來解決，但需要小心避免無限遞歸，確保有適當的終止條件。