寫個(gè)冒泡排序就可以通過面試筆試的時(shí)代早已經(jīng)過去，技術(shù)崗對于算法的掌握要求越來越高填具。最近三周參加了算法挑戰(zhàn)，題目算是一邊copy一邊囫圇吞棗地給做完了。這就導(dǎo)致當(dāng)再一次遇到類似的題目甚至是原題時(shí)肪凛，也難以在短時(shí)間內(nèi)解決掉，只有總結(jié)歸納才能得到更好地提升辽社。

Day 1 雙指針技巧：原地修改數(shù)組

對于數(shù)組來說伟墙，在尾部插入、刪除元素的時(shí)間復(fù)雜度為O(1)滴铅，但是在數(shù)組的前部進(jìn)行操作（例如頭部或者中間）戳葵，就會(huì)涉及到操作位置后部的元素的搬遷問題，時(shí)間復(fù)雜度為O(N)汉匙。

如何將復(fù)雜度給降下來拱烁，對數(shù)組進(jìn)行原地修改，是我們所要優(yōu)化的問題噩翠。

下面直接給出題目戏自，舉實(shí)際例子進(jìn)行分析：

leetcode 26題

這道題的輸入示例如下：

題目的意思相當(dāng)于把數(shù)組中重復(fù)的元素給過濾掉，并且不考慮數(shù)組中超出新長度后面的元素伤锚，那么直接對 nums[:newlength]進(jìn)行操作就好了浦妄。
考慮雙指針的方法，該方法的核心思路在于丟一個(gè)fast指針在前面探路，符合條件的就加入到slow的位置剂娄。對于這道題蠢涝，fast指針，便是判斷元素是否重復(fù)阅懦，至于具體如何操作和二，fast不管，只是一個(gè)勁往前沖耳胎。
代碼如下：

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        # 先進(jìn)行特例的判斷惯吕，如果nums本身沒有，直接返回零
        if not nums: return 0
        # 對slow怕午，fast指針初始化废登，size用來確定循環(huán)結(jié)束條件
        slow, fast, size = 0, 0, len(nums)
        # fast指針走到尾部，循環(huán)截至
        while fast < size:
            # 因?yàn)閿?shù)組已經(jīng)是排好序的郁惜，重復(fù)的元素一定是緊挨著
            # 所以能夠這樣判斷
            if nums[slow] != nums[fast]:
                slow += 1
                # 在slow位置上賦值為nums[fast]
                nums[slow] = nums[fast]
            # fast一直往前沖
            fast += 1
        # 返回長度
        return slow + 1

該題還有相應(yīng)的拓展

leetcode 80題

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        # 初始化slow，fast指針（從2開始）
        slow, fast = 2, 2
        size = len(nums)
        # 對特殊情況予以處理
        if size <= 2:
            return size
        # 循環(huán)的邊界確定
        while fast < size:  
            # 當(dāng)fast指針指向的元素虎韵，與當(dāng)前slow位置的前兩個(gè)元素不同時(shí)
            # 更新nums[slow]的元素          
            if  nums[slow - 2] != nums[fast]:
                nums[slow] = nums[fast]
                # 更新slow指針
                slow += 1
            # fast每一輪是必須要更新的
            fast += 1
        # 返回slow
        return slow

類似地易稠，如下題應(yīng)該很容易解答：

leetcode 27題

fast指針?biāo)赶虻脑刂恍枰?code>!=val就ok，代碼：

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        if not nums: return 0
        # 雙指針
        slow, fast, size = 0, 0, len(nums)

        while fast < size:
            # 進(jìn)行篩選
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        
        return slow

類似地包蓝，可以借用雙指針驶社，解如下題：

leetcode 283題

大概的思路：

• fast指針向前遍歷，當(dāng)nums[fast] != 0時(shí)测萎，nums[slow] = nums[fast]
• 當(dāng)fast指針越界亡电，循環(huán)停止時(shí)，slow指向的正好是數(shù)組中最后一個(gè)不為零的元素位置绳泉，此時(shí)將nums[slow]之后的元素置為零。
  
  
  代碼如下：

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        slow, fast, size = 0, 0, len(nums)
        # 特殊情況姆泻，直接返回nums
        if size == 1:
            return nums
        # 循環(huán)的邊界條件
        while fast < size:
            if nums[fast] != 0:
                nums[slow] = nums[fast]
                slow += 1

            fast += 1
        # 此時(shí)slow已經(jīng)指向了應(yīng)該為零的元素的位置
        while slow < size:
            nums[slow] = 0
            slow += 1

        return nums

第一天挑戰(zhàn)的題目都是簡單題零酪，很容易就cover住了，但重新總結(jié)一下拇勃，仍然有新的收獲~

Day 2 前綴和

前綴和的方法適用于快速計(jì)算某個(gè)索引區(qū)間內(nèi)的元素之和四苇，考慮這樣的場景：

nums = [x_1, x_2, ..., x_n]，想要計(jì)算該數(shù)組區(qū)間[k_1, k_2]之間的元素和方咆，那么應(yīng)該怎樣處理呢月腋？當(dāng)然，我們可以套上幾個(gè)for循環(huán)來解決，不能用暴力方法解決的算法題榆骚，只能說明方法還不夠暴力片拍。但是，我們知道妓肢，一旦套上for循環(huán)的方法捌省，基本上都會(huì)面臨超時(shí)的問題。

這時(shí)候或許就應(yīng)該考慮前綴和的技巧了碉钠，前綴和的技巧往往又與差分的思想結(jié)合起來使用纲缓。

舉例：

基于上述思想，來解決如下實(shí)際算法題：

leetcode 560 題

大概的思路：

• 初始化一個(gè)計(jì)數(shù)變量cnt喊废，當(dāng)某個(gè)子數(shù)組的區(qū)間和等于k時(shí)祝高，cnt += 1;
• 返回cnt.

代碼如下：

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        cnt, n = 0, len(nums)
        # 初始化前綴和數(shù)組
        pre = [0] * (n + 1)
        # 對nums的前i項(xiàng)進(jìn)行累加
        for i in range(1, n + 1):
            pre[i] = pre[i - 1] + nums[i - 1]
        # 尋找滿足和為k的子區(qū)間
        for i in range(1, n + 1):
            for j in range(i, n + 1):
                # 找到后，cnt += 1
                # 這個(gè)條件說明污筷，sum(nums[i:j]) == k
                if (pre[j] - pre[i - 1] == k):cnt += 1
        return cnt

這樣做的問題在于工闺，當(dāng)構(gòu)建好前綴和數(shù)組后，仍然需要用兩個(gè)for循環(huán)去匹配條件颓屑。果不其然斤寂，點(diǎn)擊提交按鈕，發(fā)現(xiàn)超時(shí)了...

這時(shí)候揪惦，考慮維護(hù)一個(gè)hashmap對前綴和方法優(yōu)化遍搞，看leetcode上的題解，一時(shí)半會(huì)兒也沒理解器腋，還是需要自己動(dòng)手畫個(gè)圖溪猿，結(jié)合幾個(gè)實(shí)際的例子：

代碼首先需要構(gòu)建這樣的一個(gè)haspmap，鍵是前綴和纫塌，值是該前綴和的個(gè)數(shù)诊县，構(gòu)建的同時(shí)，去匹配條件措左，當(dāng)滿足條件時(shí)依痊，計(jì)數(shù)變量cnt += 1，最后return cnt

代碼能夠清晰表達(dá)上述邏輯怎披，文字有時(shí)候不夠精煉胸嘁， show the code：

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # 初始化hashmap
        d = {}
        # 初始化前綴和以及計(jì)數(shù)變量
        acc, cnt = 0, 0
        for num in nums:
            acc += num
            # 這個(gè) if 的邏輯好理解
            if acc == k:
                cnt += 1
            # 這個(gè) if 的邏輯，結(jié)合圖凉逛，以及實(shí)際例子就好理解了
            if acc - k in d:
                cnt += d[acc - k]            
            # 構(gòu)建 hashmap 
            if acc in d:
                d[acc] += 1
            else:
                d[acc] = 1

        return cnt

前綴和的技巧同樣可以應(yīng)用于二維數(shù)組中性宏，解決如下題：

leetcode 304 題

初看這題，都沒多想状飞，直奔題解區(qū)ctrl c+v毫胜，趁著總結(jié)的機(jī)會(huì)书斜，算是把這題給弄懂了。

做此類初始化一次酵使，檢索多次的題目荐吉，對數(shù)據(jù)要進(jìn)行預(yù)處理

我們拿這題的示例來看：

暴力的for循環(huán)仍然能做，只不過復(fù)雜度太高了凝化，結(jié)合前面一維的前綴和技巧稍坯，這道題不過是在前綴和在二維的拓展。

因?yàn)樗蟮拇杲伲匀皇菙?shù)組的某個(gè)子數(shù)組的和瞧哟。

類比于一維的情況，拓展到二維枪向，本題的思路：

• 得到二維的 preSum勤揩，preSum[i, j] 表示從坐標(biāo)(0, 0)到(i, j)，這塊區(qū)域的元素和秘蛔；
• 利用 preSum陨亡，得到子矩陣 S[(row1, col1), (row2, col2)]范圍內(nèi)的元素和。
  具體地深员，S[(row1, col1), (row2, col2)] = S[(0, 0), (row2, col2)] - S[(0, 0), (row2, col1)] - S[(0, 0), (row1, col2)] + S[(0, 0), (row1, row1)]

結(jié)合代碼：

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        m, n = len(matrix), len(matrix[0])
        # 初始化二維前綴和矩陣
        self.preSum = [[0] * (n + 1) for _ in range(m + 1)]
        # 二維前綴和矩陣的賦值负蠕，由于多加了一次self.preSum[i][j]，所以要減一次
        for i in range(m):
            for j in range(n):
                self.preSum[i + 1][j + 1] = self.preSum[i + 1][j] + self.preSum[i][j + 1] - self.preSum[i][j] + matrix[i][j]



    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        # 由二維前綴和矩陣倦畅，直接得到某個(gè)子矩陣的元素和
        # 由于多減去了一次 self.preSum[row1][col1]遮糖，所以要加上
        return self.preSum[row2 + 1][col2 + 1] + self.preSum[row1][col1] - self.preSum[row1][col2 + 1] - self.preSum[row2 + 1][col1]

第二天挑戰(zhàn)的前綴和，首次做的時(shí)候確實(shí)很懵叠赐，重新梳理一下欲账，清晰多了。

Day 3 差分?jǐn)?shù)組技巧

對于Day2挑戰(zhàn)中學(xué)習(xí)到的前綴和芭概，我們可以總結(jié)它的適用場景：數(shù)組本身不進(jìn)行更改赛不，多次查詢某個(gè)區(qū)間內(nèi)的元素和。

差分?jǐn)?shù)組的主要適用場景則是：多次對原始數(shù)組的某個(gè)區(qū)間的元素進(jìn)行增減罢洲，當(dāng)題目中有表達(dá)出類似的意思時(shí)踢故，要想到差分?jǐn)?shù)組的技巧。

結(jié)合實(shí)際題目來說明問題：

leetcode 370 題

在數(shù)組的某個(gè)區(qū)間段nums[start, end]上進(jìn)行操作惹苗，例如+k操作殿较，等價(jià)于先在nums[start:]上+k，再在nums[end+1:]上-k鸽粉，結(jié)合下圖進(jìn)行說明：

對于這種+k再-k的套路斜脂，我們應(yīng)該如何在代碼中實(shí)現(xiàn)呢抓艳？這就要引出差分?jǐn)?shù)組了触机，設(shè)數(shù)組a[0,1,2..n]的差分?jǐn)?shù)組為d[0,1,2..n]，差分?jǐn)?shù)組的定義為：

• 當(dāng)i = 0時(shí)，d[0] = a[0]
• 當(dāng)i > 0時(shí)儡首，d[i] = a[i] - a[i - 1]

求差分?jǐn)?shù)組的過程片任，就是求前綴和數(shù)組的逆過程，對于原數(shù)組某個(gè)區(qū)間范圍[L, R]內(nèi)加減同一個(gè)數(shù)的更新操作蔬胯，反映到差分?jǐn)?shù)組上对供，只用更新區(qū)間兩端(L和R+1)位置的值

這句話怎么理解呢？由差分?jǐn)?shù)組的定義氛濒，易得：

a[i] = d[0] + d[1] + ... + d[i]

假設(shè)a[3], a[4], a[5]這三個(gè)數(shù)同時(shí)加上k产场，反映到差分?jǐn)?shù)組上d[3] + k，d[6] - k舞竿，將數(shù)組a展開：
a[0] = d[0]
a[1] = d[0] + d[1]
a[2] = d[0] + d[1] + d[2]
a[3] = d[0] + d[1] + .. (d[3] + k)
a[4] = d[0] + .. + (d[3] + k) + d[4]
a[5] = d[0] + .. + (d[3] + k) + d[4] + d[5]
a[6] = d[0] + .. + (d[3] + k) + .. + (d[6] - k)

可以看到京景，我們只需要對差分?jǐn)?shù)組邊界上的兩個(gè)元素進(jìn)行處理，就可以達(dá)到對原數(shù)組所對應(yīng)區(qū)間上的元素同時(shí)加上一個(gè)元素的效果骗奖，a[3]之前的元素不受影響确徙，a[5]之后的元素也不受影響。

代碼實(shí)現(xiàn)如下：

class Solution:
    def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
        # 初始化差分?jǐn)?shù)組
        d = [0 for _ in range(length)]
        
        # 在差分?jǐn)?shù)組的邊界元素上進(jìn)行操作
        for start, end, inc in updates:
            d[start] += inc
            if end + 1 < length:
                d[end + 1] -= inc

        # 整理差分?jǐn)?shù)組
        for i in range(1, length):
            d[i] += d[i - 1]

        return d

leetcode 1094 題

將題目的要求抽象出來执桌，其實(shí)就是一個(gè)區(qū)間和的問題鄙皇，當(dāng)某個(gè)區(qū)間上的承載量超過capacity時(shí)，返回False仰挣，結(jié)合上一題的分析伴逸，不難寫出該題的代碼：

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        # 原題中由寫明 0 <= trips.length <= 1000，
        # 所以初始化一個(gè)長度為1001的差分?jǐn)?shù)組
        diff = [0] * 1001
        # 對于原數(shù)組某個(gè)區(qū)間段的操作椎木，
        # 對應(yīng)到差分?jǐn)?shù)組的邊界上進(jìn)行處理
        for num, start, end in trips:
            diff[start] += num
            diff[end] -= num
        # preSum其實(shí)就是統(tǒng)計(jì)各個(gè)時(shí)間段上的乘客數(shù)
        # 一旦preSum > capacity违柏，return False
        preSum = 0
        for i in range(1001):
            preSum += diff[i]
            if preSum > capacity:
                return False

        return True

經(jīng)典的航班預(yù)定問題，其實(shí)是同樣的套路：

leetcode 1109 題

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        # 構(gòu)建差分?jǐn)?shù)組
        diff = [0] * n

        for first, last, seat in bookings:
            # first -= 1為了和數(shù)組的索引對應(yīng)
            first -= 1
            diff[first] += seat
            # last不需要再進(jìn)行 += 1的操作
            if last < n:
                diff[last] -= seat
        # 整理差分?jǐn)?shù)組
        for i in range(1, n):
            diff[i] += diff[i - 1]

        return diff

差分?jǐn)?shù)組的技巧馍惹，算是比較抽象。這種情況往往看別人的題解是難以完全看懂的玛界，應(yīng)該試著自己舉幾個(gè)實(shí)際例子万矾，結(jié)合起來，為什么原數(shù)組某個(gè)區(qū)間段上的操作慎框，對應(yīng)到差分?jǐn)?shù)組上就是在邊界上進(jìn)行操作就行良狈。以及為什么對差分?jǐn)?shù)組進(jìn)行累加，就可以得到想要的數(shù)組笨枯，將原數(shù)組以差分?jǐn)?shù)組的形式展開薪丁，便容易理解了遇西。

Day 4 回文串的判斷

回文串的判斷據(jù)說是面試的高頻題，盡管還不知道有啥具體實(shí)際意義严嗜。首先粱檀，明確回文串的定義，正著讀和反著讀都是一樣的字符串漫玄。

例如aaaa茄蚯，abcba，abccba都是字符串睦优，而abab就不是渗常，那么如何判斷某個(gè)字符串是否為回文串，其實(shí)是一個(gè)很簡單的問題汗盘，核心思路便是凳谦，從字符串的中間，借助雙指針衡未，向兩邊擴(kuò)散尸执，對指針指向元素是否相等進(jìn)行判斷。

回文串的判斷本身并不值得出題（很簡單）缓醋，往往會(huì)結(jié)合著其他條件如失，如下題：

leetcode 5 題

對字符串s中的元素進(jìn)行遍歷，分別作為回文子串的中心送粱，維護(hù)一個(gè)最大長度的變量：

這樣的處理乍看之下沒有問題褪贵，但忽視了回文子串長度為偶數(shù)的情況，例如字符串aabbccbbaa抗俄，其最大回文子串明顯就是它本身脆丁，但如果我們按照上述邏輯去處理的話睁蕾，只能找到長度為1的回文子串斗埂。

對于偶數(shù)長度的字符串，我們應(yīng)該取相鄰的兩個(gè)元素作為中心點(diǎn)扒袖，向外擴(kuò)散胰蝠，實(shí)際的處理中歼培，我們可以定義一個(gè)find函數(shù)，該函數(shù)的作用便是茸塞，找出當(dāng)前中心點(diǎn)的最長回文子串躲庄，由于題目中要求輸出子串，所以find函數(shù)钾虐，需要返回子串的左右索引噪窘。

那么這個(gè)find函數(shù)應(yīng)該傳入些什么參數(shù)呢？稍加分析效扫，不難確定倔监，要傳入字符串s无切，因?yàn)橐獙?code>s的左右側(cè)元素進(jìn)行比較；還需要傳入中心點(diǎn)丐枉，方便主函數(shù)中的遍歷。那么如何同時(shí)滿足奇數(shù)長度子串和偶數(shù)長度子串需求呢掘托？其實(shí)瘦锹，這時(shí)候傳入兩個(gè)參數(shù)left和right就好了，對于奇數(shù)情況闪盔，left == right弯院，一個(gè)中心點(diǎn)；對于偶數(shù)情況right = left + 1泪掀，兩個(gè)相鄰的中心點(diǎn)听绳。

結(jié)合代碼：

class Solution:
    def find(self, s, left, right):
        # find函數(shù)用來找以某元素為中心的最長回文子串
        # 返回位置索引
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1

        # 這里要將left和right退一個(gè)狀態(tài)
        return left + 1, right - 1
    
    def longestPalindrome(self, s: str) -> str:
        size = len(s)
        # 特殊情況判斷
        if size == 1:
            return s

        start, end = 0, 0

        for i in range(size):
            # 分別考慮子串長度為奇數(shù)以及偶數(shù)的情況

            # 奇數(shù)情況
            left1, right1 = self.find(s, i, i)

            # 偶數(shù)情況
            left2, right2 = self.find(s, i, i + 1)

            if right1 - left1 > end - start:
                end = right1
                start = left1

            if right2 - left2 > end - start:
                end = right2
                start = left2

        return s[start: end + 1]

Day 4 挑戰(zhàn)的算法題就這一道，明白回文串的定義异赫，懂得“從中間往兩邊擴(kuò)散”的套路椅挣，結(jié)合題目的條件，耐心分析塔拳。

Day 5 二分搜索技巧（基礎(chǔ)）

二分查找最基本的場景：尋找一個(gè)數(shù)鼠证，尋找左側(cè)邊界、尋找右側(cè)邊界靠抑。二分查找一般適用于有序數(shù)組量九，看到算法時(shí)間復(fù)雜度要求里面有l(wèi)og，就應(yīng)該想到二分颂碧。

二分查找的思路很簡單：

• 對于有序數(shù)組nums荠列，先取索引為中間位置的元素nums[mid]，與目標(biāo)target進(jìn)行比較载城，無非就三種情況：
  1. 當(dāng)nums[mid] == target時(shí)肌似，返回mid;
  2. 當(dāng)nums[mid] > target時(shí)，此時(shí)說明target只可能存在于數(shù)組的左側(cè)诉瓦；
  3. 當(dāng)nums[mid] < target時(shí)锈嫩，此時(shí)說明target只可能存在于數(shù)組的右側(cè)。
• mid = (right - left) // 2 + left垦搬，當(dāng)left > right時(shí)呼寸，說明數(shù)組中并沒有目標(biāo)元素target

二分查找的思路雖然很簡單，但對于邊界的細(xì)節(jié)問題猴贰，需要格外注意对雪，結(jié)合一道實(shí)際題目說明：

leetcode 704 題

這道題可謂是經(jīng)典的不能再經(jīng)典

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        # 在上圖的分析中迈套，left應(yīng)該允許等于right
        while left <= right:
            mid = (right - left) // 2 + left
            if nums[mid] > target:
                # 之所以right是用mid-1進(jìn)行更新猬膨，而不是mid
                # 考慮一個(gè)極端情況當(dāng)left == right == mid但
                # nums[mid] != target污它，此時(shí)循環(huán)出不去
                right = mid - 1
            elif nums[mid] < target:
                # left 也是用mid + 1進(jìn)行更新
                left = mid + 1
            else:
                return mid
        return -1

對于邊界的探討屡穗，為什么right和left都要在mid的上進(jìn)行+1或者-1的操作進(jìn)行更新帘瞭，難道不可以right = mid而left = mid + 1或者right = mid - 1而left = mid苦酱？

舉個(gè)實(shí)際例子說明躯砰，假設(shè)我們是按照right, left = mid, mid + 1這種形式對索引進(jìn)行更新方篮，那么當(dāng)nums[mid] > target，此時(shí)left = right - 1励负，此時(shí)的mid已經(jīng)是等于left了藕溅，那么right = left，仍然是會(huì)陷入nums[left] == nums[right] == nums[mid] != target的死循環(huán)中继榆。

借助二分查找的技巧巾表，解決下題：

leetcode 34

看到進(jìn)階要求，實(shí)現(xiàn)時(shí)間復(fù)雜度的算法為O(log n)略吨，加上數(shù)組本身是有序排列的集币，應(yīng)該立馬想到二分。

然而基本的二分查找方法翠忠，當(dāng)nums[mid] == target時(shí)便返回了鞠苟，應(yīng)該如何去尋找目標(biāo)值的開始位置和結(jié)束位置呢？

或許定義兩個(gè)二分查找的函數(shù)秽之，一個(gè)往左邊去擴(kuò)展当娱，當(dāng)擴(kuò)展到數(shù)組中的元素不等于target時(shí)停下，記錄下索引left考榨；一個(gè)往右邊去擴(kuò)展跨细，同樣記錄邊界索引right，最終主函數(shù)只需要返回[left, right]就ok了河质。

將思路梳理一下：

• 分別定義向左冀惭，向右的兩個(gè)探尋函數(shù)，函數(shù)的主題實(shí)現(xiàn)方式仍然是二分掀鹅；
• 對于探尋函數(shù)來講云头，當(dāng)nums[mid] == target時(shí)，并不直接返回淫半，而是分別再往左或右進(jìn)行擴(kuò)展溃槐；

在上述十分不嚴(yán)謹(jǐn)?shù)姆治鱿拢瑢τ谙蜃筇綄さ暮瘮?shù)返回的條件應(yīng)該是科吭，nums[low] == target昏滴；類似地，對于向右探尋的函數(shù)返回的條件應(yīng)該是对人，nums[high] == target

我們結(jié)合代碼進(jìn)行分析：

    def findleft(self, nums, target):
        low, high = 0, len(nums)-1
        # 整體框架仍然是二分查找的套路
        while low <= high:
            mid = (high - low) // 2 + low
            # 由于此時(shí)還需要往左側(cè)探尋谣殊，對于目標(biāo)在左側(cè)的情況
            # high = mid - 1
            if nums[mid] == target:
                high = mid - 1

            elif nums[mid] > target:
                high = mid - 1

            else:
                low = mid + 1
        
        # 當(dāng)循環(huán)結(jié)束，此時(shí)low = high + 1
        if nums[low] == target:
            return low

        # 說明數(shù)組本身連一個(gè)target都沒有
        else:
            return -1

負(fù)責(zé)探尋右側(cè)的函數(shù)和左側(cè)類似牺弄，需要改變的是if nums[mid] == target: low = mid + 1姻几，返回的是high

總代碼如下：

class Solution:
    def findleft(self, nums, target):
        low, high = 0, len(nums)-1

        while low <= high:
            mid = (high - low) // 2 + low
            if nums[mid] == target:
                high = mid - 1
            elif nums[mid] > target:
                high = mid - 1
            else:
                low = mid + 1

        if nums[low] == target:
            return low
        else:
            return -1

    def findright(self, nums, target):
        low, high = 0, len(nums)-1

        while low <= high:
            mid = (high - low) // 2 + low
            if nums[mid] == target:
                low = mid + 1
            elif nums[mid] > target:
                high = mid - 1
            else:
                low = mid + 1

        if nums[high] == target:
            return high
        else:
            return -1


    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # 先對特殊情況進(jìn)行判斷
        if not nums or target > nums[-1] or target < nums[0]:
            return [-1, -1]

        self.left = self.findleft(nums, target)
        self.right = self.findright(nums, target)

        return [self.left, self.right]

二分查找的技巧并不難，關(guān)鍵在于邊界的細(xì)節(jié)上，需要結(jié)合實(shí)際例子蛇捌，具體問題具體分析抚恒。

Day 6 二分搜索的應(yīng)用

實(shí)際的算法題目中很少直接說明在有序數(shù)組中搜索指定元素，往往會(huì)給出一些情景络拌，這時(shí)候就需要我們可以將問題給抽象出來俭驮，不要被表面的描述所迷惑了，私以為春贸，要具備這種抽象能力混萝，需要多刷題和總結(jié)。

直接拿實(shí)際題目說明：

leetcode 875 題

說實(shí)話萍恕，一開始看到這題逸嘀，連題目想讓我求什么都不太清楚。結(jié)合示例才把題目意思給搞明白允粤，但看懂題目意思后也沒有想到可以用二分的技巧求解崭倘。

對于有N堆的香蕉，由于珂珂不管她再能吃维哈，都要最起碼分N次給她吃完绳姨。那么登澜，這個(gè)最起碼的值是多少呢阔挠？稍加思索，不難得出當(dāng)k == max(piles)時(shí)脑蠕，珂珂可以N次吃完這N堆香蕉购撼，k繼續(xù)大下去，沒意義谴仙，也需要N次迂求；由于題目求的是最小值，自然只需要在[1, max(piles)]這個(gè)區(qū)間內(nèi)進(jìn)行搜索就好了晃跺。

一個(gè)樸素的想法就是從1一直遍歷到max(piles)揩局，當(dāng)首次滿足某個(gè)條件時(shí)，結(jié)束遍歷掀虎，得到的就是最小速度K凌盯。

我們可以定義一個(gè)函數(shù)幫助判斷，當(dāng)前K的值烹玉，珂珂是否能吃完所有的香蕉驰怎。仔細(xì)審題，對于這種多了的不算二打，少了的需要補(bǔ)齊的操作县忌，要想到整除操作。例如，某堆香蕉有8根症杏，當(dāng)速度為5時(shí)装获，需要兩次吃完（ 8 // 5 + 1），可以寫出如下代碼：

    def possible(piles, k, h):
        tmp = 0
        for p in piles:
            # 因?yàn)樵谡?+1鸳慈，所以p要先-1
            # 舉例饱溢，當(dāng)p = 5， k = 5走芋， tmp應(yīng)該等于1
            tmp += (p - 1) // k + 1
        if tmp <= h:
            return True
        else:
            return False

有了possible()函數(shù)后绩郎，可以直接在主函數(shù)中從小到大遍歷，當(dāng)滿足條件時(shí)候返回翁逞。這時(shí)候題目就轉(zhuǎn)換為了在有序數(shù)組中進(jìn)行搜素的問題肋杖，應(yīng)該想到二分查找，而且target也已經(jīng)定義好了挖函。
當(dāng)思路轉(zhuǎn)變到這状植，不難寫出如下代碼：

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        lo, hi = 1, max(piles)

        while lo <= hi: 
            # 仍然是拿中間的量先去比
            mid = (hi - lo) // 2 + lo
            # 當(dāng)滿足possible函數(shù)時(shí)，說明mid有點(diǎn)大了怨喘，或許可以更小津畸，更新變量hi
            if self.possible(piles, mid, h):
                hi = mid - 1
            # 當(dāng)不滿足possible函數(shù)時(shí)，說明mid大了必怜，更新lo
            else:
                lo = mid + 1
        return lo


    def possible(self, piles, k, h):
        tmp = 0
        for p in piles:
            tmp += (p - 1) // k + 1

        if tmp <= h:
            return True
        else:
            return False

從這一道題中肉拓，我們可以對二分查找的方法給抽象一下，總結(jié)二分搜索在以下場景適用：

• 可以得到一個(gè)單調(diào)函數(shù)f(x)梳庆，對于這個(gè)單調(diào)函數(shù)暖途，能夠得到自定域的左右邊界（該題便是1和max(piles))
• 有約束target（本題中的約束便是根據(jù)題意定義出來的possible函數(shù)），題目的要求是讓我們找到滿足約束條件f(x) == target時(shí)的x

再來看下面一道題：

leetcode 1011 題

這種場景題膏执，必須要結(jié)合示例的輸入輸出才能夠搞清楚它到底想問啥驻售。

對于weights這個(gè)數(shù)組而言，每個(gè)元素是不能拆開的更米。例如欺栗，當(dāng)船舶的運(yùn)載量為15，已經(jīng)載上了13的貨物征峦，這時(shí)候再來一個(gè)重量為3的貨物迟几，已經(jīng)裝不下了，不能把貨物拆成重量為2和1的兩件眶痰。此外瘤旨，需要按照weights的順序來裝，不能說看到后面有重量為2的竖伯，就先把它給裝進(jìn)去存哲。這時(shí)候因宇，只能隔天裝了，day += 1祟偷。

很顯然察滑，這道題的約束條件便是day <= days，承載量的上限是sum(weights)（一次性全部裝完）修肠，承載量的下限是max(weights)（單件貨物不能分開裝）

我們定義這道題的約束函數(shù)：

def helper(weights, days, cap):
    # 注意這里day變量的初始化應(yīng)該為1
    day = 1
    tmp = 0

    for weight in weights:
        tmp += weight
        # 此時(shí)裝載的重量已經(jīng)超過船舶的承載極限了
        if tmp > cap:
            # 天數(shù) + 1
            day += 1
            # tmp初始化為當(dāng)下的weight
            tmp = weight

    return True if day <= days else False

結(jié)合二分查找的技巧贺辰，不難寫出此題的答案

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        lo, hi = max(weights), sum(weights)

        while lo <= hi:
            mid = (hi - lo) // 2 + lo

            if self.helper(weights, days, mid):
                hi = mid - 1

            else:
                lo = mid + 1

        return lo
    

    def helper(self, weights, days, cap):
        day = 1
        tmp = 0
        for weight in weights:
            tmp += weight
            if tmp > cap:
                day += 1
                tmp = weight

        return True if day <= days else False

單純的二分查找，只需要注意邊界問題就行嵌施；對于各種各樣的場景題饲化，要對題目進(jìn)行抽象，這需要刷題的同時(shí)多進(jìn)行總結(jié)吗伤。

Day 7 滑動(dòng)窗口技巧

滑動(dòng)窗口的概念不難理解吃靠，就是對一個(gè)窗口依照某種規(guī)則進(jìn)行維護(hù)，不斷滑動(dòng)足淆，更新答案巢块。然而，到實(shí)際要寫代碼的時(shí)候巧号，經(jīng)常就是摸瞎族奢，憋半天敲不出一行代碼。

困難主要出現(xiàn)在以下幾點(diǎn)：

• 怎么向窗口中添加元素丹鸿；
• 怎么縮小窗口越走；
• 何時(shí)更新結(jié)果。

帶著上述問題卜高，我們來解決幾道算法題弥姻，結(jié)合題目來理解南片，總結(jié)出套路掺涛。

leetcode 3 題

既然這道題出現(xiàn)在滑動(dòng)窗口的專題下，也不藏著掖著了疼进，直接用滑動(dòng)窗口進(jìn)行分析：

在這道題中薪缆，滑動(dòng)窗口的刪減，一定是從左側(cè)進(jìn)行的伞广，因?yàn)?strong>子串要保持連續(xù)性拣帽；在分析中减拭，我們可以看到會(huì)有一個(gè)元素是否在窗口中的判斷区丑；此外修陡，窗口滑動(dòng)的過程可霎，明顯有一個(gè)頭部刪除，尾部添加的操作拾因。所以，當(dāng)我們能夠畫出一趟滑動(dòng)窗口的變化過程旷余，寫出代碼并不是很難的事情绢记。

代碼如下：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 特殊情況，當(dāng)s本身不存在的時(shí)候返回0
        if not s:
            return 0

        # 初始化window為一個(gè)棧結(jié)構(gòu)
        window = []
        maxlength = 0
        for i in range(len(s)):

            #當(dāng)s[i]在窗口中正卧，要?jiǎng)h除干凈庭惜，所以這里用while
            while s[i] in window:
                # 刪除頭部
                window.pop(0)
            # 尾部追加
            window.append(s[i])
            # 維護(hù)一個(gè)最大長度
            maxlength = max(maxlength, len(window))

        return maxlength

leetcode 567題

由于題目要求判斷的是否包含排列，這意味著穗酥，并不需要管s1本身字母的順序如何护赊，只要s1的子串中有即可，窗口的長度顯然需要依據(jù)s1的長度來確定砾跃。

對于每個(gè)窗口骏啰，只需要對相應(yīng)的字母計(jì)數(shù)，若與s1中字母計(jì)數(shù)的情況相同抽高，便返回True判耕，窗口滑動(dòng)完了還沒找到壁熄，返回False碳竟。

那么莹桅，具體應(yīng)該如何實(shí)現(xiàn)上述操作呢诈泼？

可以先定義兩個(gè)字母表，dictA和dicB岖赋，前者用以統(tǒng)計(jì)s1中各字母的個(gè)數(shù)唐断，后者，針對于每個(gè)滑動(dòng)窗口知牌，統(tǒng)計(jì)窗口下子串中各字母的個(gè)數(shù)角寸。

經(jīng)上述分析扁藕，可以寫出如下代碼：

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False

        # 初始化字母表
        dicA = [0] * 26
        dicB = [0] * 26
        
        m, n = len(s1), len(s2)

        for i in range(m):
            dicA[ord(s1[i]) - ord('a')] += 1
            dicB[ord(s2[i]) - ord('a')] += 1
            
        if dicA == dicB:
            return True

        for i in range(m, n):
            # 出窗口操作
            dicB[ord(s2[i-m]) - ord('a')] -= 1
            # 進(jìn)窗口操作
            dicB[ord(s2[i]) - ord('a')] += 1

            if dicA == dicB:
                return True

        return False

懂得了這道題的套路亿柑，應(yīng)該可以絲滑地解決下面這道題

leetcode 438 題

這道題無非是改一下leetcode 567題的輸出望薄，寫出如下代碼：

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        
        if len(s) < len(p):
            return []
        dicA = [0] * 26
        dicB = [0] * 26

        n, m = len(s), len(p)
        ans = []
        for i in range(m):
            dicA[ord(s[i]) - ord('a')] += 1
            dicB[ord(p[i]) - ord('a')] += 1

        if dicA == dicB:
            ans.append(0)

        for i in range(m, n):
            # 出操作
            dicA[ord(s[i - m]) - ord('a')] -= 1
            # 進(jìn)操作
            dicA[ord(s[i]) - ord('a')] += 1
            if dicA == dicB:
                ans.append(i - m + 1)
        return ans

借助滑動(dòng)窗口的技巧痕支，來正兒八經(jīng)地解決一道hard題

leetcode 76 題

解此題的思路不難想到：

• 初始化left, right = 0, 0卧须，移動(dòng)right指針花嘶，擴(kuò)大窗口蹦漠。當(dāng)窗口包含所有需要的元素津辩，記錄下此時(shí)的長度喘沿，以及指針竭贩，維護(hù)變量minlength留量；
• 向右移動(dòng)left，如果窗口中不再包含所有需要的元素忆绰，移動(dòng)right错敢，記錄此時(shí)長度，判斷是否比minlength小纸淮，如果是咽块，更新minlength侈沪，并記錄left, right峭竣。
• 繼續(xù)移動(dòng)left皆撩，對數(shù)組中的元素進(jìn)行遍歷哲银，相當(dāng)于對所有包含所有需要的元素的窗口進(jìn)行了比較荆责，最終記錄下來的一定是滿足要求的最小子串做院。

從上面的分析键耕，最重要的一點(diǎn)是判定窗口已經(jīng)包含所需要元素。

可以利用一個(gè)need字典村视，用來記錄當(dāng)下窗口中的元素蚁孔，初始化need = {A:1, B:1, C:1}栓撞，表示本來需要的是1個(gè)A敲街，1個(gè)B和1個(gè)C笛钝；

窗口滑動(dòng)時(shí)玻靡，我們需要維護(hù)need這個(gè)字典囤捻，當(dāng)滑動(dòng)窗口包含某個(gè)元素時(shí)蝎土，就讓need中這個(gè)元素對應(yīng)的數(shù)值減少1誊涯；當(dāng)滑動(dòng)窗口移除某個(gè)元素時(shí)暴构，就讓need中這個(gè)元素對應(yīng)的數(shù)值增加1取逾。

例如苹支，當(dāng)滑動(dòng)窗口中元素為ADOBEC時(shí)债蜜，need = {A:0, B:0, C:0, D:-1, E:-1, O:-1}寻定，元素D、E晶丘、O其實(shí)是多余的浅浮，但是沒關(guān)系滚秩，此時(shí)need中所有的元素都小于等于0郁油，所以此時(shí)這個(gè)滑動(dòng)窗口一定包含了所需要的元素攀痊。

此時(shí)苟径，當(dāng)left指針向左移動(dòng)一個(gè)單位棘街，滑動(dòng)窗口中的元素變?yōu)?code>DOBEC時(shí)，need = {A:1, B:0, C:0, D:-1, E:-1, O:-1}石挂，這表示痹愚，還缺少一個(gè)元素A里伯，所以right指針應(yīng)該滑動(dòng)疾瓮，使得need中所有元素都小于等于0時(shí)飒箭，停止滑動(dòng)弦蹂，此時(shí)的滑動(dòng)窗口再一次包含所有所需要的元素凸椿。

每一次對字典need的遍歷，判斷其中的值是否均小于等于零咙崎，會(huì)帶來O(k)的時(shí)間復(fù)雜度吨拍，我們可以再定義一個(gè)needcnt變量羹饰，專門表示需要元素的數(shù)量是否滿足需要队秩，need[c]>0，便表示c是需要的元素筒主。

可以寫出如下代碼：

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if len(s) < len(t): return ""

        need = collections.defaultdict(int)

        for c in t:
            need[c] += 1
        needcnt = len(t)
        left = 0
        res = (0, float('inf'))

        for right, c in enumerate(s):

            if need[c] > 0:
                needcnt -= 1

            need[c] -= 1

            # 滑動(dòng)窗口中已經(jīng)包含了所有的元素
            if needcnt == 0: 
                while True:
                    c = s[left]
                    if need[c] == 0:
                        break

                    need[c] += 1
                    left += 1
                if right - left < res[1] - res[0]:
                    res = (left, right)

                need[s[left]] += 1

                needcnt += 1
                left += 1

        return '' if res[1] > len(s) else s[res[0]: res[1] + 1]

滑動(dòng)窗口的思路不難理解物舒，關(guān)鍵在于如何對窗口進(jìn)行更新冠胯，如最小覆蓋子串問題荠察，第一次做很難想到會(huì)定義一個(gè)needcnt變量悉盆，用以判斷當(dāng)下窗口是否滿足條件焕盟。熟能生巧宏粤，需要多加練習(xí)绍哎。

Day 8 鏈表技巧匯總

Day 7的挑戰(zhàn)確實(shí)感到難度提升上來了，盡管自己梳理了一遍但感覺還是有些地方?jīng)]有理解好沃于。但不管怎么樣繁莹，要邁向下一天的挑戰(zhàn)了，我的更新進(jìn)度還是被拖慢了一些盾似。

Day 8的題目比較簡單雪标，直接結(jié)合相關(guān)的算法題來總結(jié)一下鏈表題的相關(guān)套路村刨。

leetcode 141 題

判斷鏈表是否有環(huán)嵌牺，實(shí)屬鏈表的經(jīng)典題了逆粹，鏈表題常采用雙指針的操作僻弹。

那么對于這道題蹋绽，如果用雙指針的技巧應(yīng)該怎么去解呢筋蓖？其實(shí)很簡單粘咖，就是定義一個(gè)fast一個(gè)slow指針瓮下，fast指針移動(dòng)的速度要快于slow。

這樣两蟀，一旦fast和slow在除Null外的位置相遇赂毯，那么鏈表中就一定存在環(huán)党涕，想到于在跑步比賽里面被人給套圈了膛堤。

可以寫出如下的代碼：

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head: return False

        fast = head.next
        slow = head

        while fast and fast.next:
            # fast要比slow快一步
            fast = fast.next.next
            slow = slow.next
            # 此時(shí)代表相遇
            if fast == slow:
                return True

        # 當(dāng)跳出了while，說明fast == None或者fast.next == None
        # 此時(shí)已經(jīng)到了終點(diǎn)绿渣，只有直線才有終點(diǎn)中符，說明無環(huán)淀散，返回False
        return False

再接再厲档插，我們再來解決下題

leetcode 142 題

在141題中郭膛，我們學(xué)會(huì)了如何判斷鏈表中是否有環(huán)针余，142題更進(jìn)一步圆雁，要求返回一個(gè)pos參數(shù)伪朽。

• 先初始化slow和fast指針，起點(diǎn)位置相同朴肺，fast指針的速度是slow指針?biāo)俣鹊膬杀叮?/li>
• 設(shè)鏈表的長度為m（對于示例1戈稿，m = 4)鞍盗，設(shè)環(huán)的長度為k（對于示例1，k = 3)肋乍，那么敷存，fast指針一定比slow指針多走nk步（n為正整數(shù)1锚烦，2挽牢，...）摊求；
• fast指針走了2nk步室叉，slow指針走了nk步茧痕；
• 可以確定slow指針的位置：
  [nk - (m - k)] % k + (m - k)，此時(shí)只要slow指針多走(m - k)步曼氛，就返回了環(huán)的初始位置(m - k)舀患；
• 再定義一個(gè)新的指針newslow聊浅，從頭開始低匙，newslow速度為1碳锈。那么售碳，當(dāng)slow指針與fast指針相遇時(shí)佩迟，一定是在環(huán)的初始位置（都走了（m - k）步）报强。

可以寫出如下代碼：

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        fast, slow = head, head

        while True:
            if not (fast and fast.next):
                return
            fast, slow = fast.next.next, slow.next

            if fast == slow: break

        newslow = head

        while newslow != slow:
            newslow, slow = newslow.next, slow.next

        return newslow

leetcode 876 題

對于這道題秉溉，一開始的想法是先讓指針走一趟召嘶，統(tǒng)計(jì)出鏈表的長度k弄跌，然后再讓指針從頭再走k // 2步（要根據(jù)題目要求調(diào)整）铛只，返回鏈表的中間節(jié)點(diǎn)淳玩。

根據(jù)上述思想蜕着，不難寫出如下代碼：

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        fast = head
        k = 0
        while fast:
            fast = fast.next
            k += 1

        step = k // 2 

        fast = head
        while step:
            fast = fast.next
            step -= 1

        return fast

但是這道題如是要求红柱，掃描一趟鏈表就可以返回中間節(jié)點(diǎn)锤悄，那么我們應(yīng)該如何做呢铁蹈？

還是采用雙指針的方法，快指針的速度是慢指針?biāo)俣鹊膬杀度菸埽?dāng)快指針到達(dá)鏈表終點(diǎn)览徒，慢指針正好到達(dá)鏈表的中間位置习蓬。

根據(jù)上述思想，不難寫出如下的代碼：

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        slow, fast = head, head

        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

        return slow

leetcode 160 題

一開始看到這道題的難度為簡單芦缰，正準(zhǔn)備重拳出擊让蕾，結(jié)果發(fā)現(xiàn)一時(shí)半會(huì)兒也想不到什么好思路探孝。

這道題其實(shí)有點(diǎn)類似于leetcode 142題誉裆，開始嘗試想著用雙指針的技巧足丢，最好也是能當(dāng)兩個(gè)指針碰到的時(shí)候，正好是兩個(gè)單鏈表的起始節(jié)點(diǎn)栖疑。

• 定義兩個(gè)指針A = headA和B = headB，指針移動(dòng)的速度相同揭糕；
• 當(dāng)指針A走完了headA锻霎，開始從headB往下走旋恼；當(dāng)指針B走完了headB，開始從headA往下走产徊，兩者相遇的位置舟铜，便是相交鏈表的初始位置谆刨。

leetcode 19 題

經(jīng)過了前面幾題的聯(lián)系，這道題的思路應(yīng)該不難想到刁岸，定義fast和slow兩個(gè)指針难捌，
fast指針先走n步根吁，slow指針再出發(fā)合蔽，當(dāng)fast指針走到末尾時(shí)拴事，slow指針正好走到倒數(shù)第n個(gè)節(jié)點(diǎn)的位置刃宵。

此時(shí)刪除操作也很簡單，slow.next = slow.next.next（具體細(xì)節(jié)可能需要調(diào)整）哮针；然而十厢，為了方便對涉及到head節(jié)點(diǎn)時(shí)操作更方便蛮放，需要定義dummy變量奠宜，dummy.next=head.

對于示例1的情形压真，可以直接返回head榴都，也可以返回dummy.next嘴高，此時(shí)設(shè)不設(shè)置dummy并沒有多大的差別和屎；對于示例2的情形，head都被刪除了随常，真是拿頭返回枣察，此時(shí)就需要dummy節(jié)點(diǎn)的幫助了叛赚。

不難寫出如下代碼红伦，注意fast指針和slow指針的起始位置淀衣，理想情況膨桥，fast指針走到末尾只嚣，slow指針走到要被刪除元素的前一位册舞。

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:

        dummy = ListNode()
        dummy.next = head

        fast, slow = head, dummy

        for _ in range(n):
            fast = fast.next

        while fast:
            fast = fast.next
            slow = slow.next

        slow.next = slow.next.next

        return dummy.next

鏈表的操作多涉及到雙指針的技巧调鲸，一個(gè)跑一個(gè)追，期待能與你相遇藐石，做個(gè)算法題還有幾分感動(dòng)于微。此前對dummy節(jié)點(diǎn)的用法也是不清楚株依，經(jīng)過一番梳理，有種恍然大悟的感覺抹锄。

Day 9 隊(duì)列和椘碓叮互轉(zhuǎn)

作為最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)车份，想必都能扯兩句牡彻，隊(duì)列是先進(jìn)先出庄吼，棧是先進(jìn)后出。

對于這兩種數(shù)據(jù)結(jié)構(gòu)如何相互轉(zhuǎn)換器罐，我們結(jié)合相關(guān)算法題進(jìn)行分析：

leetcode 232 用棧實(shí)現(xiàn)隊(duì)列

借助兩個(gè)棧來實(shí)現(xiàn)隊(duì)列的“先進(jìn)先出”：

只有執(zhí)行pop()以及peek()時(shí)轰坊，對棧B是否為空進(jìn)行判斷肴沫。此時(shí)颤芬，如果棧B為空站蝠，將棧A中的元素全部倒入棧B中，經(jīng)過棧B再將需要的元素彈出或者返回郁副。

代碼如下：

class MyQueue:

    def __init__(self):
        self.A = []
        self.B = []

    def push(self, x: int) -> None:
        self.A.append(x)

    def pop(self) -> int:
        if not self.B:
            while self.A:
                self.B.append(self.A.pop())

        return self.B.pop()

    def peek(self) -> int:
        if not self.B:
            while self.A:
                self.B.append(self.A.pop())

        return self.B[-1]

    def empty(self) -> bool:

        return not self.A and not self.B

Day 10 單調(diào)棧

當(dāng)題目的題意表達(dá)出類似于“尋找最近一個(gè)比某元素大”時(shí)存谎，要想到單調(diào)棧的技巧解答既荚。

leetcode 496 下一個(gè)更大元素 I

對于這道簡單題恰聘，是可以采用暴力解法的晴叨，只需要在nums2中找到對應(yīng)nums1的元素矾屯，再向右搜尋即可件蚕，不難寫出如下代碼：

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        n = len(nums1)
        res = [-1] * n

        for i in range(n):
            # 找到nums2中對應(yīng)元素的索引
            j = nums2.index(nums1[i])
            for k in range(j+1, len(nums2)):
                if nums2[k] > nums1[i]:
                    res[i] = nums2[k]
                    break
            
        return res

對于簡單題我們可以這樣處理排作，但稍微對時(shí)空復(fù)雜度做出一點(diǎn)限制，暴力解法就會(huì)超時(shí)哈雏。

那么僧著，如果采用單調(diào)棧的技巧，這道題應(yīng)該如何解決呢栅迄？

這道題目里面雖然有個(gè)nums1，但實(shí)際上找的仍然是nums2中每個(gè)元素的下一個(gè)更大元素愈腾。對于示例1岂津，我們可以定義一個(gè)字典吮成，鍵就是nums2中的每個(gè)元素，值就是所對應(yīng)的下個(gè)更大元素泳叠，得到dic = {1:3, 3:4, 4:-1, 2:-1}危纫。然后對于nums1中的每個(gè)元素种蝶，映射到dic中瞒大，找到每個(gè)值糠赦，返回結(jié)果就是我們需要的。

單調(diào)棧就是幫助我們建立起這樣一個(gè)字典的手段淌山，不難畫出單調(diào)棧的形成過程：

由于是尋找下一個(gè)最大的元素泼疑，所以逆序遍歷會(huì)高效很多退渗。對遍歷到的每一個(gè)元素会油，先和棧頂?shù)脑剡M(jìn)行比較古毛，如果棧頂元素較小都许，刪去棧頂元素胶征，繼續(xù)比較睛低。

當(dāng)棧頂出現(xiàn)比遍歷元素大的元素時(shí)钱雷，說明該遍歷元素右側(cè)的第一個(gè)最大值急波，為此時(shí)的棧頂元素瘪校，若棧刪空了阱扬，說明遍歷元素右側(cè)沒有比它大的了

如上圖，逆序遍歷馍刮，遍歷到的首個(gè)元素是1卡啰，此時(shí)椌唬空杀迹，1右側(cè)沒有比1大的元素了；遍歷到第二個(gè)元素是7浅碾，此時(shí)棧內(nèi)的元素只有1垂谢，1比7小埂陆，刪去1，此時(shí)棧空懂版，說明7的右側(cè)也沒有比7大的元素了。

基于上述分析民鼓，我們可以寫出如下代碼：

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        res, stack = {}, []

        for num in reversed(nums2):
            # 和棧頂元素比較
            while stack and num > stack[-1]:
                stack.pop()
            # 若棧內(nèi)存在元素丰嘉，res[num]賦值為棧頂元素饮亏；若椩乃空付翁，賦值為-1
            res[num] = stack[-1] if stack else -1

            stack.append(num)

        # 根據(jù)所構(gòu)造的字典進(jìn)行映射
        return [res[num] for num in nums1]

接下來解決503題

leetcode 503. 下一個(gè)更大元素 Ⅱ

題目中所謂的循環(huán)查找百侧，其實(shí)最多也就是掃描數(shù)組兩遍，當(dāng)?shù)诙檫€沒有滿足條件的元素時(shí)辫狼，說明是真沒有了予借。此時(shí)灵迫，我們可以通過取余映射來完成掃描數(shù)組兩次的操作晦溪。

相較于上一題三圆，該題的單調(diào)棧并不直接存儲(chǔ)元素了避咆，而是存儲(chǔ)對應(yīng)的索引查库，我們可以畫出示意圖：

當(dāng)索引值被彈出時(shí)樊销，說明此時(shí)找到了比索引值對應(yīng)元素大的元素围苫，初始化一個(gè)輸入res = [-1] * n剂府，其中n = len(nums)剃盾，那么只需要將數(shù)組res彈出索引的位置上的元素賦值為所找到的万俗，比索引值對應(yīng)元素大的元素，最終的res就是答案嚎研。

文字屬實(shí)有點(diǎn)繞临扮，結(jié)合代碼就能夠明白什么意思了

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        # 單調(diào)棧初始化
        stack = []
        # 初始化res
        res = [-1] * n
        # 最多遍歷兩趟
        for i in range(2 * n - 1):
            # stack 中存儲(chǔ)的索引杆勇，所以比較的對象還要映射到數(shù)組中
            while stack and nums[i % n] > nums[stack[-1]]:
                # 此時(shí)找到了更大的元素饱亿，根據(jù)彈出索引位置賦值
                res[stack.pop()] = nums[i % n]
            # stack 中存儲(chǔ)索引
            stack.append(i % n)

        return res

了解了這種在棧中存入索引的操作彪笼，不難解決下題

leetcode 739 每日溫度

不難畫出如下構(gòu)造單調(diào)棧的過程：

棧中每彈出一個(gè)索引配猫，就說明找到了比該彈出索引對應(yīng)元素大的元素，例如當(dāng)i=1時(shí)捆交，棧中存放的索引是0，temperatures[1] > temperatures[0]玄括，由于題目求的是當(dāng)天后的第幾天惠豺，所以對于temperatures[0]來講风宁，返回的應(yīng)該是1 - 0 = 1戒财；

同理饮寞，當(dāng)i = 5時(shí)幽崩，彈出棧的索引為4和3寞钥，那么對于temperatures[4]來講理郑，返回的應(yīng)該時(shí)5 - 4 = 1；對于temperatures[3]來講柒爵，返回的應(yīng)該時(shí)5 - 3 = 2.

基于上述分析棉胀，不難寫出如下代碼：

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        size = len(temperatures)
        stack = []
        ans = [0] * size

        for i in range(size):
            while stack and temperatures[i] > temperatures[stack[-1]]:
                out = stack.pop()
                ans[out] = i - out

            stack.append(i)

        return ans

Day 11 二叉樹訓(xùn)練

許多經(jīng)典算法唁奢，實(shí)質(zhì)上都是樹的問題畸写，例如回溯算法、動(dòng)態(tài)規(guī)劃算法等论笔。此外，二叉樹相關(guān)的題目也是最練習(xí)遞歸基本功蒜埋，有助于我們理解遞歸思想整份。

遞歸算法的關(guān)鍵：明確函數(shù)的定義烈评，并且相信這個(gè)定義犯建，但不要跳入細(xì)節(jié)中。

leetcode 226 翻轉(zhuǎn)二叉樹

明確題意竿开，要求我們做到對二叉樹上的每個(gè)節(jié)點(diǎn)的左右子節(jié)點(diǎn)進(jìn)行交換否彩。
1.對根節(jié)點(diǎn)的左右子節(jié)點(diǎn)進(jìn)行交換列荔；
2.對根節(jié)點(diǎn)的左節(jié)點(diǎn)的左右子節(jié)點(diǎn)進(jìn)行交換称杨，對根節(jié)點(diǎn)的右節(jié)點(diǎn)的左右子節(jié)點(diǎn)進(jìn)行交換姑原；

3. ....

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        
        tmp = root.left
        root.left = root.right
        root.right = tmp

        self.invertTree(root.left)
        self.invertTree(root.right)

        return root

leetcode 116 填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針

子樹內(nèi)的左節(jié)點(diǎn)和右節(jié)點(diǎn)連接并沒有什么問題锭汛，問題的關(guān)鍵在于如何將在子樹之間的節(jié)點(diǎn)連接。由于連接是從左至右的般婆，最右側(cè)子樹的右節(jié)點(diǎn)沒有連接的對象蔚袍，只能指向[Null]啤咽，依此來進(jìn)行判斷。

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if not root:
            return None
        if root.left:
        # 如果樹還沒有到底
            root.left.next = root.right
            if root.next:
            # 如果還沒到最右側(cè)
                root.right.next = root.next.left
      
        self.connect(root.left)
        self.connect(root.right)

        return root

leetcode 114 二叉樹展開為鏈表

題目要求展開后的單鏈表要與二叉樹的先序遍歷相同瓶佳，所以展開后的左子樹要接在展開后的右子樹之前霸饲。

對于遞歸問題厚脉，具體考慮最后一步怎么處理胶惰，前面的步驟相信我們所定義的函數(shù)能夠完成。

不難寫出如下代碼：

class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if not root:
            return 

        # 相信所定義的flatten函數(shù)，可以將左子樹與右子樹展開
        self.flatten(root.left)
        self.flatten(root.right)

        left = root.left
        right = root.right

        root.left = None

        root.right = left

        p = root
        while p.right:
            p = p.right

        p.right = right

Day 12 二叉搜索樹基礎(chǔ)

二叉搜索樹（Binary Search Tree, BST)剃斧，特點(diǎn)：左小右大

BST的定義：

1. BST中任意一個(gè)節(jié)點(diǎn)的左子樹所有節(jié)點(diǎn)的值都小于該節(jié)點(diǎn)的值幼东，右子樹所有節(jié)點(diǎn)的值都大于該節(jié)點(diǎn)的值根蟹；
2. BST中任意一個(gè)節(jié)點(diǎn)的左右子樹都是BST.

基于BST的這種特性糟秘，在其中采用類似于二分搜索的操作纺弊，搜索一個(gè)元素的效率很高狸驳。

Leetcode 700 二叉搜索樹中的搜索

題目較為簡單寻狂，分情況討論：
1冰寻、如果val < root.val，說明需要在當(dāng)前根節(jié)點(diǎn)的左子樹尋找轻腺；
2、如果val > root.val诀拭，說明需要在當(dāng)前根節(jié)點(diǎn)的右子樹尋找煤蚌；
3尉桩、如果val == root.val，說已經(jīng)找到翰苫；
4奏窑、如果root.val == None屈扎，直接返回None.

class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root or root.val == val:
            return root

        if val < root.val:
            return self.searchBST(root.left, val)

        if val > root.val:
            return self.searchBST(root.right, val)

Leetcode 701 二叉搜索樹中的插入操作

仍然是分情況討論：
1鹰晨、當(dāng)val < root.val模蜡，說明要插入該根節(jié)點(diǎn)的左子樹，插入后對根節(jié)點(diǎn)的左子樹進(jìn)行更新root.left = self.insertIntoBST(root.left, val);
2闯传、當(dāng)val > root.val丸边，說明要插入該根節(jié)點(diǎn)的右子樹荚孵，插入后對根節(jié)點(diǎn)的右子樹進(jìn)行更新root.right= self.insertIntoBST(root.right, val)
3、當(dāng)根節(jié)點(diǎn)不存在骄呼，插入新節(jié)點(diǎn)蜓萄，并返回，return TreeNode(val)

class Solution:
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root:
            return TreeNode(val)
        if val < root.val:
            # 說明要插入左子樹中
            root.left = self.insertIntoBST(root.left, val)

        else:
            # 說明要插入右子樹中
            root.right = self.insertIntoBST(root.right, val)

        return root

Leetcode 98 驗(yàn)證二叉搜索樹

二叉搜索樹的中序遍歷一定是升序的：左 --> 根 --> 右辟犀，據(jù)此驗(yàn)證二叉搜索樹

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        # 判斷中序遍歷  左 --> 根 --> 右  為升序遍歷
        stack, inorder = [], float('-inf')

        while stack or root:
            while root:
                stack.append(root)
                root = root.left

            root = stack.pop()

            if root.val <= inorder:
                return False

            inorder = root.val
            root = root.right

        return True

Day 13

leetcode 102. 二叉樹的層序遍歷

采用廣度優(yōu)先算法堂竟，逐層向下掃描出嘹，借助隊(duì)列依次讓每層節(jié)點(diǎn)出隊(duì)

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        queue = [root]
        res = []

        while queue:
            length = len(queue)
            level = []
            for _ in range(length):

                node = queue.pop(0)

                level.append(node.val)

                if node.left:
                    queue.append(node.left)

                if node.right:
                    queue.append(node.right)

            res.append(level)

        return res

leetcode 111.二叉樹的最小深度

遞歸實(shí)現(xiàn)深度優(yōu)先算法税稼，遞歸需要寫出：

1. 終止條件郎仆；
2. 不要陷入遞歸丸升，將一棵樹簡化為根節(jié)點(diǎn)牺氨，左子節(jié)點(diǎn)猴凹，右子節(jié)點(diǎn)三個(gè)節(jié)點(diǎn)郊霎；
3. 只考慮當(dāng)前做什么爷绘，不用考慮下次應(yīng)該做什么；（人做事應(yīng)該也是如此）
4. 每次調(diào)用應(yīng)該返回什么购对。

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        # 特殊情況
        if not root: return 0

        # 特殊情況
        if root.left is None and root.right is None:
            return 1

        if root.left and root.right:
            return min(self.minDepth(root.left), self.minDepth(root.right)) + 1

        if root.left:
            return self.minDepth(root.left) + 1

        if root.right:
            return self.minDepth(root.right) + 1