# python筆記 ## 演算法模板Algorithm ### deque deque(全名double-ended queue)，為一種兩端都可以放入,取出元素的資料結構。 | 尾部插入 | 頭部插入 | 尾部刪除 | 頭部刪除 | | -------- | ---------- | -------- | -------- | | append | appendleft | pop | popleft | ```python= # deque實作queue的用法 q = deque() q.append() q.popleft() ``` ### priority queue 預設是min-heap，也就是會按照小到大排序。 若要實作max-heap，可將元素x以-x的方式放入pq，取出元素時加個負號即可取出最大元素。 ```python= pq = [] heappush(pq, element) element = heappop(pq) ``` ### defaultdict 內置參數: int, list, set, dict ```python= better_dict = defaultdict(list) # default值以一個list()方法產生 better_dict['a'].append(1) # [1] better_dict['a'].append(2) # [1,2] better_dict['a'].append(3) # [1,2,3] ``` #### 查看多個字典中，共有幾種不同的字典值 ```python= unique_dicts = set() for d in dicts: dict_tuple = tuple(sorted(d.items())) # 將字典轉換為排序過的tuple unique_dicts.add(dict_tuple) print(len(unique_dicts)) ``` ### 字典樹 Trie 為一種有序樹，通常用來存放字串，鍵值（字元）存放在節點中。 ```python= class Node: def __init__(self): # self.cnt_prf = 0 self.children = collections.defaultdict(Node) class Trie: def __init__(self): self.root = Node() def insert(self, word: str) -> None: node = self.root for c in word: node = node.children[c] # node.cnt_prf += 1 ``` ### format string ```python= h, m = 13, 57 formatted_num = "{:02d}:{:02d}".format(h, m) # 02d代表要輸出長度為2的字串 print(formatted_num) # 输出: '13:57' ``` ### itertools ```python= original_list = [1, 2, 3] all_combinations = [] for r in range(len(original_list) + 1): combinations_r = itertools.combinations(original_list, r) all_combinations.extend(combinations_r) # [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)] ``` ```python= original_list = [1, 2, 3] permutations_3 = itertools.permutations(original_list, 3) # [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)] ``` ### 排列組合 ```python= def C(n, k): # 組合 if k > n or k < 0: return 0 return math.factorial(n) // (math.factorial(k) * math.factorial(n - k)) def P(n, k): # 排列 if k > n or k < 0: return 0 return math.factorial(n) // math.factorial(n - k) def H(n, k): # 重複組合 return C(n+k-1, k) ``` ### binary search ```python= l, r = 0, len(nums) while l < r: mid = (l+r)//2 if nums[mid] > target: r = mid elif nums[mid] < target: l = mid+1 else: return mid return -1 ``` ## 虛擬環境Virtual Environment 以下介紹的為python原生的venv，除此之外還有conda等虛擬環境可以使用。 ### 建立虛擬環境 name_env為安裝虛擬環境的資料夾名稱 ```bash= python3 -m venv name_env ``` 接著當前目錄下應該會出現一個資料夾裡頭有著虛擬環境的檔案。當不再需要用到虛擬環境時，可直接將/name_env資料夾刪除即可。 ### 啟用虛擬環境 ```bash= source name_env/bin/activate ``` 如果命令列最前面出現(name_env)，即代表成功開啟了虛擬環境 ### 查看虛擬環境位址 ```bash= which python3 ``` ### 套件管理 查看已有什麼套件 ```bash= pip3 list ``` 下載&更新套件。若不指定版本的話，會預設下載最新版本。 ```bash= pip3 install package_name pip3 install package_name==version pip3 install --upgrade package_name ``` 刪除套件 ```bash= pip3 uninstall package_name ``` ### 關閉虛擬環境 ```bash= deactivate ```