博客 / 列表

sevencoding - 劍指offer-64、滑動窗⼝的最⼤值

題⽬描述 給定⼀個數組和滑動窗⼝的⼤⼩，找出所有滑動窗⼝⾥數值的最⼤值。例如，如果輸⼊數組 {2,3,4,2,6,2,5,1} 及滑動窗⼝的⼤⼩ 3 ，那麼⼀共存在 6 個滑動窗⼝，他們的最⼤值分別為 {4,4,6,6,6,5} ； 針對數組 {2,3,4,2,6,2,5,1} 的滑動窗⼝有以下6個： {[2,3,4],2,6,2,5,1} ， {2,[3,4,2],6,2,5,1} ， {2,3

後端

sevencoding - 劍指offer-63、數據流中的中位數

題⽬描述 如何得到⼀個數據流中的中位數？如果從數據流中讀出奇數個數值，那麼中位數就是所有數值排序之後位於中間的數值。如果從數據流中讀出偶數個數值，那麼中位數就是所有數值排序之後中間兩個數的平均值。我們使⽤ Insert() ⽅法讀取數據流，使⽤ GetMedian() ⽅法獲取當前讀取數據的中位數。 思路及解答 排序列表法 維護一個列表，每次獲取中位數前進行排序 import java.util.

後端

sevencoding - SPI機制：服務擴展的核心技術

為什麼需要SPI機制 SPI和API的區別是什麼 SPI是一種跟API相對應的反向設計思想：API由實現方確定標準規範和功能，調用方無權做任何干預； 而SPI是由調用方確定標準規範，也就是接口，然後調用方依賴此接口，第三方實現此接口，這樣做就可以方便的進行擴展，類似於插件機制，這是SPI出現的需求背景。 SPI ： “接口”位於“調用方”所在的“包”中 概念上更依賴調用方。

後端

sevencoding - 數據結構-圖

概述 圖是一種較為複雜的非線性結構。 為啥説其較為複雜呢？ 根據前面的內容，我們知道： 線性數據結構的元素滿足唯一的線性關係，每個元素(除第一個和最後一個外)只有一個直接前趨和一個直接後繼。 樹形數據結構的元素之間有着明顯的層次關係。 但是，圖形結構的元素之間的關係是任意的。 何為圖呢？ 簡單來説，圖就是由頂點的有窮非空集合和頂點之間的邊組成的集合。通常表示為：G(V,E)，其中，G 表示

後端

sevencoding - 劍指offer-61、序列化二叉樹

題⽬描述 請實現兩個函數，分別⽤來序列化和反序列化⼆叉樹 ⼆叉樹的序列化是指：把⼀棵⼆叉樹按照某種遍歷⽅式的結果以某種格式保存為字符串，從⽽使得內存中建⽴起來的⼆叉樹可以持久保存。序列化可以基於先序、中序、後序、層序的⼆叉樹遍歷⽅式來進⾏修改，序列化的結果是⼀個字符串，序列化時通過 某種符號表示空節點（ # ），以 ！ 表示⼀個結點值的結束（ value! ）。 ⼆叉樹的反序列化是指：根據某種遍歷

後端

sevencoding - 劍指offer-60、將⼆叉樹打印成多⾏

題⽬描述 從上到下按層打印⼆叉樹，同⼀層結點從左⾄右輸出。每⼀層輸出⼀⾏。 給定的⼆叉樹是 {1,2,3,#,#,4,5} : 該⼆叉樹多⾏打印層序遍歷的結果是： [ [1], [2,3], [4,5] ] 示例1 輸⼊：{8,6,10,5,7,9,11} 返回值：[[8],[6,10],[5,7,9,11]] 思路及解答 59題的縮減版 迭代法BFS（廣度優先搜索） public

後端

sevencoding - 劍指offer-60、將⼆叉樹打印成多⾏

題⽬描述 從上到下按層打印⼆叉樹，同⼀層結點從左⾄右輸出。每⼀層輸出⼀⾏。 給定的⼆叉樹是 {1,2,3,#,#,4,5} : 該⼆叉樹多⾏打印層序遍歷的結果是： [ [1], [2,3], [4,5] ] 示例1 輸⼊：{8,6,10,5,7,9,11} 返回值：[[8],[6,10],[5,7,9,11]] 思路及解答 59題的縮減版 迭代法BFS（廣度優先搜索） public

JAVA

sevencoding - 劍指offer-59、按之字形順序打印⼆叉樹

題⽬描述 請實現⼀個函數按照之字形打印⼆叉樹，即第⼀⾏按照從左到右的順序打印，第⼆層按照從右⾄左的順序打印，第三⾏按照從左到右的順序打印，其他⾏以此類推。 示例1 輸⼊：{8,6,10,5,7,9,11} 返回值：[[8],[10,6],[5,7,9,11]] 思路及解答 雙向鏈表（推薦） 藉助雙向鏈表，初始化⼀個添加⽅向 boolean 值，先將根節點添加進去： 獲取 list

JAVA , 後端

sevencoding - 劍指offer-59、按之字形順序打印⼆叉樹

題⽬描述 請實現⼀個函數按照之字形打印⼆叉樹，即第⼀⾏按照從左到右的順序打印，第⼆層按照從右⾄左的順序打印，第三⾏按照從左到右的順序打印，其他⾏以此類推。 示例1 輸⼊：{8,6,10,5,7,9,11} 返回值：[[8],[10,6],[5,7,9,11]] 思路及解答 雙向鏈表（推薦） 藉助雙向鏈表，初始化⼀個添加⽅向 boolean 值，先將根節點添加進去： 獲取 list

JAVA

sevencoding - 數據結構-堆

什麼是堆 堆是一種滿足以下條件的樹： 堆中的每一個節點值都大於等於（或小於等於）子樹中所有節點的值。或者説，任意一個節點的值都大於等於（或小於等於）所有子節點的值。 大家可以把堆(最大堆)理解為一個公司，這個公司很公平，誰能力強誰就當老大，不存在弱的人當老大，老大手底下的人一定不會比他強。這樣有助於理解後續堆的操作。 !!!特別提示： 很多博客説堆是完全二叉樹，其實並非如此，堆不一定是完

後端

sevencoding - 數據結構-堆

什麼是堆 堆是一種滿足以下條件的樹： 堆中的每一個節點值都大於等於（或小於等於）子樹中所有節點的值。或者説，任意一個節點的值都大於等於（或小於等於）所有子節點的值。 大家可以把堆(最大堆)理解為一個公司，這個公司很公平，誰能力強誰就當老大，不存在弱的人當老大，老大手底下的人一定不會比他強。這樣有助於理解後續堆的操作。 !!!特別提示： 很多博客説堆是完全二叉樹，其實並非如此，堆不一定是完全二叉

JAVA

sevencoding - 劍指offer-58、對稱二叉樹

題⽬描述 請實現⼀個函數，⽤來判斷⼀棵⼆叉樹是不是對稱的。注意，如果⼀個⼆叉樹同此⼆叉樹的鏡像是同樣 的，定義其為對稱的。 例如：下⾯這棵⼆叉樹是對稱的 下⾯這個就不是對稱的： 示例1 輸⼊：{8,6,6,5,7,7,5} 返回值：true 示例2： 輸⼊：{8,6,9,5,7,7,5} 返回值：false 思路及解答 遞歸 遞歸，先判斷根節點是否為空，不為空則判斷左右⼦樹是

後端

sevencoding - 劍指offer-58、對稱二叉樹

題⽬描述 請實現⼀個函數，⽤來判斷⼀棵⼆叉樹是不是對稱的。注意，如果⼀個⼆叉樹同此⼆叉樹的鏡像是同樣 的，定義其為對稱的。 例如：下⾯這棵⼆叉樹是對稱的 下⾯這個就不是對稱的： 示例1 輸⼊：{8,6,6,5,7,7,5} 返回值：true 示例2： 輸⼊：{8,6,9,5,7,7,5} 返回值：false 思路及解答 遞歸 遞歸，先判斷根節點是否為空，不為空則判斷左右⼦樹是

JAVA

sevencoding - 劍指offer-57、二叉樹的下一個節點

題⽬描述 給定⼀個⼆叉樹和其中的⼀個結點，請找出中序遍歷順序的下⼀個結點並且返回。注意，樹中的結點不僅包含左右⼦結點，同時包含指向⽗結點的指針。 複雜的節點結構如下： public class TreeLinkNode { int val; TreeLinkNode left = null; TreeLinkNode right = null; TreeLinkNode next = nu

後端

sevencoding - 劍指offer-57、二叉樹的下一個節點

題⽬描述 給定⼀個⼆叉樹和其中的⼀個結點，請找出中序遍歷順序的下⼀個結點並且返回。注意，樹中的結點不僅包含左右⼦結點，同時包含指向⽗結點的指針。 複雜的節點結構如下： public class TreeLinkNode { int val; TreeLinkNode left = null; TreeLinkNode right = null; TreeLinkNo

JAVA

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 - 劍指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

JAVA

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 "。 返回值描述：如果當前字符流沒有存在出現⼀次的字符，返回 # 字符。 思路及解答 有序哈希表 可以直接使用哈希的數據結構來存取我們的字符，對與重複的字符可以對值進

後端