Zako's Blog

題目網址：https://leetcode.cn/problems/implement-trie-prefix-tree/ 題意：Trie 也稱作 prefix tree, 是一種可以高效儲存、取得 string 中的 key 的資料結構。這一資料結構有相當多的應用情境, 例如 : 自動補全和拼寫檢查。 請實現 Trie class： Trie()：初始化 trie object void insert(String word)：插入 word bool search(String word)：返回 word 是否已經存在於 trie 中 boolean startsWith(String prefix) ：若已經插入的 word 的前綴之一為 prefix, 則 return true 注意：word 和 prefix 僅由小寫字母所組成。 Solution： 想法：先用一個 root 作為所有開頭 TrieNode 之 dummy node Trie() : 初始化 root void insert(String word) : 遍歷 word 中的每個 char, 若 ...

題目網址：https://leetcode.cn/problems/design-add-and-search-words-data-structure/ 題意：請設計一資料結構, 支持新增單字、搜尋 string 是否和先前新增的單字匹配。 實作 WordDictionary class： WordDictionary()：初始化 instance void addWord(word)：將 word 新增到資料結構中, 之後可以對它進行匹配 bool search(word)：如果資料結構中存在 string 和 word 匹配, 則返回 true ; 否則, 返回 false。word 中可能包含一些 ., 每個 . 都可表示成任何一個 char 注意： addWord 中的 word 只由小寫字母所組成 search 中的 word 由 . or 小寫字母所組成 Solution： 想法：利用 Trie + DFS, 一旦遇到 ., 就對當前 node 中所有的 child 進行 DFS class TrieNode {public: TrieNo ...

題目網址：https://leetcode.cn/problems/k-closest-points-to-origin/ 題意：給一 array points 和一整數 k, 其中 points[i] = [x_i, y_i] 表示平面上的一個點, 返回距離 (0, 0) 最近的 k 個點。 平面上兩點的距離是採用歐式距離 $\sqrt{(x1 - x2)^2 + (y1 - y2)^2}$ 可以按任何順序返回答案。 Solution： 想法：利用 Heap, 用 max heap 維護前 k 小的元素, 類似 347. Top K Frequent Elements 先將前 k 個元素加入到 max heap 中 後面 n - k 個點, 都是先 insert 到 heap 中再 pop 掉, 來維持 heap 中 k 個元素 此時, heap 中為前 k 小的元素, 將其取出即可 typedef tuple<int, int, int> t3i; // {dist, x, y}class Solution {public: ...

題目網址：https://leetcode.cn/problems/kth-largest-element-in-an-array/ 題意：給一 array nums 和一整數 k, 返回第 k 大的元素。 注意：你需要找的是 nums 排序後的第 k 大的元素, 而非第 k 個不同的元素。 設計滿足 $O(n)$ time 的演算法。 Solution 1： 想法：利用 Heap, 維護前 k 大的元素, 類似 347. Top K Frequent Elements class Solution {public: int findKthLargest(vector<int>& nums, int k) { priority_queue<int, vector<int>, greater<>> pq; // min heap for (const auto& num : nums) { pq.emplace(num); ...

題目網址：https://leetcode.cn/problems/task-scheduler/ 題意：給一 char array tasks 代表 CPU 須執行的任務 list, 其中每個字母代表一種不同種類的任務, 任務能以任意順序執行, 且每個任務皆可在 1 個單位時間內完成。在任意一個時間單位, CPU 可以選擇完成一個任務 or 處於待命狀態。 然而, 在兩個相同種類的任務之間必須有長度為 n 的冷卻時間。 計算並返回完成所有任務的最短時間。 注意：tasks[i] 必為大寫字母。 Solution 1： 想法：利用 Greedy + Heap, 應該處理的出現次數最多的 task, 盡量讓每一輪都能塞滿 n + 1 個 task（因為題目要求最短時間）。盡量先取高頻的 task, 然後再來取低頻的 task, 理由如下： 若改成優先取那些低頻的 task, 可能會讓低頻的 task 一下就被取完, 導致剩下的 task 整體的多樣性減少。當 max heap 中的 task 種類 < n + 1, 但每一輪又要取 n + 1 個時, 就會需要使用 idle ...