Range Sum Query 2D - Immutable Difficulty: Medium 題目敘述 求矩陣內一塊矩形範圍的和 傳送門 LeetCode 304 輸入輸出 Leet Code 比較特別，有點像是要你完成一個 Function。 限制 它好像沒給（？） 程式碼: 最近初學 Java ，剛好可以練習一下。 提供 Build: O(nm), Query: O(1) 的解法，這題 Query: O(n) 也可以過。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 public class NumMatrix { private int [][] prefix; public Nu... Read more 01 Mar 2017 - less than 1 minute read
Dijkstra! 傳送門 POJ3268 題目敘述 一群牛（ N 隻牛）要參加派對，他們分別來自 N 個不同的農場（每個農場標記成 ），要去 X 號農場參加派對。農場間共有 M 條單向道路，每條路 需要耗時 的時間。 每隻牛都必須參加派對，因為他們很懶，所以一定要走最短的距離，從自己的農場走到派對農場，然後以最短路徑，再從派對農場走回自己的農場。 假設全部的牛都以上述最優方式走動，花費最多時間的牛要花費多少時間走路？ 輸入格式 第一行 3 個正整數 ，代表有 個農場、 條路、派對辦在 號農場。 接下來有 行，第 行有 三個數字，代表一條路從 到 ，需要耗時 秒。 限制 $$1 \leq N \leq 1000$$ $$1 \leq X \le... Read more 24 Feb 2017 - 2 minute read
Bellman!? 傳送門 POJ3259 題目敘述 有一個農夫的農場莫名奇妙出現了蟲洞，可以把自己傳送到過去時間的某個地方。 給定 F 張圖，每一張圖有 N 個區域（編號 1..N），有 M 條路，是雙向通行的，還有 W 個蟲洞，是單向通行的。 利用道路從一個區域到另一個區域需要耗時，而從蟲洞穿越則會回到過去時間的某個區域。 農夫想要從某個地方出發，遇到過去在起點的自己，請問他能不能成功呢？ 輸入格式 第一行一個正整數 F ，代表有 F 個地圖。接下來有 F 筆測資。 每一筆測資第一行有三個整數: ，分別代表有 N 個區域、 M 條雙向路、 W 個蟲洞。 接下來有 M 行，每行有 三個數字，代表一條路從 S 到 E ，需要耗時 T 秒。 接下來有 W 行，每行也有 三個數... Read more 24 Feb 2017 - 3 minute read
Floyd-Warshall 傳送門 POJ2139 題目敘述 一群牛最近正在做電影，定義一隻牛對於自己的 Degree 是 0 ，一隻牛對於一起做過同一部電影的牛 Degree 是 1 ，若兩隻牛沒有一起工作過，但有另一隻牛分別和這兩隻牛一起工作過，那麼這兩隻沒有一起工作過的牛的 Degree 是 2 。以上情況可以擴展到任意 Degree 。 輸入格式 第一行兩個正整數 ，代表有 N 隻牛（牛的編號從 1..N）、 M 部電影。 接下來有 M行， 每行先有一個整數 n ，代表這行後面有 n 個數字 ，每個數字代表編號 的牛。 限制 $$2 \leq N \leq 300$$ $$1 \leq M \leq 10000$$ 輸出格式 輸出一個整數，代表這群牛裡... Read more 24 Feb 2017 - 1 minute read
Longest Palindromic Substring 傳送門 LeetCode 5 輸入輸出 Leet Code 比較特別，有點像是要你完成一個 Function ，所以下面的 Code 有在解答下，加上輸入出。 限制 它好像沒給（？） 程式碼: 先附上 的解法，之後再補上更好的。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 /* // On Leet C... Read more 20 Feb 2017 - 4 minute read