最後更新日期 2024 / 01 / 01

個人推薦書籍列表

這份清單會持續更新喔 ><

封面 書名 簡介 評價
原子習慣 本書介紹了習慣的強大力量,且提出了多個有別於傳統框架的習慣養成法 從早上起床到夜晚入睡,人類生活中很大部分的一切都受習慣所控制。我從沒想過,習慣竟然強大到是足以改變人的一生。以前我們總是被教導著,養成一個好習慣就是要靠強大的意志力,看完之後才知道,原來那些我們認為意志力很強大的人,往往是最少用到意志力的
六分鐘日記的魔法 以正向心理學、習慣、自我反省等多種理論研究構成,一本通往快樂、更充實人生的日記 待補

推薦文章

很多最短路演算法

每次選擇最近的節點 嘗試透過該節點來更新相鄰節點距離將所有節點距離初始化為 infty 起點為 0 選擇目前距離起點最近的節點 如果目前節點距離加上相鄰節點與目前節點距離小於起點到相鄰節點的距離就更新cppfor int i = 1; i = n; i++ distancei = INF;distancex = 0;q.push{0, x};while q.empty { int a = q.top.second; q.pop; 絕對不會更新到的話直接 continue 掉 if a.first distnow.second continue; for auto u : adja { int b = u.first, w = u.second; if distancea + w distanceb { distanceb = distancea + w; 因為要讓距離小的排在前面所以加負號 q.push{-distanceb, b}; } }}這個演算法是由某個 DP 概念延伸出來的 最初的轉移式大概長這樣定義: dpkij 為 i 到 j 的最短距離,且只能經過額外的 k 個點轉移式: mathrm {dp} i,j,k=mathrm {min} {Big }mathrm {dp} i,j,k-1,mathrm {dp} i,k,k-1+mathrm {dp} k,j,k-1{Big }依照 DP 轉移式枚舉每個點做轉移就好了 實作上由於 k 是按照順序轉移的所以可以把空間壓到二維 記得要注意迴圈是由外而內順序是 k、i、j cppfor int k = 1; k = n; k++ { for int i = 1; i = n; i++ { for int j = 1; j = n; j++ { distij = mindistij, distik + distkj; } }}如果不小心忘記寫成 i j k 的話只要做三次就會對了 2019 年的某篇論文上提到了這點如果任一個 distii 0 若且唯若存在負環 代表有一個點自己繞一圈回到自己距離小於 0 但如果是無向圖的話的負環就很難判斷了對於每個邊嘗試更新連接的兩個點對於起點的距離重複 n-1 次嘗試更新所有的邊cppfor int i = 1; i = n; i++ disti = INF; distx = 0; for int i = 1; i = n-1; i++ { for auto e : edges { int a, b, w; tiea, b, w = e; distb = mindistb, dista + w; } }}如果更新了 n-1 次還能繼續更新 代表這張圖存在負環看完這些之後 想必一定有人會覺得「為什麼要學這麼多種最短路演算法」 原因很簡單,因為這些演算法各自有不同的特性與效率 所以需要適時挑選適合的演算法來使用不過比較值得注意的是 事實上如果要求多源最短路的話 枚舉每個點做 Dijkstra 甚至比 Floyd-Warshall 還快| | Bellman-Ford | Dijkstra | Floyd-Warshall || --- | --- | --- | --- || 類型 | 單點源 | 單點源 | 全點對 || 限制 | 任意圖 | 無負邊 | 任意圖 || 時間複雜度 | OVE | OE log E | OV^3 || 用途 | 檢查負環 | 快速單點源 | 負邊全點對 |

Algorithms

圖論入門

首先 我們要先來了解什麼是圖簡單來說 圖 Graph 就是由多個節點 Node 並透過邊 Edge 連結成的我們像是下面的示意圖在知道圖是什麼之後 我們要來看的是如何在 C++ 中儲存一張圖在大部分的情況下 我們會以節點關係來儲存一張圖像是上面那張圖片的範例 我們知道節點 1 會連接到節點 2 跟 3 節點 2 會連接到節點 1 跟 3 節點 3 會連接到節點 2 跟 4 節點 4 會連接到節點 3 跟 5 節點 5 會連接到節點 4 也就是說 我們實際上要存的資料大概長這樣:1 - 2, 32 - 1, 33 - 2, 44 - 3, 55 - 4C++ 內可以使用傳統陣列套 vector 來實現cpp MAXN 最大節點數量vectorint graphMAXN; 下面的操作就是相當於我們從節點 1 建立了兩條邊分別指向 2 跟 3graph1.pushback2;graph1.pushback3;在很多的情境下 我們會需要拜訪整張圖上面的所有節點來得知一些資訊這邊會簡單的介紹一下 DFS 深度優先搜尋 演算法的作法 這個演算法就是利用遞迴的特性遍歷整張圖這個演算法會儘可能深的搜尋圖的分支 當節點的所有邊都已經被搜尋過 則會回溯到上個節點 這個過程會一直重複到搜尋完整張圖為止程式碼應該不難理解 直截來看看吧:cppvectorint graphMAXN; 存圖bool visMAXN; 紀錄哪些節點拜訪過void dfsint v { 枚舉每一個 v 可以走到的節點 for int u : graphv { 如果走過就略過 if visu continue; 標記為走過 visu = true; 造放進節點 u dfsu; }}樹其實就是圖的一種 有一些特性:- 不存在環- 每個節點均可以走到其他每個節點- 若有 n 個節點,邊就是 n-1 條這邊先補充一下 環就是指像是最上面的示意圖 1 - 2 - 3 那部分的結構然後樹的其他部分都跟圖差不多 不過 DFS 可以寫的比圖簡單cppvoid dfsint v, int p { 枚舉每一個 v 可以走到的節點 for int u : graphv { 不能走回上個節點 if u == p continue; 造放進節點 u dfsu, v; }}這裡是一些簡單的練習題:- CSES Building Roads- CSES Message Route或者你也可以在這邊了解一些更進階的內容:- 最短路演算法

Algorithms

C++ 常見 STL 教學

pair 是一種可以儲存兩個元素的資料結構通常用來儲存二維座標或者是陣列的 index 與 value 而且常數較小 如果用 array vector 替代有些題目真的會被卡 TLEcpp 宣告一個第一個欄位為 1 第二個欄位為 5 的 pair 在一些 c++ 版本較舊的環境下要使用 makepair1, 5pairint, int pos = {1, 5}; 取得第一個欄位的值cout pos.first endl; 取得第二個欄位的值cout pos.second endl; 將 pos 的第一個欄位的 1 改成 2pos.first = 2; 將 pos 的第二個欄位的 5 改成 4pos.second = 4;在比較兩個 pair 時會先比第一個元素 如果第一個元素相同才會比第二個元素跟傳統陣列差不多 不過長度是可變的 會因為加入更多元素讓 vector 變得更長不用多說了吧 就是可以像陣列一樣儲存 n 個元素cpp 直接宣告 vector 的方式vectorint v1; 宣告長度為 n 的 vectorvectorint v2n; 宣告長度為 n 且每個元素都是 5 的 vectorvectorint v3n, 5; 宣告一個有元素 {1, 2, 3, 4} 的 vectorvectorint v4 = {1, 2, 3, 4} 宣告一個跟其他 vector 一樣的 vector 複製vectorint v5v4; 加入元素在尾端v1.pushback7; 從尾端移除元素v1.popback; 存取 vector 中的某一項cout v42 endl; 取得大小cout v2.size endl;從第一個元素開始比較 如果相同就繼續往後比 直到第一個不同為止像是一個排隊的隊伍 可以從一端進入 從另一端離開 也就是先進去的會先離開大部分情況用來實作一些較複雜的演算法 比如 BFS、拓撲排序等等cpp 宣告一個 queuequeueint q; 將元素 5 推入 queue 後端q.push5; 取得 queue 前端的元素cout q.front endl; 取得 queue 後端的元素cout q.back endl; 將隊伍前端的元素彈出移除q.pop; 檢查 queue 是否為空if q.empty { cout "empty" endl;} 取得 queue 的大小cout q.size endl;類似於一疊盤子 最後放上去的盤子會最先被取走 而你不能從中間拿走盤子 也就是說後進去的會先出去stack 常用來會處理一些匹配類問題 或者是模擬遞迴 更進階一點還有單調堆疊之類的玩法cpp 宣告一個 stackstackint stk; 將元素 3 推入 stackstk.push3; 從 stack 頂端取出元素cout stk.top endl; 將 stack 頂端的元素彈出移除stk.pop; 檢查 stack 是否為空if stk.empty { cout "empty" endl;} 取得 stack 的大小cout stk.size endl;就是集合的意思 用來儲存不重複的元素 並會按照元素的大小自動排序主要用於快速插入和查找元素cpp 宣告一個 setsetint st; 插入元素st.insert5;st.insert3;st.insert7; 檢查 set 是否包含某元素if st.find3 = st.end { cout "set contains 3" endl;} else { cout "set does not contain 3" endl;} 刪除元素st.erase5; 遍歷 set 中的元素for int e : st { cout e " ";} 取得 set 的大小cout st.size endl; 取得 set 的第一項 因為回傳的是 iterator 所以要加 cout st.begin endl; 取得 set 的最後一項 由於 back 是開區間所以要 -1cout --st.end endl;語法根陣列有點像 不過可以接受整數以外的型態來當作索引值有些時候需要使用負數、非常大的數字、字串等等來當索引值 map 就會是一個很方便的工具cpp 宣告一個以 string 為索引,int 為值的 mapmapstring, int mp; 把字串對應到數字mp"one" = 1;mp"two" = 2;mp"three" = 3; 輸出 one 的值cout mp"one" endl; 在 map 中刪除 onemp.erase"one"; 遍歷 mapfor auto key, value : mp { cout key ", " value endl;} 取得 map 的大小cout mp.size endl;又稱為 heap 可以支援快速地插入及查詢最大最小值很常使用在一些複雜的演算法內 比如最短路徑、最小生成樹等等cpp 宣告一個 priority queuepriorityqueueint pq; 宣告一個 priority queue 並且頂部為最小值priorityqueueint, vectorint, greaterint pq; 插入元素pq.push3;pq.push1;pq.push5; 取得頂端的元素最大值cout pq.top endl; 移除頂端的元素pq.pop; 檢查 priority queue 是否為空if pq.empty { cout "empty" endl;} 取得 priority queue 的大小cout pq.size endl;

Algorithms