sevencoding -
劍指offer-70、把數字翻譯成為字符串
題⽬描述
有⼀種將字⺟編碼成數字的⽅式：'a'-1, 'b-2', ... , 'z-26'。
現在給⼀串數字，返回有多少種可能的譯碼結果
示例1
輸⼊："12"
返回值：2
説明：2種可能的譯碼結果（”ab” 或”l”）
示例2
輸⼊："31717126241541717"
返回值：192
説明：192種可能的譯碼結果
仔細觀察，就會發現上⾯的編碼從 1 到
後端
sevencoding -
劍指offer-69、數字序列中某⼀位的數字
題⽬描述
數字以 0123456789101112131415... 的格式作為⼀個字符序列，在這個序列中第 2 位（從下標 0 開始計算）是 2 ，第 10 位是 1 ，第 13 位是 1 ，以此類題，請你輸出第 n 位對應的數字。
示例1
輸⼊：0
返回值：0
示例2
輸⼊：2
返回值：2
示例3
輸⼊：13
返回值：1
思路及解答
暴力法
通過逐步構造數字序列來
後端
sevencoding -
劍指offer-68、調整數組順序使奇數位於偶數前⾯(⼆)
題⽬描述
輸⼊⼀個⻓度為 n 整數數組，數組⾥⾯可能含有相同的元素，實現⼀個函數來調整該數組中數字的順序，使得所有的奇數位於數組的前⾯部分，所有的偶數位於數組的後⾯部分，對奇數和奇數，偶數和偶數之間的相對位置不做要求，但是時間複雜度和空間複雜度必須如下要求。
數據範圍：0 ≤ n ≤ 50000，數組中每個數的值 0 ≤ val ≤ 10000
要求：時間複雜度 O(n)，空間複雜度 O(1)
示
後端
sevencoding -
CopyOnWriteArrayList：寫時複製機制與高效併發訪問
前言
Vector無論是add方法還是get方法都加上了synchronized修飾，當多線程讀寫List必須排隊執行，很顯然這樣效率比較是低下的，CopyOnWriteArrayList是讀寫分離的，好處是提高線程訪問效率。
CopyOnWrite容器即寫時複製的容器。通俗的理解是當往一個容器添加元素的時候，不直接往當前容器添加，而是先將當前容器裏的值Copy到新的容器，然後再往新的容器裏添加元
後端
sevencoding -
Queue & Stack：實現機制與使用場景深度分析
為什麼不推薦使用Stack
Java已不推薦使用Stack，而是推薦使用更高效的ArrayDeque
為什麼不推薦使用
性能低：是因為 Stack 繼承自 Vector， 而 Vector 在每個方法中都加了鎖。由於需要兼容老的項目，很難在原有的基礎上進行優化，因此 Vector 就被淘汰掉了，使用 ArrayList 和 CopyOnWriteArrayList 來代替，如果在非線程安
後端
sevencoding -
劍指offer-67、剪繩⼦
題目描述
給你⼀根⻓度為n 的繩⼦，請把繩⼦剪成整數⻓的m 段（ m 、n 都是整數， n1 並 且m1 ， m=n ），每段繩⼦的⻓度記為k[1],...,k[m]。請問k[1]x...xk[m] 可能的最⼤乘積是多少？例如，當繩⼦的⻓度是8 時，我們把它剪成⻓度分別為2 、3 、3 的三段，此時得到的最⼤乘積是18`。
輸⼊描述:輸⼊⼀個數n，意義⻅題⾯。（2 = n = 60）
返回值描述:
後端
sevencoding -
劍指offer-66、機器⼈的運動範圍
題目描述
地上有⼀個 m ⾏和 n 列的⽅格。⼀個機器⼈從座標（0,0） 的格⼦開始移動，每⼀次只能向左，右，上，下四個⽅向移動⼀格，但是不能進⼊⾏座標和列座標的數位之和⼤於 k 的格⼦。 例如，當k 為 18 時，機器⼈能夠進⼊⽅格（35,37） ，因為 3+5+3+7 = 18 。但是，它不能進⼊⽅格（35,38） ，因為 3+5+3+8 = 19 。請問該機器⼈能夠達到多少個格⼦？
示例1
後端
sevencoding -
劍指offer-65、矩陣中的路徑
題目描述
請設計⼀個函數，⽤來判斷在⼀個矩陣中是否存在⼀條包含某字符串所有字符的路徑。路徑可以從矩陣中的任意⼀個格⼦開始，每⼀步可以在矩陣中向左，向右，向上，向下移動⼀個格⼦。如果⼀條路徑經過了矩陣中的某⼀個格⼦，則該路徑不能再進⼊該格⼦。 例如矩陣：
中包含⼀條字符串 " bcced " 的路徑，但是矩陣中不包含 " abcb " 路徑，因為字符串的第⼀個字符 b佔據了矩陣中的第⼀⾏第⼆個格⼦
後端
sevencoding -
InheritableThreadLocal，從入門到放棄
InheritableThreadLocal相比ThreadLocal多一個能力：在創建子線程Thread時，子線程Thread會自動繼承父線程的InheritableThreadLocal信息到子線程中，進而實現在在子線程獲取父線程的InheritableThreadLocal值的目的。
關於ThreadLocal詳細內容，可以看這篇文章：史上最全ThreadLocal 詳解
和 ThreadL
後端
sevencoding -
PriorityQueue的秘密：堆結構的高效應用與實現原理
介紹
優先級隊列的作用是能保證每次取出的元素都是隊列中權值最小(或最大)的。這裏元素大小的評判可以通過元素本身的自然順序(natural ordering)，也可以通過構造時傳入的比較器(Comparator)。
Java中PriorityQueue實現了Queue接口，不允許放入null元素；其通過堆實現，具體説是通過完全二叉樹(complete binary tree)實現的小頂堆(任意一個非
後端
sevencoding -
劍指offer-62、⼆叉搜索樹的第k個結點
題⽬描述
給定⼀棵⼆叉搜索樹，請找出其中的第 k ⼩的 TreeNode 結點。
示例1
輸⼊：{5,3,7,2,4,6,8},3
返回值：{4}
思路及解答
二叉搜索樹的關鍵性質
二叉搜索樹具有一個重要特性：中序遍歷（左-根-右）BST會得到一個升序排列的節點值序列。因此，尋找第k小的節點本質上就是獲取中序遍歷序列中的第k個元素。理解這一點是掌握所有解法的基石。
遞歸中序遍歷（直觀版
後端
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
