Problems LeetCode : 785. Is Graph Bipartite? [BFS] LeetCode : 207. Course Schedule [topological sort] LeetCode : 210. Course Schedule II [topological sort] LeetCode : 269. Alien Dictionary [topological sort] LeetCode : 778. Swim in Rising Water [BFS][priority queue] LeetCode : 1192. Critical Connections in a Network [Articulation Bridge] LeetCode …

Hello! 本篇延續了上一篇的內容。 本篇主要是參考 ( 抄襲 ) 這個大神的筆記。 假如看到內容有錯誤的話，再麻煩跟我說一聲了~ Binary Indexed Tree ( BIT ) 單點修改 建構 BIT 前綴和查詢 例題：leetcode 307 Range Sum Query — Mutable ( 單點修改，查詢區間和 ) BIT + 差分序列 BIT + 差分序列：O( logN ) 區間修改 BIT + …

Hello! 本篇延續了上一篇的內容。 本篇主要是參考 ( 抄襲 ) 這個大神的筆記。 假如看到內容有錯誤的話，再麻煩跟我說一聲了~ 線段樹 ( Segment Tree ) 線段樹建構 單點修改 區間查詢 例題 — Leetcode 307 （ 單點修改，區間查詢 ） 懶人標記：建構線段樹 懶人標記：區間修改 懶人標記：區間查詢 懶人標記：例題 — zeroJudge d799 動態開點 動態開點：例題 …

Hello! 本篇延續了上一篇的內容。 本篇主要是參考 ( 抄襲 ) 這個大神的筆記。 假如看到內容有錯誤的話，再麻煩跟我說一聲了~ 稀疏表 ( sparse table) 在前綴和中，我們可以在 O(1) 的時間找出某個區間的和，那現在我們想要找的是某個區間的最大值或最小值該怎麼辦呢？ 剛剛我們看過了分塊法，會將一個長陣列分成一個個長度為 sqrt(n) 的區塊。最後可以得到 O(n * sqrt(n)) 的 …

Hello! 最近開始看些資料結構與演算法的東西，驚覺自己的實力竟然比高中生還差勁。雖然已經從研究所畢業工作一段時間了，但我的實力仍舊停留在別人國，高中程度（甚至不如國，高中程度）。希望可以在工作之餘，盡量彌補一些知識了。 本篇主要是參考 ( 抄襲 ) 這個大神的筆記。 假如看到內容有錯誤的話，再麻煩跟我說一聲了~ 前綴和 輸入一個長度為 n 的陣列，以及一個數字 q ， …

題目： Contiguous Array - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared…leetcode.com 這一題是最近寫的題目裡，比較有成就感的一題了，因為沒有看解答，就想出自己還算滿意的解。 我的解法： 每次多算一個數時，計算 1 的總和以及 0 的總和，並將其相減得 diff。假如 diff == 0 ， 則可以把這個長度計入計算。假如不是 0 ， 則用 hashMap 記起得此值的 index 。 此後假如有遇到相同的 diff 值，表示在這個區 …

題目： — Valid Triangle Number - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared…leetcode.com 我的解法： Time : O(N²logN) /* 1. sort 2. 遍尋前兩數，用二分搜找最後一數 */ class Solution { public: int triangleNumber(vector<int>& nums) { if(nums.size() < 3) { return 0; …

題目： LRU Cache - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared…leetcode.com 這一題在一年前就已經寫出來了，但是一年前的 Code 使用最新的測資卻會 LTE ， 於是一年後再來寫寫看這一題，希望這一年以來，我能有一些些的長進。 然而一年以後，仍舊無法把 get 以及 put 壓到 O(1)，僅僅是從原本的 O(N log (capacity)) 優化到了 O(log(capacity))，看來還是太嫩了 (´・ω・`) 以前的解法： 時間複 …

題目： Count Complete Tree Nodes - LeetCode Given the root of a complete binary tree, return the number of the nodes in the tree. According to , every level…leetcode.com 這個問題很好的演示了，該怎麼把一個問題拆解成多個步驟，並將一個個步驟好好地實做出來。 我的解法： 時間複雜度： O(N + E) 空間複雜度： O(1) N 為節點個數， E 為邊的個數 這題如果只是單純解題的話，是個很簡單的一題，任何的 Tree Traversal 都可以解掉，但是題目的敘述有說，時間複雜度必須要低於 O(N)。 class Solutio …