#anwendeng
Beats 100%|C++ BFS LCA binary lfting與模指數運算解Leetcode難題3559 Number of Ways to Assign Edge Weights II
- Adjacency-list: array linked Lists
- BFS - construct parent[], level[]
- LCA- binary lifting - distance
- Fast modular power , pow2
在這部影片中，我們將挑戰 LeetCode 的 Hard 難題 3559。我會詳細拆解如何結合 BFS、LCA（最近公共祖先）以及 Binary Lifting（倍增法）來優化路徑查詢，並搭配快速冪運算處理模指數，最終達成 C++ 55ms、擊敗 100% 的極致效能。無論你是要準備面試還是深耕演算法，這部深入的教學都能帶給你啟發。
--------
In this video, we tackle the challenging LeetCode problem 3559 (Hard). I’ll walk you through the full logic of combining BFS, LCA (Lowest Common Ancestor), and Binary Lifting to optimize path queries. We’ll also implement Fast Modular Exponentiation for efficient calculations, achieving a top-tier C++ runtime of 55ms (Beats 100%). Perfect for competitive programming and technical interview prep!
[codes on Leecode 3558. Number of Ways to Assign Edge Weights I]https://leetcode.com/problems/number-of-ways-to-assign-edge-weights-i/solutions/8326730/bfsfast-modular-explinked-list15ms-beats-lpaa/
---00:00 - 實測結果與題意分析 | Submission Result & Problem Overview
02:02 - 成本定義與組合邏輯分析 | Cost Definition & Combinatorics Logic
03:59 - 證明：為何是 2^(d-1) | Proof: Why the answer is 2^(d-1)
05:33 - 範例測資詳解 1 & 2 | Example Walkthrough 1 & 2
06:51 - 約束條件與快速冪運算需求 | Constraints & Fast Modular Exponentiation
08:22 - 五大解題步驟概覽 | 5 Steps to Solve the Problem
08:55 - 使用 Adjacency List 優化效能 | Optimizing with Adjacency List
09:44 - LCA 與 Binary Lifting 核心觀念 | LCA & Binary Lifting Core Concepts
10:44 - Binary Lifting 實作細節 (DP Table) | Implementing Binary Lifting (DP Table)
17:25 - 如何高效計算 LCA (兩次跳躍法) | Efficient LCA Calculation (Two-Jump Method)
21:18 - 利用 LCA 計算兩點間距離 | Calculating Distance between Nodes via LCA
24:03 - 最終答案計算與 BFS 走訪設定 | Final Answer Calculation & BFS Traversal
26:30 - LeetCode 完整程式碼實作演示 | Full C++ Code Implementation on LeetCode
29:10 - 最終結果：55ms Beats 100% | Final Verdict: 55ms Beats 100%
沒有留言:
張貼留言