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 …

題目： — Minimum Adjacent Swaps to Reach the Kth Smallest Number - LeetCode You are given a string num, representing a large integer, and an integer k. We call some integer wonderful if it is a…leetcode.com 我自己因為想這題想了很久，所以還是忍不住去看 hint 了。。。羞愧之餘，順手將解答給記錄下來。 解這題前，首先需要會 Next Permutation ，會了之後就會變得相當簡單了。 我的解答： class Solution { public: void swap(char &a, char &b) { char t; t = a; a = b …

題目： Find Greatest Common Divisor of Array - LeetCode Given an integer array nums, return the greatest common divisor of the smallest number and largest number in nums. The…leetcode.com 我的解法： 這題固然簡單，但我常常會忘記 GCD 該怎麼寫。。。所以將我的推導記錄下來，以增強我那少的可憐的記憶力。 一邊寫一邊感慨自己的基礎數論差的可憐，通通都忘光光了。要是數學實力還停留在高中程度的話，就方便多了。 int gcd(int a, int b) { if(b == 0) { return a; …