DSA

含有「DSA」共 17 篇內容
全部內容
發佈日期由新至舊
在之前的教學中,已經學會了Node和Linked List的實作, 用Python實現了單向鏈結串列Singly linked list、雙向鏈結串列Doubly linked list。 並且用雙向鏈結串列來實作Queue(佇列 或稱 隊列)。 今天要從Python 內建deque資料結
Thumbnail
深入探討圖(Graph)的基本概念 及 最短路徑Shortest Path的尋找。 我們專注於廣度優先搜尋(BFS)演算法,以等權圖的最短路徑為例, 詳細說明如何利用BFS從起點擴散到終點,並且提供詳細的程式碼範例。 透過實作,讀者能夠更清楚理解圖論及BFS的應用,並體會水波紋擴散模型的重要性。
Thumbnail
定義 圖Graph: 由節點和邊所組成的一個網狀資料結構。 圖的表達方式Graph representation: 常見的有相鄰串列adjacency list或相鄰矩陣adjacency matrix。 本文以adjacenct list作為示範。 節點Vertex: 節點
Thumbnail
定義 圖Graph: 由節點和邊所組成的一個網狀資料結構。 圖的表達方式Graph representation: 常見的有相鄰串列adjacency list或相鄰矩陣adjacency matrix。 本文以adjacenct list作為示範。
Thumbnail
Min-Heap 最小堆是一種特殊的樹狀資料結構, 其中每個節點的值都小於或等於其子節點的值。這意味著最小值總是位於根節點。 Min-Heap 常用於實作優先權佇列 (Priority Queue)、Dijkstra 演算法、 排序以及尋找中位數等應用。
Thumbnail
Prefix Sum(前綴和)是一種用於計算陣列中任意區間和的高效方法。 前綴和算是一種犧牲空間換取時間效能提升的策略。 這在需要頻繁查詢區間和的情況下特別有用。 一開始,初始化時花費O(n)時間,掃描每個元素累加,建立一個prefix sum table, 接著,提供query介面查詢區間和
Thumbnail
二元搜尋樹(Binary Search Tree,簡稱 BST)是一種特殊的二元樹結構, 具有以下特性: 左子樹:左子樹上所有節點的值均小於該節點的值。 右子樹:右子樹上所有節點的值均大於該節點的值。 無重複值:每個節點的值都是唯一的。 這些特性使得二元搜尋樹在搜尋、插入和刪除操作具有較佳的效能。
Thumbnail
接著來進入圖論的重點之一,Tree與Binary Tree。 二元樹(Binary Tree)是一種樹狀數據結構,其中每個節點最多有兩個子節點,通常稱為左子節點和右子節點。這些子節點可以是其他節點或空節點(即無子節點)。 二元樹是其他進階樹的基礎,可延伸推廣到Binary Search Tree
Thumbnail
看樣子真的要找時間來學
今天,我們將用Python list來實現Disjoint Set (併查集,另外也有人稱之為Union-Find)。 Disjoint Set適合用於處理一些子集合的合併和根節點的查找操作。 這種資料結構在圖論中非常有用,特別是在解決連通性相關問題的應用。
Thumbnail
在之前的教學中,已經學會了用雙向鏈結串列來實作Stack 堆疊。 今天,要用另一種底層資列結構,python list,來實作Stack 堆疊。 讀者可以從中發現,因為python list的功能和function實作已經很豐富, 所以使用起來,相當直覺,也簡單許多。
Thumbnail