Leetcode # 210. Course Schedule II
https://leetcode.com/problems/course-schedule-ii/ Explanation 使用 in-degree 關鍵在於 優先提取 in-degree 為 0 的 vertex（即該 vertex 已無任何前導 vertex） vertex被提取時，調整其子 vertex 的 in-degree 當 graph 中有 loop 當 graph 中有 loop ...
A1go
[Python] list, set, dict, collections (deque, defaultdict, Counter)
- 2021.12.23
- collections Counter defaultdict deque dict frozenset list Python Queue set
list 常用操作 Operation Syntax ATC Append an item x to the last lst.append(x) O(1) Remove and return the last (most left) item in the list lst.pop() O(1) Remove and return the ith item in the list lst.pop ...
Leetcode # 5. Longest Palindromic Substring (Manacher’s Algorithm)
- 2021.12.22
- Algorithm Dynamic Programming LeetCode
https://leetcode.com/problems/longest-palindromic-substring/ Solution Dynamic Programming \begin{align*} & \text{定義 } P(i, j) \text{ 為：} \\ & P(i, j)= \begin{cases} True & \text{, if the s ...
Leetcode # 902. Numbers At Most N Given Digit Set
- 2021.12.22
- Dynamic Programming LeetCode
https://leetcode.com/problems/numbers-at-most-n-given-digit-set/ Solution class Solution: def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int: n_str = str(n) l = len(n_str) dp = [0] * ...
Leetcode # 143. Reorder List
- 2021.12.22
- LeetCode Linked List
https://leetcode.com/problems/reorder-list/ Key point 使用一快一慢的pointer來找到length和middle node Solution class Solution: def reorderList(self, head: Optional[ListNode]) -> None: """ Do not return anythin ...
[Python] Sorting
概覽 Syntax Description Average Time Complexity Space Complexity list_b = sorted(list_a) 回傳排序好的新list O(n * log(n)); n = len(list_a) O(n) list_a.sort() 將list_a排序 O(n * log(n)) O(n) 常用auguments key 排序時以ke ...
Leetcode # 53. Maximum Subarray (Kadane’s Algorithm)
- 2021.12.09
- ★★ Medium Dynamic Programming Kadane’s Algorithm LeetCode
https://leetcode.com/problems/maximum-subarray/ Solution \begin{align} &\text{max_ending_here } := \mathop{\max}_{i \in [0, j]}\quad{\mathop{\sum}_{k=i}^j{nums[k]}} \\ &\text{max_so_far } := \ ...
Dynamic Programming
- 2021.12.09
- Algorithm Dynamic Programming Kadane’s Algorithm Memoization Optimized Space Complexity Tabulation
動態規劃在尋找有很多重疊子問題的情況的最佳解時有效。 動態規劃儲存遞迴時計算子問題的結果， 因而不會在解決同樣的問題時花費時間。 適用條件 最佳子結構 Optimal Substructure 如果問題的最佳解所包含的子問題的解也是最佳的，我們就稱該問題具有最佳子結構性質（即滿足最佳化原理）。最佳子結構性質為動態規劃演算法解決問題提供了重要線索。 無後效性 Without Aftereffect ...
Disjoint Set Union (DSU)
- 2021.11.29
- Disjoint Set Union
為 disjoint (non-overlapping) sets 設計的資料結構 演算法 Time Complexity: O(node 的數量) Space Complexity: O(node 的數量) 使用「秩(rank)」能在連結兩元素時所建立的樹較為平均 「秩(rank)」的定義如下： 只有根節點的樹（即只有一個元素的集合），秩為0 當兩棵秩不同的樹合併後，新的樹的秩為原來兩棵樹的秩的 ...
Early Return Pattern
- 2021.11.28
- Programming Techniques / Tools
說明 def some_method(...): if some_conditions: ...statementsA... else: ...statementsB... 改寫作： def some_method(...): if some_conditions: ...statementsA... return ...statementsB... 好處 提高程式的可讀性，透過預先排除不符規格的 ...
