LeetCode刷題時遇到的有“名”算法（頻繁更新中。。。）

1. 分治法（240.搜尋二維矩陣 II）

思路：

• 左下角的元素是這一行中最小的元素，同時又是這一列中最大的元素。比較左下角元素和目标：
  • 若左下角元素等于目标，則找到
  • 若左下角元素大于目标，則目标不可能存在于目前矩陣的最後一行，問題規模可以減小為在去掉最後一行的子矩陣中尋找目标
  • 若左下角元素小于目标，則目标不可能存在于目前矩陣的第一列，問題規模可以減小為在去掉第一列的子矩陣中尋找目标
• 若最後矩陣減小為空，則說明不存在

應用擴充

• 歸并排序 

2.動态規劃（887. Super Egg Drop ）

聯系

• 沒有分叉，一路推理 ➜ 〔線性結構〕
• 看到決策結果有分叉 ➜ 〔樹形結構〕
• 若在推理過程中，産生交彙 ➜ 〔圖結構〕

3.遞歸回溯（131. 分割回文串）

 特點：

• 遞歸：在函數的定義中使用函數自身的方法，把規模大的問題轉化為規模小的子問題來解決。
• 回溯：從問題的某一種狀态（初始狀态）出發，搜尋從這種狀态出發所能達到的所有“狀态”，當一條路走到“盡頭”的時候（不能再前進），再後退一步或若幹步，從另一種可能“狀态”出發，繼續搜尋，直到所有的“路徑”（狀态）都試探過。

應用

• 遞歸：漢諾塔
• 回溯：四/八皇後

4. 字首樹

特點：

即字典樹，又稱單詞查找樹或鍵樹，是一種樹形結構，是一種哈希樹的變種。典型應用是用于統計和排序大量的字元串（但不僅限于字元串），是以經常被搜尋引擎系統用于文本詞頻統計。它的優點是：最大限度地減少無謂的字元串比較，查詢效率比哈希表高。

思想：

空間換時間，利用字元串的公共字首來降低查詢時間的開銷以達到提高效率的目的。 

它有3個基本性質：

1. 根節點不包含字元，除根節點外每一個節點都隻包含一個字元。
2. 從根節點到某一節點，路徑上經過的字元連接配接起來，為該節點對應的字元串。
3. 每個節點的所有子節點包含的字元都不相同。

5.大頂堆（378. 有序矩陣中第K小的元素）

思路：

設定K容量堆，依次存入大值，多于K個後删除堆内最大值，排序完成後堆首值即為矩陣内第K小值。 

注：對于python語言執行速度較差，用大頂堆的思路解決第K小元素問題時運作逾時，需安裝如下思路解題：

class Solution:
    def kthSmallest(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        lo, hi = matrix[0][0], matrix[-1][-1]
        while lo <= hi:
            mid = lo + (hi-lo)//2
            loc = self.countLower(matrix, mid)
            if loc >= k:
                hi = mid - 1
            else:
                lo = mid + 1
        return lo

    def countLower(self, matrix, num):
        i, j = len(matrix) - 1, 0
        cnt = 0
        while i >= 0 and j < len(matrix[0]):
            if matrix[i][j] <= num:
                cnt += i + 1
                j += 1
            else:
                i -= 1
        return cnt
           

6.快慢指針（141.環形連結清單）

給定一個連結清單，判斷連結清單中是否有環。為了表示給定連結清單中的環，我們使用整數 

pos

 來表示連結清單尾連接配接到連結清單中的位置（索引從 0 開始）。 如果 

pos

 是 

-1

，則在該連結清單中沒有環。

思路：

通過使用具有 不同速度 的快、慢兩個指針周遊連結清單，空間複雜度可以被降低至 O(1)O(1)。慢指針每次移動一步，而快指針每次移動兩步。

如果清單中不存在環，最終快指針将會最先到達尾部，此時我們可以傳回 

false

。

現在考慮一個環形連結清單，把慢指針和快指針想象成兩個在環形賽道上跑步的運動員（分别稱之為慢跑者與快跑者）。而快跑者最終一定會追上慢跑者。這是為什麼呢？考慮下面這種情況（記作情況 A） - 假如快跑者隻落後慢跑者一步，在下一次疊代中，它們就會分别跑了一步或兩步并相遇。

其他情況又會怎樣呢？例如，我們沒有考慮快跑者在慢跑者之後兩步或三步的情況。但其實不難想到，因為在下一次或者下下次疊代後，又會變成上面提到的情況 A。

複雜度分析

• 時間複雜度：O(n)O(n)， 讓我們将 nn 設為連結清單中結點的總數。為了分析時間複雜度，我們分别考慮下面兩種情況。

  • 連結清單中不存在環：

    快指針将會首先到達尾部，其時間取決于清單的長度，也就是 O(n)O(n)。

  • 連結清單中存在環：

    我們将慢指針的移動過程劃分為兩個階段：非環部分與環形部分：

    1. 慢指針在走完非環部分階段後将進入環形部分：此時，快指針已經進入環中 \text{疊代次數} = \text{非環部分長度} = N疊代次數=非環部分長度=N
    2. 兩個指針都在環形區域中：考慮兩個在環形賽道上的運動員 - 快跑者每次移動兩步而慢跑者每次隻移動一步。其速度的內插補點為1，是以需要經過 \dfrac{\text{二者之間距離}}{\text{速度內插補點}}速度內插補點二者之間距離​ 次循環後，快跑者可以追上慢跑者。這個距離幾乎就是 "\text{環形部分長度 K}環形部分長度 K" 且速度內插補點為 1，我們得出這樣的結論 \text{疊代次數} = \text{近似于}疊代次數=近似于 "\text{環形部分長度 K}環形部分長度 K".
  是以，在最糟糕的情形下，時間複雜度為 O(N+K)O(N+K)，也就是 O(n)O(n)。
• 空間複雜度：O(1)O(1)， 我們隻使用了慢指針和快指針兩個結點，是以空間複雜度為 O(1)O(1)。

 7.歸并排序（手懶中。。）

（python，使用list實作連結清單https://blog.csdn.net/dinnerhowe/article/details/58191823）

8.快速排序（手懶中。。）