買賣股票的最佳時機III | Hard | LeetCode#123. Best Time to Buy and Sell Stock III
前言這題是股票買賣系列的題目: 121. Best Time to Buy and Sell Stock122. Best Time to Buy and Sell Stock II188. Best Time to Buy and Sell Stock IV309. Best Time to Buy and Sell Stock with Cooldown 題目敘述 題目難度：Hard 題目描述： 給定一個整數陣列 prices，prices[i] 代表第 i 天的股票價格，每一天可以選擇買或賣股票，最多只能交易兩次 (買賣兩次)，請找出最大收益。 與先前幾題的原則一樣，只能先買後賣，並且不允許同時有多筆交易，手上股票要賣出才能夠繼續買 解法一開始的想法一開始的想法蠻簡單的，就是與前面幾題一樣，假設 prices=[3,4,5,0,0,3,1,4] 那漲跌幅值如下 1+1 +1 -5 +0 +3 -2 +3 只要有連續漲幅，就加總起來，並加入到 dp 中，因此會是 dp={2,3,3} 只要將 dp 排序後取最後兩個元素相加就會是兩次交易的最大收益...
買賣股票的最佳時機II | Medium | LeetCode#122. Best Time to Buy and Sell Stock II
前言這題是股票買賣系列的題目: 121. Best Time to Buy and Sell Stock123. Best Time to Buy and Sell Stock III309. Best Time to Buy and Sell Stock with Cooldown 題目敘述 題目難度: Medium 題目描述： 給定一個整數陣列 prices，prices[i] 代表第 i 天的股票價格，每一天可以選擇買或賣股票，允許當日買在當日立刻賣出，然而任意時間段最多僅能持有一份股票 解法一開始的想法這題跟 LeetCode-121 Best Time to Buy and Sell Stock 不太一樣的是，這題允許多次交易，所以要求的是， 多筆買賣的總收益要最大化。 假設今天 prices = {7, 1, 5, 3, 6, 4} 則在股價為 1 時買入，隔天為 5 時賣出，此時收益為 4 然後在隔天股價為 3 的時候再度買入，隔天股價為 6 的時候賣出，此時總收益為 4+3 =7 這題會有個特性，就是跨天數的收益，可以拆解！假設 price...
買賣股票的最佳時機 | Easy | LeetCode#121. Best Time to Buy and Sell Stock
前言這題是股票買賣系列的題目，與他類似的題目會是 122. Best Time to Buy and Sell Stock II123. Best Time to Buy and Sell Stock III188. Best Time to Buy and Sell Stock IV309. Best Time to Buy and Sell Stock with Cooldown 題目敘述 題目難度： Easy 題目描述： 給定一個陣列 prices，prices[i] 代表在第 i 天的股票價格。請選一天進買入股票，但在不同天賣出股票 (買賣股票不能在同一天，且須先買股票才能賣股票)，求股票的最大化收益。 解法一開始的想法一開始的想法複雜度其實比較高，就是透過一個迴圈來決定買入，透過另一個內部迴圈決定賣出，然後透過一個變數 maxValue 保存第 i 天買入然後第 j 天賣出的的最大股票收益值。但這樣的做法會導致 time limit excceded! 123456789101112131415class Solution {public: int...
最大正方形 | Medium | LeetCode#221. Maximal Square
題目敘述 題目難度: Medium 題目敘述: 給定一個 m x n 大小的二元陣列 matrix (由 0, 1 填充而成)，請找出僅包含 1 的最大正方形面積。 解法一開始的想法這個問題要找出 僅包含 1 的最大正方形面積 ，可以拆分成兩個問題，第一個就是 如何找出正方形面積? 第二個就是 如何比較出最大的面積? 我最初的想法還是偏向暴力解，如果將矩陣的右下角定為起點，那正方形就會是任意點 (i, j) 往上以及往左圍出的區域 我的解法 - 暴力解1234567891011121314151617181920212223242526272829303132class Solution {public: int maximalSquare(vector<vector<char>>& matrix){ if(matrix.empty() || matrix[0].empty()) return 0; int m = matrix.size(); int n = matrix[...
從排序串鏈移除重複節點 II | Medium | LeetCode#82. Remove Duplicates from Sorted List II
題目敘述 題目難度： Medium 題目描述：給定一個排序鏈結的 head，刪除所有具有重複數字的節點，使原有鏈結最後只剩下相異的數值的節點，並回傳該list的 head 解法一開始的想法由於要檢查是否有數值重複，因此這部分會想到要用 Hash Table 來實現，並且移除重複節點，還需要一個dummy head 搭新的指標來去指向前一個節點。 我的做法123456789101112131415161718192021222324252627282930313233343536373839/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *...
無重複字元的最長字串 | Medium | LeetCode#3. Longest Substring Without Repeating Characters
題目敘述 題目難度: Medium 題目描述：給定一個字串 s，求最長子字串的長度，並且該子字串中不能有重複的字元 解法一開始的想法這題的暴力解就會是透過雙重迴圈來去找各種子字串，然後查找多種不同非重複子字串的長度，然後回傳最長的那個，但在迴圈查找過程中，由於要查找的是輸入資料中的變動長度的字串，因此可以用 sliding window 來解題。其中在確認字元是否重複的過程，則可以用Hash Table 來去儲存和查找。 我的做法1234567891011121314151617181920class Solution {public: int lengthOfLongestSubstring(string s){ if(s.size()==0) return 0; int left=0, right=0; int maxLength = 0; unordered_map<char, int> umap; // Find substrings // Ch...
長度最小的子陣列和 | Medium | LeetCode#209. Minimum Size Subarray Sum
題目敘述 題目難度： Medium 題目描述： 給定一個整數陣列 nums，以及正整數 target，請回傳長度最短的子陣列，其所有元素和大於或等於 target 值。若沒有任何子陣列，則回傳 0 解法一開始的想法這題的關鍵就是要 回傳滿足條件的子陣列 ，因此可以很直覺地聯想到要用 sliding windo來去找出滿足要求的子陣列。 我的做法123456789101112131415161718192021class Solution {public: int minSubArrayLen(int target, vector<int>& nums){ int left=0, right=0; int sum = 0; int length = INT_MAX; while(right < nums.size()){ sum += nums[right]; while( sum >= target){...
編輯距離 | Medium | LeetCode72. Edit Distance
題目敘述 題目難度: Medium 題目敘述: 題目給定兩個字串 word1 和 word2，請回傳 由 word1 轉換成 word2 所需的最少步驟數 ， 步驟有分三種，分別是 1.插入字元 2. 刪除字元 3.取代字元 解法一開始的想法這題我是參考了 neetcode 的前半段影片 解釋題目，才比較有想法 (話說原來這題在兩年前是 HARD..)。其實想法上就是要去比較 word1 和 word2 的所有字元，逐一比較。如果一樣就換下一個，如果不一樣，則需要去比較三個操作何種會有最小的步驟數。 如果是要插入，則步驟數加一，並且接下來需要將 j+1 而 i 不用動，因為 i 還是指向那個不匹配的字元，因此需要看 word2 後續字元是否能夠匹配 如果是刪除，則步驟數加一，並且 j 不動，但要看下一個 word1 字元能否跟當前的 word2[j] 匹配，因此 i+1 如果是取代，則步驟數加一，並且 i 跟 j 都加一，因為取代的話就是字元會相通，就可以換下一組子字元進行比較了 問題可以被 model 成一個二維陣列，代表 word1 對應到 word2 的所需轉換...
最佳股票買賣時機含冷凍期 | Medium | LeetCode#309. Best Time to Buy and Sell Stock with Cooldown
前言121. Best Time to Buy and Sell Stock122. Best Time to Buy and Sell Stock II123. Best Time to Buy and Sell Stock III188. Best Time to Buy and Sell Stock IV 題目敘述 題目難度：Medium 題目描述： 給定一個整數陣列 prices，其中 prices[i] 代表給定股票在第 i 天的價格，請找到你能獲得的最高股票收益，可以買賣股票多次，但是有以下限制： 當你賣出股票後，隔一天為冷卻期，無法進行買賣 在你買股票前，需要把先前持有的股票賣出 (i.e. 你不能夠 第一天買然後第二天也買，要先把第一天的賣掉) 解法一開始的想法這題我後來參考了 NeetCode 的影片，裡面的樹狀圖幫助很大， Decision Tree Recursive + Memoization1234567891011121314151617181920212223242526272829303132class Solution ...
交錯字串 | Medium | LeetCode#97. Interleaving String
題目敘述 題目難度：Medium 題目敘述：給定字串 s1, s2, s3，檢查 s3 是否是由 s1 以及 s2 交錯組合而成 (Interleaving)。 s = s1 + s2 + s3 +... + snt = t1 + t2 + t3 + ... + tn|n-m| <= 1Interleaving: s1+t1+s2+t2+s3+t3+... or t1+s1+t2+s2+t3+s3+... 解法一開始的想法123456789101112131415161718192021222324bool helper(string s3,string s1, string s2, string temp, int start){ if(start > s3.length()) return false; if(start == s3.length()){ return true; } for(int i=start; i<=s3.length();i++){ ...
