用網路形式相互連接的節點

頂點：節點

邊：edge，一對節點

權重/成本

有向圖

無向圖

鄰接矩陣

鄰接表

廣度優先搜尋DFS

深度優先搜尋TFS

實現廣度和深度優先搜索

檢查圖是否為樹

計算圖的邊數

求兩個頂點之間的最短距離

也稱為：前綴樹，特殊的樹狀資料結構

解決字串相關問題很有效

提供快速檢索

搜尋字典中的單字

搜尋引擎中自動提供建議

用於IP的路由

計算字典樹中的總單字數

列印儲存在字典樹中的所有單字

使用字典樹對數組中的元素進行排序

使用字典樹從字典形成單字

建構T9字典：字典樹 DFS

鍵值對的形式儲存唯一識別的對象

字典：鍵值對的集合

使用鍵key搜尋物件value

Java 中的 HashSet / HashMap，C 中的 unordered_map，Python 中的 dict

<br>工作原理：對於set。 key透過hash函數得到一個index，然後把value存在數組裡。 <br>對於get，透過key和hash函數求出index，得到value。

key可以是字串，整數等未知長度的東西。所以用O(L)合適；任何操作的時間複雜度從嚴格意義上來說 都是 O(keySize) 而不是 O(1)<br>

128 哈希函數

衝突（Collision），是說兩個不同的 key 經過雜湊函數的計算後，得到了兩個相同的值。解決衝突的方法，主要有兩種：<br>開散列法（Open Hashing）。是指哈希表所基於的陣列中，每個位置是一個 Linked List 的頭結點。這樣衝突的 <key, value> 二元組，就都放在同一個鍊錶中。 <br>閉散列法（Closed Hashing）。是指在發生衝突的時候，後來的元素，往下一個位置去找空位<br>

129 重哈希

哈希函數

哈希表大小

碰撞處理方法

數組中尋找對稱的鍵值對

是否會靈活的使用哈希表解決問題

是否熟練哈希表的基本原理

追蹤便利的完整路徑

尋找數組是否為另一個數組的子集

檢查給定的陣列是否不相交

526. 負載平衡器<br>

134. LRU快取策略<br>657. Insert Delete GetRandom O(1)<br>954. Insert Delete GetRandom O(1) - Duplicates allowed<br>209. 第一個只出現一次的字符

Data Stream類別問題<br>960. First Unique Number in a Stream II<br>138.子陣列總和<br>105. 複製隨機指標的鍊錶<br>171. 亂序字串<br>124.最長連續序列

插入排序

快速排序

選擇排序

歸併排序

基數排序

堆排序

靜態查找表

動態查找表

哈希表

演算法1:O(n) lowerBound O(1) add

演算法2:O(logn) lowerBound O(logn) add

一維數組

二維數組

多維數組

子數組

數組區間問題

外排序問題

位元運算

樹狀數組很少考

增get

刪delete

插入insert、

大小size

尋找數組中第二小的元素

找第一個不重複的整數

重新排列數組中的正負值

65. 兩個排序數組的中位數，難題<br>

6. 合併排序數組II<br>64.合併排序數組<br>839.合併兩個排序的間隔列表<br>486. Merge K Sorted Arrays<br>577.合併K個排序間隔列表<br>547 . 兩個數組的交集<br>548. 兩個數組的交集II<br>793. 多個數組的交集<br>654. 稀疏矩陣乘法<br>931. Median of K Sorted Arrays<br>149. 買賣股票的最佳時機<br>405. 和為零的子矩陣<br>944. Maximum Submatrix<br>943. Range Sum Query - Immutable<br>665. 平面範圍求和-不可變矩陣<br>840.可變範圍求和

後進先出LIFO。例如物流裝車，後裝的貨物先卸

用於非遞歸的遍歷二元樹，計算逆波蘭表達式，等等。

非遞歸實現DFS的主要資料結構

在寬度優先搜尋(BFS）中，記錄待擴展的節點。

佇列可用於實作訊息佇列（message queue），以完成非同步（asynchronous）任務。

當訊息生產和消費的速度不一致時，就需要訊息佇列，暫時保存那些已經發送而並未接收的訊息。

用一個儲存結構（常用數組，偶見鍊錶），儲存元素

用一個陣列實作三個堆疊？

用兩個佇列實作一個棧？ <br>

差別

練習題<br>

push，頂部插入元素

pop返回並且移除棧頂元素

isEmpty堆疊是空，回傳true

top返回頂部元素，但不移除它

Java，使用java.util.Stack，它是擴展自Vector類，支援push()，pop()，peek()，empty()，search()等操作。

C ，使用<stack>中的stack即可，方法類似Java，只不過C 中peek()叫做top()，而且pop()時，回傳值為空。

Python，直接使用list，查看棧頂用[-1]這樣的切片操作，彈出棧頂時用list.pop()，壓棧時用list.append()。 <br>

使用堆疊計算後綴表達式

對棧的元素進行排序

判斷表達式是否括號平衡

FIFO先進先出的順序儲存線性資料結構，超市結帳

用作 BFS 演算法的主要資料結構

enqueue隊列尾插入元素

dequeue移除隊列頭部元素

isEmpty對列為空，回傳true

top傳回佇列的第一個元素

用鍊錶實作隊列？

用兩個棧實作一個佇列？ <br>

用循環數組實作佇列？

使用佇列表示堆疊

對隊列的前面k個元素倒序

使用佇列產生1到n的二進制數

642. Moving Average from Data Stream<br>

955. Implement Queue by Circular Array<br>

節點鏈：每個節點包含資料和指向後續節點的指針

實作檔案系統，哈希表，鄰接表

單向鍊錶

雙向鍊錶

insertAtEnd

insertAtHead

Delete

DeleteAtHead

Search

isEmpty,為空，回傳true

反轉鍊錶

檢測鍊錶中的循環

返回鍊錶倒數第n個節點

刪除鍊錶中重複項

層級式的資料結構

頂點和邊組成

樹中沒有圖中的環路

root根節點

parent父節點

child子節點

leaf葉子節點

sibling兄弟節點

N元樹

線段樹，基本上不考，萬能的

二元樹，常考

求二元樹高度

在二元搜尋樹中尋找第k個最大值

找出和根節點距離k的節點

在二元樹中尋找給定節點的祖先節點

104. Merge K Sorted Lists<br>