閒人筆記

更新紀錄： 2022.03.01 更新網路資料 2 的連結 網路資料： Link  中文維基百科 Link Robert Sedgewick 教授的 Algorithm 4th 配套投影片 觀念紀錄： Union-Find 是一種 data structure 也可以是一種類型的問題。 問題的主要描述是： Find(x, y): 回傳 x, y 是否屬於同一個 set Union(x, y): 合併 x, y 所屬的 set 之所以會說是一種 data structure 是因為，實務上高效率解決這類問題的作法是一種特定的資料結構。 Python 程式碼: class UnionFind: def __init__(self, n): self.id = [i for i in range(n)] self.sz = [1 for _ in range(n)] def root(self, i): while i != self.id[i]: self.id[i] = self.id[self.id[i]] i = self.id[i]; return i def find(self, p, q): return self.root(p) == self.root(q) def unite(self, p, q): i = self.root(p) j = self.root(q) if self.sz[i] <= self.sz[j]: self.id[i] = j self.sz[j] += self.sz[i] else: self.id[j] = i self.sz[i] += self.sz[j]

主要目標： 紀錄 defaultdict 的概念跟常見用法。 說明： 帶有預設值的 dictionary ，第一個參數是一個可呼叫的物件，後面接的參數會直接給 dict 當參數使用。 例如： defaultdict(int, {'a': 10, 'b': 20}) 等同於會呼叫的意思： dict({'a': 10, 'b': 20}) 整理最常用的方法：  1. 要計算所有的東西有多少個：  d = defaultdict(int)  d[x] += 1  2. 要把同一個 key 的東西串在一起：  d = defaultdict(list)  d[x].append(y)  3. 要使用指定的預設值：  d = defaultdict(lambda :False) 參考資料： https://docs.python.org/3/library/collections.html#collections.defaultdict