LeetCode #120 Triangle - 刷題之旅
1 題目描述
給定一個三角形,找到從頂部到底部的最小路徑和。每一步只能移動到下一行的相鄰元素上。
2 解法
其實這題與leetcode #300 Longest Increasing Subsequence有點類似,如果我們嘗試用樹狀圖,把所有可能寫出來,如果今天題目是[[1], [2,3], [4,5,6], [7,8,9,10]]大概會長以下這樣:
特徵如下:
從底部慢慢往上走,算出每層由下往上的最佳解
dp 的值是由下往上的最佳解
2.1 Recursion
但我們先慢慢來吧,先寫出Recursion的寫法。他的問題也是經典的拿與不拿問題。題目可以看到,如果我這一層layer取i,那我下一層layer只能取i或是i+1,這兩個選最小的。
其實Recursive的關係式
(helper是recursive的function)
1min(helper(layer+1, i), helper(layer+1, i+1)) + triangle[layer][i]
那最小問題基本上就是當已經走到底了,直接回傳triangle[layer][i],因為這時候就是最底層了,不用再往 ...
機器學習 - 如何提高分類器的準確度
前言
CSND | 提高SVM分類器的準確率
目前,因為論文的主要題目是做法律文件的機器學習分類,但是因為資料量少,碰到一點瓶頸。所以整理了一些提高分類器準確度的方法,但是注意的是本篇內容主要針對傳統的機器學習像是SVM, RF, NB等,並非Deep Learning。主要有以下:
特徵工程:選擇更好的特徵
調整超參數:可以透過找到最佳的超參數組合,來提高分類器的準確率
數據清洗與預處理:數據清洗是機器學習中非常重要的一個環節,數據清洗的好壞直接影響到模型的準確率
使用核函數:有些模型像是SVM可以使用不同的核函數,來提高分類器的準確率,例如線性核函數、多項式核函數、高斯核函數等
集成學習:使用集成學習如Bagging、Boosting等方法,來提高分類器的準確率
增加訓練數據:增加訓練數據,可以提高分類器的準確率,特別是針對複雜的問題
調整超參數
你是否曾經覺得模型有太多的超參數而感到厭煩嗎?要從某一個演算法得到好的解必須要調整超參數,所謂的超參數就是控制訓練模型的一組神秘數字,例如學習速率就是一種超參數。你永遠都不知道 0~1 之間哪一個數字是最適合的,唯一的方法就是試錯 ...
LeetCode Biweekly Contest #Find the Power of K-Size Subarrays - 打怪開始
1 題目描述
這是我的第一次參加 LeetCode Contest,這次的題目是一道簡單的滑動窗口問題,給定一個數組nums和一個整數k,你需要針對大小為 k 的所有子陣列計算它們的 “power”:
如果子陣列的所有元素是連續且按升序排列,則該子陣列的 power 是其最大元素。
如果子陣列的元素不符合條件,則返回 -1。
2 解法
2.1 我的解法
我一開始的想法很簡單,我需要有一個function負責檢查是否為連續且按升序排列,如果是就返回最後一個數值,如果不是就返回-1。
12345def helper(sub_nums: List[int]) -> int: for j in range(1, k): if sub_nums[j - 1] + 1 != sub_nums[j]: return -1 return sub_nums[-1]
接下來我們只要根據 k 的長度,把數組分成大小為 k 的子陣列,然後檢查每個子陣列是否符合條件,如果符合就找出最大值,如果不符合就返回-1。
12345678910111213141 ...
LeetCode #300 Longest Increasing Subsequence - 刷題之旅
1 題目描述
給定一個整數數組nums,找到一個最長的遞增子序列的長度。
2 解法
2.1 Recursion
這題是DP問題,假設我們有一組數字[1, 2, 3, 7, 4, 5, 6] 我們需要比較當前的值 nums[i]是否比上一個值 last還要大,當滿足條件的時候,我們就要思考一個問題到底是**要把當前的值考量進去,還是跳過當前的?**這就會牽涉到兩個公式,類似背包問題,偷與不偷,那這裡就是塞與不塞:
塞: 1塞(當前值) + 未來的最佳解
不塞: 不塞 + 未來的最佳解
以上述的例子來說,如果我們走到 7 的時候,我們可以選擇塞或不塞
如果塞的話,未來的最佳解都是 0,因為沒有比7大的值了
如果不塞的話,後面還有4, 5, 6可以選擇
這樣的話我們可以得出一個公式,假設i是當前的值:
塞: 1 + helper(nums[i+1:])
不塞: helper(nums[i+1:])
但是還有一個問題需要考慮,就是我們在往後比較的時候,需要知道被比較的對象是誰,舉例來說一樣從7開始
塞:那後續與4, 5, 6比較的就是7
不塞:那後續與4比較的就是3,與5比較的 ...
LeetCode #322 Coin Change - 刷題之旅
1 題目描述
給定不同面額的硬幣coin和一個總金額amount,寫一個函數來計算可以製造出總金額的最少硬幣數量。如果無法製造出總金額,則返回-1。
2 解法
其實dp的題目中有個共通點,都像是書包題目,為什麼是 dp 問題是因為可以拆分成小問題,而 amount 的小問題基本上就是 range(1, amount+1) 這些範圍如果都能夠找到最佳解ㄝ那自然amount也能找到最佳解。所以我們腦子有個思路,就是我們可以先從1開始。而最小值就是0,因為0元不需要硬幣。
小問題開始
123456# 初始化 dp 碰到 0 的 amount 就是 0dp = {0: 0} # 因為 range 是不包含最後一個數字,所以要 +1 for i in range(1, amount+1): # 初始化 dp[i] 為無限大 dp[i] = float('inf')
接下來,我們假設: amount=11 且 coins=[3, 5],我們可以看到dp的變化如下:
dp[0] = 0
dp[1] = inf 沒有對應的 coin
dp[2] ...
LeetCode #139 Word Break - 刷題之旅
1 題目描述
這題簡單來說就是給定一個字串s和一個字典wordDict,判斷s是否可以被空格分割成一個或多個在字典中出現的單詞。
2 解法
2.1 我的作法
但是這個為什麼說他是一個dp問題,是因為他就像背包問題一樣,s是背包,wordDict是物品,我們要看看s能不能裝下wordDict裡面的物品。如果裝錯物品可能導致裝不下。
我的想法一開始是一個用切割的方式切成兩塊,然後把所有可能的組合都存到字典裡面,最後找到可以把目前切割結果組合成s的組合。
切割成兩塊
例如:applepenapple
a + pplepenapple
ap + plepenapple
app + lepenapple
…
123for i in range(1, n): check_w = word[0:i] rest_w = word[i:n]
如果找到一組,切成兩塊的結果都是True就找到了
假設helper是一個可以判斷是否可以切割成wordDict的函數
關係式:helper(word[0:i]) and helper(word[i:n])
12345for i in ran ...
LeetCode #198 House Robber - 刷題之旅
1 題目描述
有一排房子,每個房子裡面有一定的錢,但是不能連續偷兩個房子,否則會報警,在不觸發報警的狀況下求最多可以偷到多少錢。
2 解法
按照之前的介紹LeetCode 課前預習 - 掌握 Dynamic Programming 的思維指南,我很推薦把每一種步驟都嘗試寫出來看看,分別是:
Step1: Recursive
Step2: Recursive with Memoization
Step3: Iterative + Tabulation
Step4: Iterative with Constant Space
Step1: Recursive
一道很典型的通過子問題去解決原問題的題目,所以可以透過遞歸以及動態規劃解決。
假設:知道了前 n - 1 家店最多能偷的錢數,前 n - 2 家店最多能偷的錢數。
關係式:如果我們想要知道前 n 家商店最多能偷多少錢,我們可以選擇偷
偷:偷第 n 家商店 + 前 n - 2 家商店最多能偷的錢數。
不偷:不偷第 n 家商店 + 前 n - 1 家商店最多能偷的錢數。
最小問題:如果今天 n = 0,那麼就是0,如果n = 1 ...
LeetCode #70 Climbing Stairs - 刷題之旅
1 題目描述
爬樓梯,每次可以爬一階或是兩階,求爬到第n階有幾種方法。
2 解法
按照之前的介紹LeetCode 課前預習 - 掌握 Dynamic Programming 的思維指南,我很推薦把每一種步驟都嘗試寫出來看看,分別是:
Step1: Recursive
Step2: Recursive with Memoization
Step3: Iterative + Tabulation
Step4: Iterative with Constant Space
Step1: Recursive
最基本也是最蠢的就是我們要先發現,基本上走樓梯的方法數量是f(n) = f(n-1) + f(n-2),這樣的遞迴式,我們可以直接寫出來。
123456def climbStairs(n): if n == 1: return 1 if n == 2: return 2 return climbStairs(n-1) + climbStairs(n-2)
Step2: Recursive with Memoization
那我們就思考,是不 ...
LeetCode 課前預習 - 掌握 Dynamic Programming 的思維指南
前言
我希望可以熟悉DP的思維,剛好看到這篇Medium | Ultimate Guide to Dynamic Programming獲得蠻多的讚,所以打算這篇為基礎做筆記。
在解決Dynamic Programming重要的前提是:
耐心: DP問題通常需要花時間來思考,不要急著寫程式
熟悉遞迴: DP問題通常可以用遞迴的方式來解決,因此熟悉遞迴是很重要的
Recursion遞迴跟DP的不同
遞歸和動態規劃的主要關聯在於:
重疊子問題:如果一個遞歸算法在計算過程中重複解決相同的子問題,可以使用動態規劃來優化。這時,遞歸算法可以轉化為帶備忘錄的遞歸(自頂向下的動態規劃)。
最優子結構:如果一個問題的最優解可以由其子問題的最優解構成,那麼可以使用動態規劃來解決這個問題。
有一個很簡單的例子,使用Fibonacci數列來說明這兩個概念。
Fibonacci數列的遞歸解法123456def fib(n): if n == 0: return 0 if n == 1: return 1 return fib(n-1) + fib(n-2) ...
LeetCode #98 Validate Binary Search Tree - 刷題之旅
1 題目描述
2 解法
我的問題是在,我一開始以為,只要把上一個節點,傳下去,跟下一層的節點進行比較就好了。但是我錯了!
我一開始腦子想著
你會發現上圖根本不是正確的二元搜尋樹,因為節點3比root小,不應該出現在右子樹中…所以我就卡住了。
2.2 使用Recursion
其實這題真的目的在於,在 左子樹,只要一往右走,就要考慮到根節點的值,不能大於root.val。而在右子樹,只要一往右走,就要考慮到根節點的值,不能小於root.val。我想了好久,都沒想到到底要怎麼樣知道走不同子樹的路線時(在左子樹還是在右子樹),還能知道當前到底走在哪個方向(一往右走,還是一往左走)…直到我試著畫出每個節點的上下限。
你會發現,根本不需要顧慮左還是右子樹,你會發現:
只要是往左走,max一定會更新成parent.val,而min則是繼承自上一層的min。
只要是往右走,min一定會更新成parent.val,而max則是繼承自上一層的max。
然後神奇的事情發生了:
因為在左子樹往右走時,max會一路繼承上一層的max,追溯到源頭就是root! 也就是說,我們在左子樹往右走時,m ...