Kevin Liu's 部落格 || Technical || Travel

前言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 ...

題目敘述 題目難度: Medium 題目描述：給定一個字串 s，求出其最長的迴文子字串 babadsscca 最長回文子字串會是 bab 或 aba 解法一開始的想法一開始想法一樣比較暴力，一樣會是想先找出遞迴關係式，首先應該會分成兩個函數處理，一個負責遞迴的邏輯，另一個用於確認是否為回文，遞迴邏輯會先透過迴圈來去切出不同範圍的子字串，子字串丟到函數檢查是否為回文，如果是那就檢查是否是最長的子字串，如果是，那就丟給原本的函數遞迴檢查下去 Recursive1234567891011121314151617181920212223242526272829class Solution {public: bool checkPalindrome(string subStr){ string tempStr = subStr; reve ...

題目敘述 題目難度: Medium 題目描述： 給定一個 m x n 大小的整數2D陣列 grid，有個機器人為位在網格最左上角 (grid[0][0])，機器人想要移動到最右下角 (grid[m-1][n-1])。機器人每次可以選擇往下或是往右邊移動。網格中某些格子有障礙物，有障礙物的那格會被標注 1，如果沒有障礙物則是標注 0，機器人移動的路線中不能包含任何障礙物。 題目要求回傳機器人可以走的所有唯一的路徑數量。 解法一開始的想法一開始的想法一樣還是要找子問題，從左上角起點每次可以選擇往右或往下，而終點會是陣列中 [m-1][n-1] 的位置，最短路徑和可以從終點加上他的上面或左邊那格一路回朔回起點， 因此這會是一個大量重疊的子問題，因此可以用 DP 中的 Recursion + Memoization 來解決。 我的解法 - Recursion + Memoization123 ...

題目敘述 題目難度：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 ori ...

前言 這是第一次寫 Multidimensional DP 的時間小於 20 min 就 AC !! 值得紀念一下 ~ 題目敘述 題目難度：Medium 題目描述： 題目給了一個 m x n 大小的二維整數陣列 grid，陣列中的值為非零整數，請找到從網格左上角走到右下角的最小路徑和， 在每一格每次只能選擇往下或是往右邊走 解法一開始的想法一開始的想法一樣還是要找子問題，從左上角起點每次可以選擇往右或往下，而終點會是陣列中 [m-1][n-1] 的位置，最短路徑和可以從終點加上他的上面或左邊那格一路回朔回起點， 因此這會是一個大量重疊的子問題，因此可以用 DP 中的 Recursion + Memoization 來解決。 我的解法 - Recursion + Memoization1234567891011121314151617181920class Solution { ...

題目敘述 題目難度：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) {} ...

題目敘述 題目難度: Medium 題目敘述: 題目給定一個2D陣列 triangle，求從最頂端走到最底端的最小路徑總和值 對於每個 row 只能往下一層走，並且每次都會有兩種走法，假設現在在當前row的位置是 i，則下一層能夠選擇繼續走到 i 或者是 i+1 的位置。 123456範例: 2 3 4 6 5 74 1 8 3最短路徑總和會是: 2 + 3 + 5 + 1 = 11 解法一開始的想法想法其實也還蠻單純的，就是每層都可以有選或不選特定路徑，由於要找最短的路徑和， 因此需要兩條路徑都選擇，比較回傳結果大小 ，然後選小的回傳，這樣整體遞迴呼叫完畢後就能夠求出最短路徑和。 我的解法Recursive1234567891011121314151617181920212223class Solution {public: int helper( ...

題目敘述 題目難度：Easy 題目敘述： 題目給定兩個整數陣列 nums1, nums2，並以 非遞減的順序排序(non-decreasing order) ，並且給定整數 m 以及 n 分別代表兩個陣列中有多少元素。 題目要求合併兩個陣列，並且一樣已非遞增的順序存放，需要將 nums2 的元素合併到 nums1，而不需用函數返回，nums1 函數的長度會是 m+n 而前 m 的元素會是原先 nums1 中的元素。 可以看上面範例圖中的第一個測資，nums1 中的0會被 nums2 取代掉，並且 m 為3，由於是非遞減排序的陣列，因此0不算是元素之一。 解法一開始的想法我的想法就是先將 nums2 的部分填補到 nums1 多出來的地方，在去排序 我的解答1234567891011121314151617181920class Solution {public: v ...

題目敘述 題目難度：Medium 題目描述：給定一個字串 s，以及一個字串形成的陣列 wordDict，若 s 可以被分割成一個或多個 wordDict 當中的單字序列，則回傳 True Note that the same word in the dictionary may be reused multiple times in the segmentation. 解法一開始的想法s 中的每個字元可以 選或不選，每次形成一個子字串，就去跟 wordDict 進行比較看當前子字串是否存在於 wordDict 當中，一旦嘗試過每個子字串，則回傳結果。 我的解答1234567891011121314151617181920212223242526class Solution {public: vector<int> dp; bool helper( ...