博客 / 列表

sevencoding - LockSupport深度解析：線程阻塞與喚醒的底層實現原理

LockSupport簡介 LockSupprot 用來阻塞和喚醒線程，底層實現依賴於Unsafe 類。 LockSupport用來創建鎖和其他同步類的基本線程阻塞原語。簡而言之，當調用LockSupport.park時，表示當前線程將會等待，直至獲得許可，當調用LockSupport.unpark時，必須把等待獲得許可的線程作為參數進行傳遞，好讓此線程繼續運行。在AQS中大量使用，AQS最終都是

後端

sevencoding - 劍指offer-76、刪除鏈表的節點

題⽬描述 給定單向鏈表的頭指針和⼀個要刪除的節點的值，定義⼀個函數刪除該節點。返回刪除後的鏈表的頭節點。 此題對⽐原題有改動 題⽬保證鏈表中節點的值互不相同 該題只會輸出返回的鏈表和結果做對⽐，所以若使⽤ C 或 C++ 語⾔，你不需要 free 或 delete 被刪除的節點 數據範圍: 0=鏈表節點值=10000 0=鏈表⻓度=10000 示例1 輸⼊：{2,5,1,9},5

後端

sevencoding - 劍指offer-75、買賣股票的最好時機

題⽬描述 假設你有⼀個數組 prices ，⻓度為 n ，其中 prices[i] 是股票在第 i 天的價格，請根據這個價格數組，返回買賣股票能獲得的最⼤收益 你可以買⼊⼀次股票和賣出⼀次股票，並⾮每天都可以買⼊或賣出⼀次，總共只能買⼊和賣出⼀次，且買⼊必須在賣出的前⾯的某⼀天 如果不能獲取到任何利潤，請返回 0 假設買⼊賣出均⽆⼿續費 示例1： 輸⼊：[8,9,2,5,4,7,1

後端

sevencoding - 劍指offer-74、n個骰⼦的點數

題目描述 把 n 個骰⼦扔在地上，所有骰⼦朝上⼀⾯的點數之和為 s 。輸⼊ n ，打印出 s 的所有可能的值出現的概率。 你需要⽤⼀個浮點數數組返回答案，其中第 i 個元素代表這 n 個骰⼦所能擲出的點數集合中第 i ⼩的那個的概率。 示例1： 輸⼊: 1 輸出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667] 示例2 輸⼊: 2 輸

後端

sevencoding - AQS深度探索：以ReentrantLock看Java併發編程的高效實現

概述 AQS ( Abstract Queued Synchronizer ）是一個抽象的隊列同步器，通過維護一個共享資源狀態（ Volatile Int State ）來表示同步狀態 和一個先進先出（ FIFO ）的線程等待隊列來完成資源獲取的排隊工作，通過CAS完成對State值的修改。 AQS整體框架如下： 當有自定義同步器接入時，只需重寫第一層所需要的部分方法即可，不需要關注底層具體的

後端

sevencoding - 劍指offer-73、連續⼦數組的最⼤和(⼆)

題⽬描述 輸⼊⼀個⻓度為n 的整型數組array ，數組中的⼀個或連續多個整數組成⼀個⼦數組，找到⼀個具有 最⼤和的連續⼦數組。 ⼦數組是連續的，⽐如[1,3,5,7,9] 的⼦數組有[1,3] ， [3,5,7] 等等，但是[1,3,7] 不是⼦數組 如果存在多個最⼤和的連續⼦數組，那麼返回其中⻓度最⻓的，該題數據保證這個最⻓的只存在⼀個 該題定義的⼦數組的最⼩⻓度為1 ，不存在為

後端

sevencoding - 劍指offer-72、禮物的最⼤價值

題⽬描述 在⼀個m × n的棋盤的每⼀格都放有⼀個禮物，每個禮物都有⼀定的價值（價值⼤於 0）。你可以從棋盤的左上⻆開始拿格⼦⾥的禮物，並每次向右或者向下移動⼀格、直到到達棋盤的右下⻆。給定⼀個棋盤及其上⾯的禮物的價值，請計算你最多能拿到多少價值的禮物？ 如輸⼊這樣的⼀個⼆維數組， [ [1,3,1], [1,5,1], [4,2,1] ] 那麼路徑 1→3→5→2→1 可以拿到最多價值的禮物，

後端

sevencoding - 劍指offer-71、剪繩子（進階版）

題⽬描述 給你⼀根⻓度為 n 的繩⼦，請把繩⼦剪成整數⻓的 m 段（ m 、 n 都是整數， n 1 並且 m 1 ， m = n ），每段繩⼦的⻓度記為 k[1] ,..., k[m] 。請問 k[1] * k[2] * ... * k[m] 可能的最⼤乘積是多少？例如，當繩⼦的⻓度是 8 時，我們把它剪成⻓度分別為 2 、3 、3 的三段，此時得到的最⼤乘積是 18 。 由於答案過⼤

後端

sevencoding - 線程如何停止？線程之間如何協作？線程之間的異常如何處理？

線程停止 stop方法 stop 方法雖然可以停止線程，但它已經是不建議使用的廢棄方法了，這一點可以通過 Thread 類中的源碼發現，stop 源碼如下： stop 方法是被 @Deprecated 修飾的不建議使用的過期方法，並且在註釋的第一句話就説明了 stop 方法為非安全的方法。 原因在於它在終止一個線程時會強制中斷線程的執行，不管run方法是否執行完了，並且還會釋放這個線程所持有的所

後端

sevencoding - BlockingQueue：阻塞操作與條件隊列的高效結合

BlockingQueue和BlockingDeque BlockingQueue BlockingQueue 通常用於一個線程生產對象，而另外一個線程消費這些對象的場景。下圖是對這個原理的闡述: 一個線程往裏邊放，另外一個線程從裏邊取的一個 BlockingQueue。 一個線程將會持續生產新對象並將其插入到隊列之中，直到隊列達到它所能容納的臨界點。也就是説，它是有限的。如果該阻塞隊列到達了其

後端

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 ： “接口”位於“調用方”所在的“包”中 概念上更依賴調用方。

後端