预购商品
书目分类
特别推荐
本書旨在探討如何優化算法效率,詳細闡述了經典算法和特殊算法的實現、應用技巧和復雜度驗證過程,內容由淺入深,能幫助讀者快速掌握復雜度適當、正確率高的高效編程方法以及自檢、自測技巧,是參加ACM/ICPC、Google Code Jam等國際編程競賽、備戰編程考試、提高編程效率、優化編程方法的參考書目。
第1章 引言 1 1.1 程式設計競賽 1 1.1.1 線上學習網站 3 1.1.2 線上裁判的返回值 4 1.2 我們的選擇:Python 5 1.3 輸入輸出 6 1.3.1 讀取標準輸入 6 1.3.2 顯示格式 9 1.4 複雜度 9 1.5 抽象類別型和基本資料結構 11 1.5.1 棧 11 1.5.2 字典 12 1.5.3 佇列 12 1.5.4 優先順序佇列和最小堆 13 1.5.5 並查集 16 1.6 技術 18 1.6.1 比較 18 1.6.2 排序 18 1.6.3 掃描 19 1.6.4 貪婪演算法 20 1.6.5 動態規劃演算法 20 1.6.6 用整數編碼集合 21 1.6.7 二分查找 23 1.7 建議 25 1.8 走得更遠 27 第2章 字串 28 2.1 易位構詞 28 2.2 T9:9 個按鍵上的文字 29 2.3 使用字典樹進行拼寫糾正 31 2.4 KMP(Knuth-Morris-Pratt)模式匹配演算法 33 2.5 最大邊的KMP 演算法 35 2.6 字串的冪 38 2.7 模式匹配演算法:Rabin–Karp 演算法 38 2.8 字串的最長回文子串:Manacher 演算法 42 第3章 序列 44 3.1 網格中的最短路徑 44 3.2 編輯距離(列文斯登距離) 45 3.3 最長公共子序列 47 3.4 昇冪最長子序列 49 3.5 兩位玩家遊戲中的必勝策略 52 第4章 陣列 53 4.1 合併已排序列表 53 4.2 區間的總和 54 4.3 區間內的重複內容 54 4.4 區間的最大總和 55 4.5 查詢區間中的最小值:線段樹 55 4.6 計算區間的總和:樹狀陣列(Fenwick 樹) 57 4.7 有k 個獨立元素的視窗 59 第5章 區間 61 5.1 區間樹(線段樹) 61 5.2 區間的並集 64 5.3 區間的覆蓋 64 第6章 圖 66 6.1 使用Python 對圖編碼 66 6.2 使用C++ 或Java 對圖編碼 67 6.3 隱式圖 68 6.4 深度優先遍歷:深度優先演算法 69 6.5 廣度優先遍歷:廣度優先演算法 70 6.6 連通分量 71 6.7 雙連通分量 74 6.8 拓撲排序 77 6.9 強連通分量 79 6.10 可滿足性 84 第7章 圖中的環 86 7.1 歐拉路徑 86 7.2 中國郵差問題 88 7.3 最小長度上的比率權重環:Karp 演算法 89 7.4 單位時間成本最小比率環 92 7.5 旅行推銷員問題 93 第8章 最短路徑 94 8.1 組合的屬性 94 8.2 權重為0 或1 的圖 96 8.3 權重為正值或空值的圖: Dijkstra 演算法 97 8.4 隨機權重的圖:Bellman-Ford 演算法 100 8.5 所有源點- 目標頂點對:Floyd-Warshall 演算法 101 8.6 網格 102 8.7 變種問題 104 8.7.1 無權重圖 104 8.7.2 有向無環圖 104 8.7.3 最長路徑 104 8.7.4 樹中的最長路徑 104 8.7.5 最小化弧上權重的路徑 105 8.7.6 頂點有權重的圖 105 8.7.7 令頂點上最大權重最小的路徑 105 8.7.8 所有邊都屬於一條最短路徑 105 第9章 耦合性和流 106 9.1 二分圖最大匹配 107 9.2 最大權重的完美匹配: Kuhn-Munkres 演算法 110 9.3 無交叉平面匹配 116 9.4 穩定的婚姻:Gale-Shapley 演算法 117 9.5 Ford-Fulkerson 最大流演算法 119 9.6 Edmonds-Karp 演算法的最大流 121 9.7 Dinic 最大流演算法 122 9.8 s-t 最小割 125 9.9 平面圖的s-t 最小割 126 9.10 運輸問題 127 9.11 在流和匹配之間化簡 127 9.12 偏序的寬度:Dilworth 演算法 129 第10章 樹 132 10.1 哈夫曼編碼 133 10.2 最近的共同祖先 135 10.3 樹中的最長路徑 138 10.4 最小權重生成樹:Kruskal 演算法 140 第11章 集合 142 11.1 背包問題 142 11.2 找零問題 143 11.3 給定總和值的子集 145 11.4 k 個整數之和 146 第12章 點和多邊形 148 12.1 凸包問題 149 12.2 多邊形的測量 150 12.3 最近點對 151 12.4 簡單直線多邊形 153 第13章 長方形 156 13.1 組成長方形 156 13.2 網格中的最大正方形 157 13.3 長條圖中的最大長方形 158 13.4 網格中的最大長方形 159 13.5 合併長方形 160 13.6 不相交長方形的合併 164 第14章 計算 165 14.1 最大公約數 165 14.2 貝祖等式 165 14.3 二項式係數 166 14.4 快速求冪 167 14.5 素數 167 14.6 計算算數運算式 168 14.7 線性方程組 170 14.8 矩陣序列相乘 174 第15章 窮舉 176 15.1 鐳射路徑 176 15.2 精確覆蓋 179 15.3 數獨 184 15.4 排列枚舉 186 15.5 正確計算 188 調試工具 191 參考文獻 192
Christoph Dürr,法國國家科學研究院研究員,巴黎皮埃爾-瑪麗·居裡大學博士生導師,Operation Research科研組研究主任。 Jill-Jênn Vie,法國高等電力學院博士、算法講師,擔任法國高等師範學院Paris-Saclay團隊在ACM競賽中的演算法導師;曾任法國國際程式設計大賽Prologin主席,並于2014年獲Google RISE Award。
客服公告
热门活动
订阅电子报