Posts

383. Ransom Note Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise. Each letter in magazine can only be used once in ransomNote. 規則 給予 ransomNote(target) 和 magazine(dict) 拼字，如果拼得出來=True，反之為 False。 測試案例 Example 1: Input: ransomNote = "a", magazine = "b" Output: false Example 2: Input: ransomNote = "aa", magazine = "ab" Output: false Example 3: Input: ransomNote = "aa", magazine = "aab" Output: true 思路 根據規則每個字只能用一次，如果重複使用則返回 False 創建 hashmap 儲存 magazine values loop 依序遞減 解法 def canConstruct(self, ransomNote: str, magazine: str): values = {} for c in magazine: if c not in values: # 不存在 hashmap 內 values[c] = 1 # 建立 else: values[c] += 1 # 有則+1 for c in ransomNote: if c not in values or values[c] == 0: # 不存在或已經用完 return False else: values[c] -= 1 # 有則-1 return True 使用內建 defaultdict 來處理 hashmap，解法大同小異，但速度較快且代碼更簡潔。...

Global search 搜尋條件 以什麼欄位搜尋 // 單獨 protected static ?string $recordTitleAttribute = 'title'; // 多個 public static function getGloballySearchableAttributes(): array { return ['title', 'slug', 'author.name', 'category.name']; } 客製化搜尋結果欄位顯示，舉例來說 title = Yish 前面想要添加 author.name: public static function getGlobalSearchResultTitle(Model $record): string { return $record->author->name .':'. $record->name; } 添加更多內容在搜尋結果欄位內： public static function getGlobalSearchResultDetails(Model $record): array { return [ 'Author' => $record->author->name, 'Category' => $record->category->name, ]; } 使用何種 query 來作搜尋，這邊可以看到我們必須先 eager load author 和 category:...

1. Two Sum Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order. 規則 給一組陣列以及 target，回傳某兩數 index 相加等於 target 數。 測試案例 Example 1: Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1]....

34. Find First and Last Position of Element in Sorted Array Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value. If target is not found in the array, return [-1, -1]. You must write an algorithm with O(log n) runtime complexity. 規則 尋找已排序過的陣列找到 first 和 last target 數 測試案例 Example 1: Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4] Example 2: Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1] Example 3: Input: nums = [], target = 0 Output: [-1,-1] 思路 透過已排序過的輸入，透過二元搜尋法切割查找 找到 first 和 last，回傳 index 如果沒找到則回傳 -1 實作 nums = [1, 3, 3, 5, 7, 8, 9, 9, 9, 15] target = 9 print(Solution()....

98. Validate Binary Search Tree Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key. Both the left and right subtrees must also be binary search trees....

這篇文章是翻譯自 Binance academy，因為寫得相當清楚且好懂，可以從頭了解大概所謂的網路擁塞是如何發生的。 TL;DR 區塊鏈網路擁塞發生在提交到網路的交易量超過網路的處理量。 交易活動增加、小的區塊大小，以及產塊的時間都會造成網路擁塞。 區塊鏈網路擁塞結果會包含以下幾種狀況：增加交易手續費、緩慢的交易確認，以及糟糕的用戶體驗。 在2023 春天，比特網路由於 BRC-20 代幣交易活動量增加導致待處理交易跟交易手續費飆升。 網路擁塞到底是什麼？ 網路擁塞發生在提交到網路的交易量超過網路的處理量。這種現象有幾種影響因素，像是外部因素，包含市場波動、既有網路特定像是區塊大小與產塊時間。 在我們深入細節之前，來看看如何將區塊添加到區塊鏈的過程。 區塊鏈是如何運作的？ 區塊鏈由一系列的區塊組成，每個區塊包含使用者創建的交易數據。每當新的區塊被添加到鏈上時，它就是永久且不可改變的。 這些區塊在分散式節點網絡中傳播，每個節點都存儲著區塊鏈的副本。區塊鏈以加密和博弈理論為基礎，是比特幣和以太坊等加密貨幣的支柱。 要完全理解區塊鏈網絡為何會擁塞，我們需要探討幾個關鍵概念，這些概念對於網絡處理交易的能力起著重要作用：記憶池、候選區塊、確定性和最長鏈原則。 什麼是「記憶池」？ 一個 mempool 指得是等待被包含到下一個區塊的未確認交易集合。 例如，當一筆交易在比特幣網絡上廣播時，它不會立即被添加到區塊鏈中。相反，它首先進入內存池（簡稱為mempool），這實際上是所有待處理交易的等待區域。一旦交易得到確認，它將從內存池中移除。 「候選區塊」是什麼？ 候選區塊，也被稱為「提議區塊」，是礦工或驗證者提議添加到區塊鏈中的區塊。這些區塊包含尚未被納入區塊鏈的未確認交易，這些交易已經被廣播到網絡上。 要使候選區塊成為確認區塊，必須根據區塊鏈的共識機制進行挖礦或驗證。例如，比特幣的工作量證明（PoW）共識機制讓礦工們競爭解決一個複雜的數學問題。第一個解決問題的礦工可以將其候選區塊添加到區塊鏈並獲得獎勵。 在以太坊的權益證明（PoS）共識機制中，驗證者被隨機選擇來提出候選區塊。其他驗證者則對該區塊的有效性進行證明。當一個區塊獲得足夠的證明時，它從候選區塊轉變為確認區塊。 區塊鏈中的 “finality”(最終性) 是什麼？ 當一筆交易或操作無法再被改變或撤銷時，我們稱之為「確定性」。一旦交易達到確定性，它將永久地被記錄在區塊鏈上，無法被修改或刪除。 在比特幣區塊鏈中，交易被廣播到網絡並添加到記憶池中。礦工從這個池子中選擇並驗證交易，將它們包含在新的區塊中，以添加到區塊鏈中。該區塊中包含的交易被認為是確認的，但其他礦工仍然有理論上的可能性挖掘出競爭的區塊。 交易的最終性會隨著確認區塊的增加而增加。比特幣交易通常是以額外的六個區塊被附加到交易區塊中而變成"最終"。由於以太坊有比較短的區塊時間，會建議使用較多的確認區塊來確保最終性。 「最長鏈原則」是什麼？ 如之前所說，由於多個礦工可能會在相似時間產生新的有效區塊，這個可能會暫時的產生區塊鏈的臨時分叉。 「最長鏈」原則指的是區塊鏈中有效版本的規則，即投入最多計算工作的版本通常是具有最長區塊鏈的版本。因此，較短鏈上的「有效」區塊，通常被稱為孤立或過時區塊，將被丟棄，其交易將返回至記憶池。 以太坊在先前工作量證明(PoW) 時採用了最長鏈原則。在 2022 年升級至權益證明(PoS) 後，網路採用了更新分叉演算發來衡量鏈的"權重"，即驗證者抵押以太幣加權驗證者投票總和。 什麼導致區塊鏈網絡擁塞？ 區塊鏈網絡擁塞發生在提交到網絡的交易數量超過網絡處理能力的情況下。 區塊鏈網絡可能出現擁擠的原因有幾個： 需求增加 隨著越來越多的人將交易提交到區塊鏈，未確認交易在記憶池中的數量可能超過單個區塊所能包含的範圍。對於具有區塊大小和區塊時間固有限制的區塊鏈來說，這一點尤為重要。 另外交易量增加也可能由於價格突然波動或是大規模採用週期導致。 小區塊大小 每個區塊鏈都有一個區塊大小，它定義了一個區塊的最大尺寸。這個區塊大小限制了一個區塊可以包含多少筆交易。 例如，比特幣最初的設計是將區塊大小限制在 1M 字節。在2017年，比特幣實施了一項名為隔離見證（Segregated Witness）或 SegWit 的升級，以提高交易吞吐量。它將理論上的區塊大小限制增加到約 4M 字節。 如果交易數量超過此限制，將導致網絡擁塞。 產塊時間 產塊時間是指新區塊被添加到區塊鏈的頻率。比特幣大約每10分鐘添加一個新區塊。如果交易的創建速度和量遠高於此，將會出現交易積壓。 網絡擁塞的後果是什麼？ 區塊鏈網絡擁塞可能導致多種負面後果，阻礙網絡順利運作。 交易手續費增加 礦工被激勵優先處理支付較高手續費的交易。因此，當區塊鏈網絡擁擠時，用戶通常需要支付較高的交易手續費，以激勵礦工優先處理他們的交易。這可能使使用區塊鏈比平常更加昂貴，尤其是對於較小的交易。 延遲的交易確認時間 網絡擁塞可能導致交易確認和最終確定的等待時間變長。在極端情況下，交易可能需要數小時、數天甚至更長時間才能確認。這可能會讓用戶體驗不佳。 用戶體驗不佳 高昂的手續費和緩慢的交易確認時間會導致極差的用戶體驗，進而影響區塊鏈的骰用率和可用性。 市場波動 擁塞可能會加劇不確定性並導致市場波動。如果有很多使用者試圖出售加密貨幣，但網絡過於擁塞以至於無法處理這些交易，使用者可能會恐慌並試圖迅速出脫他們的持有。...