LeetCode 64. 最小路徑和 - 動態規劃經典網格路徑
題目 給定 m×n 非負整數網格,從左上角到右下角,每步只能向右或向下,求路徑上數字和的最小值。 DP 狀態與轉移 dp[i][j] = 從 (0,0) 到
LeetCode 1. Two Sum - 哈希表單次遍歷 O(n) 解法
題目 給定整數數組 nums 和目標值 target,找出兩數下標使其和等於 target。假設恰好有一解,不可重複使用同一元素。返回下標(0-based)。
二分查找優化插入排序:遞歸實現二分定位插入位置
背景 插入排序中,將當前元素插入已排序前綴時,線性查找位置為 O(n),改用二分查找可降為 O(log n)(雖整體仍 O(n^2) 因移動元素)。本文採用遞歸
匈牙利算法入門與 HNOI 2006 超級英雄題解
匈牙利算法核心思想 求二分圖最大匹配。將頂點分為左右兩部(U、V)。從左部每個未匹配點出發,DFS 尋找增廣路:交替出現的「非匹配邊、匹配邊」路徑,兩端點均未匹
棋盤覆蓋問題:分治法遞歸鋪設 L 型骨牌
問題描述 在 2^k × 2^k 棋盤中,恰有一格為特殊方格(已佔用)。用 4 種旋轉形態的 L 型骨牌(佔 3 格)覆蓋其餘所有格,骨牌不重疊。輸出鋪設方案(
LeetCode 92. 反轉鏈表 II - 一次遍歷原地反轉區間
題目要求 給定單鏈表頭節點,反轉位置 m 到 n 的節點(1-indexed)。要求原地、一次遍歷完成。1 ≤ m ≤ n ≤ 鏈表長度。 例:1→2→3→4→
BZOJ 4455 小星星 - 樹形 DP + 容斥原理 完整題解
題目大意 給定一個 n 點無向圖 G 和一棵 n 點樹 T(n ≤ 17)。求將 T 的節點一一映射到 G 的節點的方案數,使得 T 中每條邊對應的 G 中兩點
大整數乘法:分治法(Karatsuba 風格)C++ 實現詳解
問題描述 輸入兩個大整數(可含負號),用數組存儲每一位,採用分治策略計算乘積並輸出。 分治思想 設兩數 X、Y 位數為 n(補齊為 2 的冪次)。分為高低兩半
Gym 100703G Game of Numbers - 動態規劃求最長合法操作序列
題目大意 公主寫下一個數列 c[1..n],初始結果為 0。騎士依次對每個數選擇「+」或「-」,加到或減去當前結果。要求過程中結果始終在 [0, k] 範圍內。
Tarjan 算法詳解:強連通分量與 CodeVS 1332 實戰
什麼是強連通分量(SCC)? 在有向圖中,若兩頂點 u、v 互相可達,則稱它們強連通。極大強連通子圖即為強連通分量。Tarjan 算法基於 DFS,線性時間 O
LeetCode 104. 二叉樹的最大深度 - 遞歸與迭代解法詳解
題目描述 給定一棵二叉樹,找出其最大深度。最大深度是指從根節點到最遠葉子節點的最長路徑上的節點數。 遞歸解法(DFS) 最直觀的方法:一棵樹的最大深度 = m
POJ 1703 Find them, Catch them - 並查集與關係追蹤經典題解
題目背景 塔杜城警方決定徹底消滅城裡的兩大幫派:龍幫與蛇幫。但警方首先需要確認兩名罪犯是否屬於同一幫派。給定 N (N ≤ 10^5) 名罪犯(編號 1 到 N
Linux 下 VS Code 編譯調試 C++ 專案完整指南:從 gcc/g++ 到 Makefile 再到 launch.json/tasks.json
Linux 下 VS Code 編譯調試 C++ 專案完整指南 在 Linux 環境開發 C++ 專案時,掌握 gcc/g++ 編譯鏈接流程、Makefile
POJ 1611 The Suspects:並查集統計傳染鏈規模
POJ 1611 The Suspects:並查集統計傳染鏈規模 POJ 1611「The Suspects」以 2003 年 SARS 疫情為背景:學生分組活
POJ 2236 Wireless Network:並查集解決動態連通性問題
POJ 2236 Wireless Network:並查集解決動態連通性問題 在 POJ 2236「Wireless Network」這道經典題目中,我們面臨一
HDU 1856 More is better:並查集求最大朋友圈
HDU 1856 More is better:並查集求最大朋友圈 題目大意 有 107 個男孩(編號 1~107),給定 n 對直接好友關係(n ≤ 105
HDU 5884 Sort:K 叉哈夫曼樹與二分查找優化合併成本
HDU 5884 Sort:K 叉哈夫曼樹與二分查找優化合併成本 題目背景 給定 N 個已排序序列,長度分別為 ai。每次可合併至多 k 個序列,成本為其長度