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

題目敘述 題目難度： Medium 題目敘述： 給定一個整數陣列 coins，分別代表不同硬幣的面額，另外給定目標金額 amount，題目要求回傳，達到目標金額 amount 所需的 最少硬幣數量，如果 coins 中的面額無法達到目標金額就回傳 -1 解法一開始的想法首先假設今天陣列是 [1,2,5] 那對於 amount 每次可以選擇減1減2或減5，扣除完畢後下一輪又可以選擇要減1減2還是減5，直到最後如果 amount 為 0 則代表達到目標金額，如果扣除太多 amount < 0 就代表不能達到目標金額，這時候就需要回傳 -1。如果畫出這個想法的遞迴樹會像是下面這樣。 Step1 解法的遞迴樹 可以看到應該會有很多重複的計算，因此稍後也會有最佳化的空間在。 我的解答Step-112345678910111213141516int coinchangehelper(ve ...

(尚未完成)

(尚未完成)

題目敘述 題目難度: Medium 題目描述: 題目假設你是一個專業的竊賊，街上的屋子都有一筆現金，在街上挨家挨戶的入室竊盜，但如果你偷了相鄰兩間屋子就會觸發自動警報報警，你就會被抓。給定一個整數陣列 nums 代表街上每間屋子藏有的錢有多少，請回傳竊賊在不觸發警報的狀況下，可以偷到最大數目的金額。 解法一開始的想法我的想法就是，其實就是要找一個陣列 除了相鄰元素外彼此的相加的所有可能組合當中的最大和。舉例來說，給定 nums={2,7,9,3,1}，那非相鄰的所有可能組合如下： 123452,9,1 => 122,3 => 57,3 => 107,1 => 89, 1 => 10 這當中數值最大的和為 12，而因此有了下面的遞迴做法 錯誤解法12345678910111213class Solution {public: ...

題目敘述 題目難度: Easy 題目敘述: 題目給定一個整數陣列 cost，其中 cost[i] 代表通過第 i 階所需要的成本，一旦付完成本後，就可以再度選擇走一階還是兩階直到到達階梯頂端。題目也有說明，起點也可以選第一階 (index=0) 或者第二階 (index=1) 開始。這題的最終目標要求的是到達頂端所需要的最小成本是多少。 解法一開始的想法這題是基於 LeetCode 76. Climbing Stairs 的延伸問題。那這題根據題目給的例子，假設 cost=[10,15,20] 由於初始可以選第一階或第二階，而所有走法如下: 123410, 15, 20 = 45 (每次走一階)10,20 = 30 (先走一步再一次跨兩階)15, 20 = 35 (起點在第二階，然後再走一階)15 (起點 ...

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

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

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

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