博客 / 列表

sevencoding - 劍指offer-56、刪除鏈表中重複的節點

題⽬描述 在⼀個排序的鏈表中，存在重複的結點，請刪除該鏈表中重複的結點，重複的結點不保留，返回鏈表頭指針。 例如，鏈表 1-2-3-3-4-4-5 處理後為 1-2-5 示例1 輸⼊：{1,2,3,3,4,4,5} 返回值：{1,2,5} 思路及解答 hash統計 第一次遍歷統計頻率，第二次遍歷刪除重複節點 import java.util.HashMap; public class

後端

sevencoding - 回溯算法總結

概述 其實回溯算法和我們常説的 DFS 算法非常類似，本質上就是一種暴力窮舉算法。回溯算法和 DFS 算法的細微差別是：回溯算法是在遍歷「樹枝」，DFS 算法是在遍歷「節點」 抽象地説，解決一個回溯問題，實際上就是遍歷一棵決策樹的過程，樹的每個葉子節點存放着一個合法答案。你把整棵樹遍歷一遍，把葉子節點上的答案都收集起來，就能得到所有的合法答案。 站在回溯樹的一個節點上，你只需要思考 3 個問題：

後端

sevencoding - 回溯算法總結

概述 其實回溯算法和我們常説的 DFS 算法非常類似，本質上就是一種暴力窮舉算法。回溯算法和 DFS 算法的細微差別是：回溯算法是在遍歷「樹枝」，DFS 算法是在遍歷「節點」 抽象地説，解決一個回溯問題，實際上就是遍歷一棵決策樹的過程，樹的每個葉子節點存放着一個合法答案。你把整棵樹遍歷一遍，把葉子節點上的答案都收集起來，就能得到所有的合法答案。 站在回溯樹的一個節點上，你只需要思考 3 個問題：

JAVA

sevencoding - 動態規劃

什麼是動態規劃 動態規劃，英文：Dynamic Programming，簡稱DP，如果某一問題有很多重疊子問題，使用動態規劃是最有效的。 所以動態規劃中每一個狀態一定是由上一個狀態推導出來的，這一點就區分於貪心，貪心沒有狀態推導，而是從局部直接選最優的， 例如：有N件物品和一個最多能背重量為W 的揹包。第i件物品的重量是weight[i]，得到的價值是value[i] 。每件物品只能用一次，求解將

後端

sevencoding - 動態規劃

什麼是動態規劃 動態規劃，英文：Dynamic Programming，簡稱DP，如果某一問題有很多重疊子問題，使用動態規劃是最有效的。 所以動態規劃中每一個狀態一定是由上一個狀態推導出來的，這一點就區分於貪心，貪心沒有狀態推導，而是從局部直接選最優的， 例如：有N件物品和一個最多能背重量為W 的揹包。第i件物品的重量是weight[i]，得到的價值是value[i] 。每件物品只能用一次，求解將

JAVA

sevencoding - 劍指offer-55、鏈表中環的⼊⼝節點

題⽬描述 給⼀個鏈表，若其中包含環，請找出該鏈表的環的⼊⼝結點，否則，輸出null 。 例如，輸⼊{1,2},{3,4,5} 時，對應的環形鏈表如下圖所示： 可以看到環的⼊⼝結點的結點值為3，所以返回結點值為3的結點。 給定的鏈表節點的結構： public class ListNode { int val; ListNode next = null; ListNode(i

後端

sevencoding - 劍指offer-55、鏈表中環的⼊⼝節點

題⽬描述 給⼀個鏈表，若其中包含環，請找出該鏈表的環的⼊⼝結點，否則，輸出null 。 例如，輸⼊{1,2},{3,4,5} 時，對應的環形鏈表如下圖所示： 可以看到環的⼊⼝結點的結點值為3，所以返回結點值為3的結點。 給定的鏈表節點的結構： public class ListNode { int val; ListNode next = null; ListNode(i

JAVA

sevencoding - 劍指offer-54、字符流中第一個不重複的字符

題⽬描述 請實現⼀個函數⽤來找出字符流中第⼀個只出現⼀次的字符。例如，當從字符流中只讀出前兩個字符" go "時，第⼀個只出現⼀次的字符是" g "。當從該字符流中讀出前六個字符“ google "時，第⼀個只出現⼀次的字符是" l "。 返回值描述：如果當前字符流沒有存在出現⼀次的字符，返回 # 字符。 思路及解答 有序哈希表 可以直接使用哈希的數據結構來存取我們的字符，對與重複的字符可以對值進

後端

sevencoding - 劍指offer-54、字符流中第一個不重複的字符

題⽬描述 請實現⼀個函數⽤來找出字符流中第⼀個只出現⼀次的字符。例如，當從字符流中只讀出前兩個字符" go "時，第⼀個只出現⼀次的字符是" g "。當從該字符流中讀出前六個字符“ google "時，第⼀個只出現⼀次的字符是" l "。 返回值描述：如果當前字符流沒有存在出現⼀次的字符，返回 # 字符。 思路及解答 有序哈希表 可以直接使用哈希的數據結構來存取我們的字符，對與重複的字符可以對值進

JAVA

sevencoding - 劍指offer-53、表達數值的字符串

題⽬描述 請實現⼀個函數⽤來判斷字符串str是否表示數值（包括科學計數法的數字，⼩數和整數）。科學計數法的數字(按順序）可以分成以下⼏個部分: 若⼲空格 ⼀個整數或者⼩數 （可選）⼀個 ' e ' 或 ' E ' ，後⾯跟着⼀個整數(可正可負) 若⼲空格 ⼩數（按順序）可以分成以下⼏個部分： 若⼲空格 （可選）⼀個符號字符（'+' 或 '-'） 可能是以下描述格式之⼀:

後端

sevencoding - 劍指offer-53、表達數值的字符串

題⽬描述 請實現⼀個函數⽤來判斷字符串str是否表示數值（包括科學計數法的數字，⼩數和整數）。科學計數法的數字(按順序）可以分成以下⼏個部分: 若⼲空格 ⼀個整數或者⼩數 （可選）⼀個 ' e ' 或 ' E ' ，後⾯跟着⼀個整數(可正可負) 若⼲空格 ⼩數（按順序）可以分成以下⼏個部分： 若⼲空格 （可選）⼀個符號字符（'+' 或 '-'） 可能是以下描述格式之⼀:

JAVA

sevencoding - 一文講清楚圖論相關算法

建圖函數 ListInteger[] buildGraph(int numCourses, int[][] prerequisites) { // 圖中共有 numCourses 個節點 ListInteger[] graph = new LinkedList[numCourses]; for (int i = 0; i numCourses; i++) {

後端

sevencoding - 一文講清楚圖論相關算法

建圖函數 ListInteger[] buildGraph(int numCourses, int[][] prerequisites) { // 圖中共有 numCourses 個節點 ListInteger[] graph = new LinkedList[numCourses]; for (int i = 0; i numCourses; i++) {

JAVA

sevencoding - 遞歸與分治算法

遞歸算法 遞歸算法（Recursion Algorithm）是一種重要的編程方法，核心思想是函數通過調用自身來解決問題。在遞歸中，一個複雜的問題被分解為相同類型但規模更小的子問題，直到達到一個簡單到可以直接解決的基本情況（基準情況）。遞歸算法特別適合解決具有自相似結構的問題，時間複雜度跟遞歸深度和每層處理的複雜度有關。 遞歸算法的妙處在於它能用簡潔優雅的代碼解決看似複雜的問題，但在使用時一定要注意

後端

sevencoding - 遞歸與分治算法

遞歸算法 遞歸算法（Recursion Algorithm）是一種重要的編程方法，核心思想是函數通過調用自身來解決問題。在遞歸中，一個複雜的問題被分解為相同類型但規模更小的子問題，直到達到一個簡單到可以直接解決的基本情況（基準情況）。遞歸算法特別適合解決具有自相似結構的問題，時間複雜度跟遞歸深度和每層處理的複雜度有關。 遞歸算法的妙處在於它能用簡潔優雅的代碼解決看似複雜的問題，但在使用時一定要注意

JAVA

sevencoding - 劍指offer-52、正則表達式匹配

題⽬描述 請實現⼀個函數⽤來匹配包括' . '和' * '的正則表達式。模式中的字符' . '表示任意⼀個字符， ⽽' * '表示它前⾯的字符可以出現任意次（包含0 次）。 在本題中，匹配是指字符串的所有字符匹配整個模式。例如，字符串" aaa "與模式" a.a "和" ab*ac*a "匹配，但是與" aa.a "和" ab*a "均不匹 配 示例1 輸⼊: "aaa","a

後端

sevencoding - 劍指offer-52、正則表達式匹配

題⽬描述 請實現⼀個函數⽤來匹配包括' . '和' * '的正則表達式。模式中的字符' . '表示任意⼀個字符， ⽽' * '表示它前⾯的字符可以出現任意次（包含0 次）。 在本題中，匹配是指字符串的所有字符匹配整個模式。例如，字符串" aaa "與模式" a.a "和" ab*ac*a "匹配，但是與" aa.a "和" ab*a "均不匹 配 示例1 輸⼊: "aaa","a

JAVA

sevencoding - 劍指offer-51、構建乘積數組

題⽬描述 給定⼀個數組A[0,1,...,n-1] ,請構建⼀個數組B[0,1,...,n-1] ，其中B 中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1] 。不能使⽤除法。（注意：規定B[0] =A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2] ） 對於A ⻓度為1 的情況，

後端

sevencoding - 劍指offer-51、構建乘積數組

題⽬描述 給定⼀個數組A[0,1,...,n-1] ,請構建⼀個數組B[0,1,...,n-1] ，其中B 中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1] 。不能使⽤除法。（注意：規定B[0] =A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2] ） 對於A ⻓度為1 的情況，

JAVA

sevencoding - 劍指offer-50、數組中重複的數字

題目描述 在⼀個⻓度為 n 的數組⾥的所有數字都在 0 到n-1 的範圍內。 數組中某些數字是重複的，但不知 道有⼏個數字是重複的。也不知道每個數字重複⼏次。請找出數組中第⼀個重複的數字。 例如，如果輸⼊⻓度為 7 的數組 [2,3,1,0,2,5,3] ，那麼對應的輸出是第⼀個重複的數字 2 。沒有重複的數字 返回 -1 。 示例1 輸⼊ [ 2, 3, 1, 0, 2, 5,

後端

sevencoding - 劍指offer-50、數組中重複的數字

題目描述 在⼀個⻓度為 n 的數組⾥的所有數字都在 0 到n-1 的範圍內。 數組中某些數字是重複的，但不知 道有⼏個數字是重複的。也不知道每個數字重複⼏次。請找出數組中第⼀個重複的數字。 例如，如果輸⼊⻓度為 7 的數組 [2,3,1,0,2,5,3] ，那麼對應的輸出是第⼀個重複的數字 2 。沒有重複的數字 返回 -1 。 示例1 輸⼊ [ 2, 3, 1, 0, 2, 5,

JAVA

sevencoding - 字符串匹配算法

Rabin-Karp算法 Rabin-Karp算法是一種基於哈希函數的字符串匹配算法，由 Michael O. Rabin 和 Richard M. Karp 於1987年提出，核心思想是用哈希函數將模式串和文本串中的子串轉換為數值進行比較，避免大量不必要的字符比較。這個算法特別適合多模式串匹配場景，時間複雜度平均為O(n+m)，n是文本串長度，m是模式串長度。 Rabin-Karp算法的關鍵在於

後端

sevencoding - 字符串匹配算法

Rabin-Karp算法 Rabin-Karp算法是一種基於哈希函數的字符串匹配算法，由 Michael O. Rabin 和 Richard M. Karp 於1987年提出，核心思想是用哈希函數將模式串和文本串中的子串轉換為數值進行比較，避免大量不必要的字符比較。這個算法特別適合多模式串匹配場景，時間複雜度平均為O(n+m)，n是文本串長度，m是模式串長度。 Rabin-Karp算法的關鍵在於

JAVA

sevencoding - 查找算法

二分查找 二分查找（Binary Search）是一種高效的查找算法，也叫折半查找。核心思想：對於一個有序的數據集合，每次查找都將查找範圍縮小為原來的一半，直到找到目標值或確定目標值不存在。二分查找要求數據必須是有序的，經常應用於數組等支持隨機訪問的數據結構裏。跟線性查找相比，二分查找的效率要高得多，特別是對於大規模數據集。 算法步驟 確定查找範圍的左邊界 left 和右邊界 right 計

後端