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

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

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

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

前言 這是第一次寫 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 題目描述： 給定一個 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...

題目敘述 題目難度: 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(vector<vector<int>>& triangle, int row, int index ,int result ){ if(r...

題目敘述 題目難度：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: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n){ ...

題目敘述 題目難度：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(string s, int start, vector<string>& wordDict){ if(start == s.length())...

前言 這算是第一次做 LeetCode Weekly Contest 的紀錄，今天是心血來潮上來打，所以準備考的時候只剩下沒多少時間，但我還是菜雞，因此就專攻第一題試水溫，寫完後就停止 題目敘述 題目難度: Easy 題目敘述: 題目給定一個整數陣列 nums，並且需要先選定一個起始點 curr，其中 nums[curr] =0。從起始點可以選擇往左走或往右走，接著可以重複下面的步驟: 若 curr 超出範圍 [0, n-1] 則步驟停止 透過加減 curr 值來實現向左和向右移動，curr 增加: 向右移動，curr 減少: 向左移動 移動後一旦 nums[curr] > 0 則 需要將 nums[curr] 值減一 反轉當前的移動方向 朝新方向前進一步 當移動結束時，所有元素值都歸零則被視為 Valid，請回傳總共有幾種 Valid 的走法 解法一開始的想法首先會需要迭帶題目給的陣列 nums，並且需要找到起始點，可能會有多個起始點，接著就是要從起始點開始向左或向有走來判斷是否 valid，在走訪過程中，一旦碰到大於0的值就會開始反向走，直到碰到另一端的...

題目敘述 題目難度: Medium 題目敘述: 題目給定一個整數陣列 nums，回傳所有可能的遞增子序列中最長的長度 子序列(Subsequence) 可由原先陣列中刪除多個元素來得到，但不可更動其元素順序，其中遞增子序列代表元素由左至右數字漸增 Ex. [5,8,3,2,4,5,9,15,7,20]其子序列包含:[5,8,4,5,20] 非遞增子序列[2,4,9,15] 遞增子序列[15,7,20] 非遞增子序列[5,9,15,20] 遞增子序列 解法一開始的想法一開始的想法比較偏向暴力解，一開始先思考要怎麼手動找出遞增子序列，並且要找到最長的。 對於 nums = [10,9,2,5,3,7,101,18] 1234567i=0 [10,9]i=1 [10,2]i=2 [10,5]i=3 [10,3]i=4 [10,7]i=5 [10,101]i=6 [10,18] -> 遞增子序列，max_length = 2 接著就會是每一輪迭代 1234567891011121314151617181920212223i=0 [9,2]i=1 [9,5]i=2 [9,...