題目： LeetCode - 230. Kth Smallest Element in a BST 題目說明給一個 Binary Search Tree 及一個整數 k，求 Tree 中第 k 小的值。 解題思路使用遞迴將值推入 v，由於是 BST，所以先將左子樹推入，再推入自己的值，最後推入右子樹，這樣 v 裡面就是由小到大排序了，最後回傳 v[k - 1] 即可。 參考解法12345678910111213141516171819202122232425// fast IOstatic auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0;}();class Solution {public: void putsIn(TreeNode* root) { if(!root) return; ...

題目： LeetCode - 901. Online Stock Span 題目說明設計一個 Class，負責收集每日股票的價格及跨度 ( 從今天開始往前數前面有幾天比今天的價格低 )。 解題思路解法一： 動態規劃，dp[i] 代表第 i 天時前面有連續幾天比今天的價格低。當每次呼叫 next() 時，j = i - 1 表示前一天的價格，若是 prices[i - 1] <= price，就將 j 減去 dp[j]，表示前面有多少天的價格小於今天的價格，重複執行直到 j < 0 或是 price < prices[j]，最後 i - j + 1 即是今天價格的跨度，最後將跨度推入 dp 及價格推入 prices 即可。 解法二： 解法二其實是解法一的濃縮，我們可以發現，當 dp[i] 的數值確定後，前面幾天的資料其實就不需要了，所以我們可以使用 Stack，當每次呼叫 next() 時，若是 top() 的價格小於等於今天的價格，就將跨度加到今天，然後 pop() 掉，最後再將今天的價格及跨度推入即可。 參考解法解法一： 12345678910111213141 ...

題目： LeetCode - 567. Permutation in String 題目說明給兩個 String s1、s2，求 s2 中是否有某段文字結構組成和 s1 相同。 解題思路建兩個表，v1 放 s1 中的英文字母個數，v2 放 s2 某段的英文字母個數。使用一個迴圈遍歷 s2，將遍歷到的元素加入 v2，當裡面存放的字母個數超過 s2 的長度時，需要把最前面的刪除。最後判斷 v2 是否等於 v1 即可。 參考解法1234567891011121314151617181920212223242526// fast IOstatic auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0;}();class Solution {public: bool checkInclusion(string s1, string s2) { ...

題目： LeetCode - 438. Find All Anagrams in a String 題目說明給兩個 String s、p，求 s 中某段文字結構組成和 p 相同的 index。 解題思路建兩個表，vp 放 p 中的英文字母個數，vs 放 s 某段的英文字母個數。使用一個迴圈遍歷 s，將遍歷到的元素加入 vs，當裡面存放的字母個數超過 p 的長度時，需要把最前面的刪除。最後判斷 vs 是否等於 vp 即可。 參考解法123456789101112131415161718class Solution {public: vector<int> findAnagrams(string s, string p) { int ls = s.size(), lp = p.size(); vector<int> vs(26), vp(26), res; for(auto c : p) ++vp[c - 'a']; for(int i ...

題目： LeetCode - 328. Odd Even Linked List 題目說明給一個 Linked List，題目要求將奇數的 node 往前放，偶數的 node 往後放。 解題思路將原本的第一個節點當作奇數 node 的頭，第二個節點當作偶數 node 的頭，將奇數與偶數各自串起，最後將偶數 node 的頭接在奇數最後一個 node 後面即可。 參考解法12345678910111213141516class Solution {public: ListNode* oddEvenList(ListNode* head) { if (!head || !head->next) return head; auto odd = head, even = head->next, evenhead = even; while(even && even->next) { odd->next = odd-& ...

題目： LeetCode - 918. Maximum Sum Circular Subarray 題目說明給一個陣列，求此陣列的最大子陣列和。( 可以循環 ) 解題思路 想法： 最大子陣列和可能會有兩種情況，一種是沒有跨過頭尾，就是單純的最大子陣列和。另一種是有跨過頭尾，這時的和就是 陣列和 - 最小子陣列和。 作法： 使用一個迴圈得到最大子陣列和及最小子陣列和，最後比對 sum - mn 及 max 何者較大即可。需要注意的是，若是最小值 mn 和 sum 相等，代表整個陣列都是負的，這時需要直接回傳 max。 參考解法1234567891011121314151617181920212223// fast IOstatic auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0;}();class Solution {public: int max ...

題目： LeetCode - 1526. Minimum Number of Increments on Subarrays to Form a Target Array 題目說明給一個陣列 target，求一個同等大小，元素值為 0 的陣列，建成 target 那樣需要建造幾層。 解題思路想像成是在爬山，只有在走上坡的時候才需要建造，走下坡時因為上坡已經建過了所以就不用再建。 參考解法123456789101112131415161718192021// fast IOstatic auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0;}();class Solution {public: int minNumberOperations(vector<int>& target) { int res = 0, pr ...

題目： LeetCode - 208. Implement Trie (Prefix Tree) 題目說明建立一個 Prefix 字典樹 ( Trie )，並且完成某些功能。 解題思路定義一個 class node 作為節點，裡面包含 node *child[26] 代表 26 個字母，isWord 代表走到這個 node 時是否形成一個單字。 insert(string word)： 定義一個 ptr，一開始指向 root，之後遍歷 word，逐一檢查對應的 child 是否存在，若不存在就新建。全部做完後 ptr 這時會指向最後一個字母的 node，再將 ptr->isWord 設為 True 即可。 search(string word)： 和 insert() 類似，只是當 child 不存在時就回傳 False。全部做完後，若 ptr->isWord 為 True 代表這個字串有被 insert() 進來，回傳 True，反之回傳 False。 startsWith(string prefix)： 和 search() 一模一樣，只是最後不需檢查 ...

題目： LeetCode - 402. Remove K Digits 題目說明給一個字串及一個整數 k，字串代表一個整數，求刪除 k 個數字後，結果是最小的數字。 解題思路 想法： 由於數字比大小是從高位往低位比，所以我們的目的是讓高位數盡可能的小。 解法一： 定義一個字串 res，遍歷 num，若是 res 的最後一位數比現在遍歷到的元素大，就刪除最後一位數，直到已經刪除了 k 個數字，或是 res 已經刪除光了。最後再 res.resize(digits)，因為我們只需要 digits 位數，而後面的數字一定會比前面的大，所以直接刪除掉後面的數字。最後如果 res 前面是 0 的話就把 0 拿掉即可。 解法二： 和解法一類似，只是在放入的時候就判斷是否有 leading zero 的情況。 解法三： 和解法二相同，只是不再定義新的字串，而是將直接將結果存在 num 裡面。 參考解法解法一： 123456789101112131415161718192021class Solution {public: string removeKdigits(str ...

題目： LeetCode - 540. Single Element in a Sorted Array 題目說明給一個排序好的陣列，裡面只有一個值是單一存在的，其餘都兩兩成對，求單一存在的值為何？ ※ 題目希望時間複雜度為 O(log n) 解題思路觀察規則，使用二元搜尋法即可。 參考解法1234567891011121314151617181920212223class Solution {public: int singleNonDuplicate(vector<int>& nums) { int begin = 0, end = nums.size(), mid; while(end - begin != 1) { mid = (begin + end) / 2; if(nums[mid - 1] != nums[mid] && nums[mid] != nums[mid + 1]) ...