無重複字元的最長字串 | 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++){ ...
最長迴文子字串 | Medium | LeetCode#5. Longest Palindromic Substring
題目敘述 題目難度: Medium 題目描述：給定一個字串 s，求出其最長的迴文子字串 babadsscca 最長回文子字串會是 bab 或 aba 解法一開始的想法一開始想法一樣比較暴力，一樣會是想先找出遞迴關係式，首先應該會分成兩個函數處理，一個負責遞迴的邏輯，另一個用於確認是否為回文，遞迴邏輯會先透過迴圈來去切出不同範圍的子字串，子字串丟到函數檢查是否為回文，如果是那就檢查是否是最長的子字串，如果是，那就丟給原本的函數遞迴檢查下去 Recursive1234567891011121314151617181920212223242526272829class Solution {public: bool checkPalindrome(string subStr){ string tempStr = subStr; reverse(tempStr.begin(), tempStr.end()); if(tempStr == subStr) return true; else return...
特殊路徑II | Medium | LeetCode#63. Unique Paths II
題目敘述 題目難度: Medium 題目描述： 給定一個 m x n 大小的整數2D陣列 grid，有個機器人為位在網格最左上角 (grid[0][0])，機器人想要移動到最右下角 (grid[m-1][n-1])。機器人每次可以選擇往下或是往右邊移動。網格中某些格子有障礙物，有障礙物的那格會被標注 1，如果沒有障礙物則是標注 0，機器人移動的路線中不能包含任何障礙物。 題目要求回傳機器人可以走的所有唯一的路徑數量。 解法一開始的想法一開始的想法一樣還是要找子問題，從左上角起點每次可以選擇往右或往下，而終點會是陣列中 [m-1][n-1] 的位置，最短路徑和可以從終點加上他的上面或左邊那格一路回朔回起點， 因此這會是一個大量重疊的子問題，因此可以用 DP 中的 Recursion + Memoization 來解決。 我的解法 - Recursion + Memoization12345678910111213141516171819202122232425262728class Solution {public: vector<vector<i...
複製有 Random 指標的鏈結串列 | Medium | LeetCode#138. Copy List with Random Pointer
題目敘述 題目難度：Medium 題目描述： 給定長度為 n 的 Linked List，每個節點都有一個額外的指標 random，可以指向相同list中的任意節點，以及 NULL，題目要求建立這個 List 的 Deep Copy 以下是節錄自維基百科對於 Deep Copy 的定義Deep copy involves copying the state of all subordinate objects – recursively dereferencing object references at each level of the tree that is the state of the original object and creating new objects and copying fields. A modification of either the original or copied object, including their inner objects, does not affect the other since they share...
最短路徑總和 | Medium | LeetCode#64. Minimum Path Sum
前言 這是第一次寫 Multidimensional DP 的時間小於 20 min 就 AC !! 值得紀念一下 ~ 題目敘述 題目難度：Medium 題目描述： 題目給了一個 m x n 大小的二維整數陣列 grid，陣列中的值為非零整數，請找到從網格左上角走到右下角的最小路徑和， 在每一格每次只能選擇往下或是往右邊走 解法一開始的想法一開始的想法一樣還是要找子問題，從左上角起點每次可以選擇往右或往下，而終點會是陣列中 [m-1][n-1] 的位置，最短路徑和可以從終點加上他的上面或左邊那格一路回朔回起點， 因此這會是一個大量重疊的子問題，因此可以用 DP 中的 Recursion + Memoization 來解決。 我的解法 - Recursion + Memoization1234567891011121314151617181920class Solution {public: vector<vector<int>> dp; int helper(vector<vector<int>>&...
旋轉鏈結串列 | Medium | LeetCode#61. Rotate List
題目敘述 題目難度：Medium 題目描述： 給定一個 Linked List 的 head，選轉整個 List k 次後回傳新的List head 解法一開始的想法 看題目給的範例測資，可以知道所謂旋轉就是尾端的 node 插入到 List 前端作為新的 head，而這個操作要進行 k 次，一開始的想法就是很直觀， 找到尾端節點，插入到首端，然後遞迴操作 先前的解法123456789101112131415161718192021222324252627282930313233/** * 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 *next...
