📄️ 10.1 C++ STL
在刷題時,我們幾乎一定會用到各種資料結構來輔助我們解決問題,因此我們必須熟悉各種資料結構的特點。C++ STL 提供的資料結構包括(實際底層細節可能因編譯器而異):
📄️ 10.2 Python 常用資料結構
類似於 C++ STL,Python 也提供了許多資料結構(實際底層實作細節可能因編譯器而異):
📄️ 10.3 陣列
448. Find All Numbers Disappeared in an Array
📄️ 10.4 堆疊與佇列
232. Implement Queue using Stacks
📄️ 10.5 單調堆疊
單調堆疊透過維持堆疊內值的單調遞增(遞減)性,可以在整體 $O(n)$ 的時間內解決需要大小比較的問題。
📄️ 10.6 優先佇列
優先佇列(priority queue)可以在 $O(1)$ 時間內獲得最大值,並且可以在 $O(\log n)$ 時間內取出最大值或插入任意值。
📄️ 10.7 雙端佇列
239. Sliding Window Maximum
📄️ 10.8 雜湊表
雜湊表(hash table, hash map),又稱散列表,使用 $O(n)$ 空間複雜度儲存資料,通過雜湊函數(hash function)映射位置,從而實現近似 $O(1)$ 時間複雜度的插入、查詢、刪除等操作。雜湊表可以用來統計頻率、記錄內容等等。
📄️ 10.9 多重集合和映射
332. Reconstruct Itinerary
📄️ 10.10 前綴和與積分圖
一維的前綴和(cumulative sum, cumsum),二維的積分圖(summed-area table, image integral)是通過將每個位置之前的一維線段或二維矩形的數值預先計算並儲存,從而加速後續的查詢與計算。如果需要對前綴和或積分圖的值進行查找,可以將其存入雜湊表;如果需要對每個位置記錄前綴和或積分圖的值,則可以將其儲存到一維或二維數組中,通常還伴隨著動態規劃。
📄️ 10.11 練習
基礎難度