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

題目敘述 題目難度：Easy 題目敘述：題目描述要爬階梯，需要 n 階可以到頂端，每次可以跨一步或是兩步，有多少種爬到頂端的方式? 解法一開始的想法首先要先思考這題的遞迴關係，任意階的步驟數，會是由什麼組成？ 這裡可以觀察到如果 n=1 也就是往上一層有幾種走法，答案就是 1 因為只能走一步，那 n=2 這時就可以選擇走兩次一步 [1,1] 或者是一次走兩步 [2]，也就是有兩種選擇，那若 n=3 呢？ 往上三階其實就是往上一階和往上兩街的組合，因此他們對應的走法數量也會是 n=1 和 n=2 的加總 1234n=1 | output1=1n=2 | output2=2n=3 = 2+1 | output= output1+ output2 因此可以總結遞回式為 $F(n) = F(n-1) + F(n-2)$，把它寫成程式如下： 123456int climbStairs(int n){ if(n<=0) return 0; if(n==1) return 1; if(n=2) return 2; return cli...

前言從還沒開始刷題前就耳聞了DP題目的恐怖，因此想說在實際開始刷類似題目前整理一下DP的知識。 在閱讀網路資料的時候發現這篇文章解釋得很好，因此非常推薦先閱讀這篇 文章，作者有提到要理解 DP，耐心很重要，然後還需要熟悉遞迴，因為DP問題通常會用遞迴來解決 甚麼是 Dynamic Programming(DP)?這裡我必須提到上面那篇文章說的結論: Dynamic Programming 是一種用來幫助遞迴程式碼更加有效率的工具，所以文章作者也認為不該在面對一個問題的時候就先去識別這個問題是否是一個 DP問題，而是先判斷是否需要用到遞迴，而在遞迴的基礎上，會延伸思考到這個遞迴程式碼可能會很冗，因此有答案應該會有改善空間，而改善的方式就透過 Dynamic Programming DP 是用來改善現有 Solution 的方式 ! 接下來介紹使用這個工具的步驟，其中包含了4個步驟，這裡會用一個題目來逐步解釋 題目:　LeetCode62. Unique Paths 這題中給了一個大小 m x n 的格子，有一個機器人在最左上角的位置，機器人每次執行可以往下或往右走一格，機...

題目敘述 題目難度: Medium 題目敘述: 題目給定一個 single linked list，L0 → L1 → … → Ln - 1 → Ln 請將這個 list 重組成 L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … 在這當中請不要改動節點值。 解法一開始的想法 由於排序看起來像是把一個 linked list 頭尾對折然後再交互連接，因此我的想法會是先找到鏈結的中間節點，再將其拆分成兩個 list，之後將後半部分的 list 進行反序排列，接著再跟前半部分的list交互排列。 我的解法12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), ne...

題目敘述 題目難度：Medium 題目敘述： 給定一個 Linked List 的 head，移除從尾端數來第 n 個節點，並返回list 解法一開始的想法最直覺的做法就是，先取得 list 長度，再用長度扣掉 n 得到的數字假設是 m，就要被刪除的就是從首端往後數的第 m 個節點。 刪除節點這部分也很基本，那就是透過一個 pointer 指向要被刪除節點指向的下一個節點位址，在讓待刪除節點的前一個節點指向這個 pointer，最後返回 head 我的解法123456789101112131415161718192021222324252627282930313233343536373839404142434445/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : v...

題目敘述 題目難度： Medium 題目敘述：給定字串 s，分割字串使其所有子字串都是 回文(Palindrome) ，並回傳所有可能的分割結果 回文(Palindrome) 代表字串從左往右讀的結果跟從右往左讀的結果一樣。 解法一開始的想法這題的想法一樣會是 backtracking，主要會需要去分割每個字串，意思是將不同字串組合加入到某個字串變數中，接著需要檢查該字串組合是否是回文，如果不是，那就繼續嘗試其他字串組合，如果是回文，那就將該字串組合添加到子陣列中，並且進入下一層遞迴。 遞迴終止條件就是當前遞迴深度已經達到題目給的字串長度 到目前爲止的想法都蠻正確的，但這次主要會是在字串分割還有字串反轉，我其實還沒刷對應題目，因此要怎麼樣在Leetcode 中快速做到，是這題中學習的 我的解法123456789101112131415161718192021222324252627282930class Solution {public: vector<vector<string>> result; bool check...

題目敘述 題目難度: Easy 題目描述: 給定字串 pattern 以及 字串 s，檢查 s 是否遵循相同模式 題目有說明這裡 相同模式 的意思: pattern 中的任一字元與 s 中的非空字串完全匹配的 1對1映射關係，具體來說規則如下: 在 pattern 中的每個字母，都有明確的對應到 s 中的 unique 字串 在 s 中的 unique 字串，明確對應到 pattern 中的一個字母 沒有兩個字母映射到同一個單詞，也沒有兩個單詞映射到同一個字母 解法一開始的想法這裡想法很單純就是透過 Hash Table 來去建立並儲存映射關係。而在建立過程中可以去檢查當前的字母和對應字串是否已經存在映射關係於 hash table 中，如果有救回傳 false，如果整個 hash table都建立好後都沒有重複的映射關係那就回傳 true。 我的解法1234567891011121314151617181920212223242526272829303132333435class Solution {public: bool wordPatter...

題目敘述 題目難度: Medium 題目敘述：給定一個整數陣列 nums， 回傳所有可能的子集，回傳的子集不能重複，但可以任意順序排序 這題是 78.Subsets 的延伸題型，可以看我這一篇解法，但是這題不同的是，對於 nums 陣列中 [2] 是不等於 [2,2] 的，但 [1,2] 是等於 [2,1] 的，也就是説對於個別子集來說，若相同元素但元素數量不同則看成不同子集 解法一開始的想法我的想法就跟上一題差不多，只是想說在添加到回傳陣列時，額外進行檢查，踢除重複的子集。 我的解法123456789101112131415161718192021222324252627282930class Solution {public: vector<vector<int>> result; void subsetHelper(vector<int>&nums, vector<int> &cur, int depth){ if(depth == nums...

題目敘述 題目難度: Medium 題目敘述: 給定一個具有不重複元素的整數陣列 nums，回傳所有可能的子集合 子集會包含空集合，另外，若子集中的元素相同但順序不同，則視為相同子集。 123Ex. nums = {1,2,3}[1,2] = [2,1][1,3,2] = [3,1,2] 解法一開始的想法子集合問題也是典型的 backtracking 問題，它包含了在每個數字中選與不選，因此終止條件會是目前選擇的深度到達題目所給的長度上限就停止，而在每一層中要做的事就是選跟不選，首先是不選，那就會需要直接往往下一層去，到下一層在進行選以及不選，直到到達長度限制。 假設題目是 nums={1,2} 則他的樹狀結構會如下： 123456 [] / \ [] [1] / \ / \[] [2] [1] [1,2] 我的解法123456789101112131415161718192021222324class Solution {publ...

題目敘述 題目難度： Hard 題目描述： N-Queens 其實就是有名的八皇后問題，將 n 個皇后放到一個大小為 n x n 的棋盤，使得任何一個皇后都無法直接吃掉其他的皇后，題目要求輸入 n 求所有可能的棋盤組合，答案的可以是任意順序。每個解答中都需要能夠呈現皇后的擺放位置，題目中以 'Q' 代表皇后，而 '.' 代表空位。 這裡可以看八皇后問題的介紹：八皇后問題 補充：在西洋棋中，皇后可以走直的、橫的和協的，因此如果皇后的的位置如下，則以它為中心的十字及對角都不能走，都可能會被攻擊 1234| . | $ | . | $ || $ | $ | $ | . || $ | Q | $ | $ || $ | $ | $ | . | 解法一開始的想法首先這個問題一樣是要窮盡各種可能的走法組合，因此想法一樣會是朝 backtracking 想。首先對於 backtracking 的遞迴終止條件，首先題目給的棋盤會是二維的向量 vector<vector<string>>因此我們在每一層中會去窮盡所有可能的排法，一定...

題目敘述 題目難度：Hard 題目敘述： 題目給定你一個 Binary Tree 的 root，求這棵二元樹中的所有路徑中，最大路徑和 這裡二元樹的路徑的代表的是 節點序列，序列由每個由邊連接的相鄰節點組成。一個節點最多只能在序列中出現一次。請注意，該路徑不需要經過Root節點 解法 這是第一次解 Hard，真的花比較久的時間，但也學習到很多 一開始的想法我一開始的想法是有問題的，但還是紀錄一下這個錯誤思路，我一開始想得太簡單了，以為就先把所有二元樹的節點DFS 走訪一遍，就能夠得到一個節點順序，接著就是 backtracking 中的子集問題，在序列中找子集元素和最大的組合就是答案。 但這有一個缺陷，那就是DFS(inorder)走訪過程的順序不滿足題目敘述的節點序列 像是下面這個例子，經過 inorder 走訪過後的順序會是 -8, 10, 20, -5, -10 那這樣後面就可能以為 10 跟 20 會是相鄰的，且最大的就輸出 30，但實際情況就是他們之間根本沒有邊相連。 因此這樣的做法會是錯的。 所以做法其實也算是 DFS 但不會是傳統意義上的 ba...