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

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

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

題目敘述 題目難度： Medium 題目敘述： 給定字串 s，回傳 s 中有多少回文子字串，回文代表字串從前往後讀等於從後往前讀都是一樣的字串。 解法一開始的想法我的想法就是可以遞迴處理，每次可以讀取一段字串，之後用一個函數檢查是否是回文，如果是，就將字串加入結果列表， 12345678910111213s = "abc"a -> Check if palindromicab -> Check if palindromicabc -> Check if palindromicac -> Check if palindromicb -> Check if palindromicbc -> Check if palindromicc -> Check if palindromiclist = [a,b,c]return list ...

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