Shannon's Blog 🐟 技術 | 生活 | 旅行

1 題目描述 從numbers裡面找出兩個數字，使得他們的和等於target，並且返回這兩個數字的索引，且索引是從1開始。 這個題目要求空間複雜度為O(1)，因此我們不能使用hashmap。 2 解法 2.1 暴力解法 最純的暴力破解法，就是O(N^2)遍歷所有的組合，找出符合條件的組合。 1234567class Solution: def twoSum(self, numbers: List[int], target: int) -> List[int]: n = len(numbers) for i in range(n): for j in range(i+1, n): if numbers[i] + numbers[j] == target: return [i+1, j+1] 2.2 Speed O(N) 這題的關鍵是，我們該如何避免檢查那些不可能的組合？ 我一開始沒有立刻領悟出 numbers[right] + numbers[l...

前言 今天想要深度的去了解Two pointer與sliding window 的使用，這也是面試常見的技巧。主要整理出『如何辨識要使用這些技巧』。 Two Pointer 那我們先從two pointer開始，因為sliding window其實是two pointer的一種特例，或是進階應用。 那麼什麼是two pinter呢？pinter 俗稱指標，指標用來儲存另一個物件的記憶體位置，通常在leetcode中，指標只是一個整數，用來指向陣列的某個物件索引。 12345678pointer = 0arr = [10, 30, 50, 70, 100] ^arr[pointer] = arr[0] = 10pointer = 3arr = [10, 30, 50, 70, 100] ^arr[pointer] = arr[3] = 70 Two pointer就是指向陣列的兩個指標，通常是指向陣列的頭尾，然後向中間移動，或是指向陣列的兩個不同位置，然後向中間移動。雙指標允許我們同時查看兩個不同的值，然後我們根據這兩個值的關係來決...

1 題目描述 給定一個數組，其中第i個元素是第i天的股票價格。你最多可以完成兩筆交易。請計算你可以獲得的最大利潤。 注意的是，你的股票是在賣掉之前，不可以再買入。 2 解法 2.1 Recursion 一次遍歷每個股票價格，然後選擇買入或賣出，然後遞歸下去。這樣的時間複雜度是O(2^N)。 沒股票：如果目前沒有股票，那麼可以選擇買入或不買入。 有股票：如果目前已經有股票，那麼可以選擇賣出或不賣出。 而目前題目說，可以進行2次的transaction，基本上1次transaction就是買入和賣出，也就是2次的action，因此2次的transaction就是4次action。 從上面看到，基本上會有四種可能 買入 不買入 賣出 不賣出 我們需要幾個變數 idx: 當前的股票價格 have_stack: 是否有股票，來決定是買入還是賣出 count: 剩餘的交易次數 如果沒股票 12345if not have_stack: # 這次買入(-cost)，下次就只能選則賣出 do_action = -prices[idx] + helper(idx+1, n...

1 題目描述 給定一個二維矩陣matrix，找到只包含1的最大正方形，並返回其面積。 2 解法 其實看到這種2D的DP題目，老樣子可以先把圖片畫出來，然後開始找規律，我們可以先定義如下： dp[i][j] 代表以matrix[i][j]為右下角的最大正方形邊長，這樣的話我們就可以推導出以下公式： 如果matrix[i][j] == 1 那麼dp[i][j]就是min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1，這裡的+1是因為matrix[i][j]是1，所以可以構成一個正方形 如果matrix[i][j] == 0 那麼dp[i][j]就是0，因為無法構成正方形 比較特別的是思考的方式：但是必須考慮dp[i][j]的時候，周遭的cell必須都是計算過的，才可以透過解決小問題來解決大問題 可以從最左下角開始思考，那我們就要看dp[i][j]的左邊、下面、下斜角的cell 或是從最右上角開始思考，但是必須考慮dp[i][j]的右邊、上面、上斜角的cell Solution1: 左下角開始 Solution2: 右上角...

1 題目描述 給定兩個單詞word1和word2，找到將word1轉換為word2所需的最小操作數。 操作包括插入一個字符、刪除一個字符、替換一個字符 美的操作的成本是1 2 解法 我會建議先畫出一個dp圖，這個dp代表，word1的前i個字元與word2的前j個字元的最小操作數，這樣就可以從dp[i-1][j-1]推導出dp[i][j]。 你會發現，第一列或是第一排，也就是word1或word2為空的時候，最小操作數就是當前字元的長度，可以透過這個特性來初始化dp。 如上圖所示，可以寫出以下程式碼進行初始化： 1234567891011121314151617class Solution: def minDistance(self, w1: str, w2: str) -> int: m = len(w2) n = len(w1) # 如果某一方為空，但是雙方長度不一樣，就回傳最長的那個 if (n == 0 or m == 0) and n != m: return max(m...

1 題目描述 找到最長的字串，該字串是回文的，也就是說，從左到右和從右到左是一樣的。 2 解法 2.1 暴力破解 12345678910111213141516def isPalindrome(s: str, i: int, j: int) -> bool: while i < j: if s[i] != s[j]: return False i += 1 j -= 1 return Truedef longestPalindrome(self, s: str) -> str: best = "" n = len(s) for i in range(n): for j in range(i, n): if j - i + 1 > len(best) and isPalindrome(s, i, j): best = s[i:j+1] return best 2.2 由中...

1 題目描述 給定一個m x n的矩陣，找到一條從左上角到右下角的最小路徑和。每次只能向右或是向下移動，但是他中間有障礙物，所以要避開障礙物。 2 解法 這題與LeetCode 課前預習 - 掌握 Dynamic Programming 的思維指南的題目類似，如果你會做Leetcode-62-Unique Paths，這題也是一樣的概念，只是這題有障礙物，因此碰到障礙物就要記得把路徑設定為0。 2.1 Iterative 因為已經做過類似的題目，所以直接從Iterative下手，我的想法是這樣的： 今天邊緣也有可能有障礙物，所以要從邊緣開始處理 如果碰到障礙物，就把路徑設定為0 其他的就是從上面或是左邊來的路徑和 12345678910111213141516171819202122232425def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int: rows = len(obstacleGrid) columns = len(obstacleGrid[0]) ...

1 題目描述 給定一個m x n的矩陣，找到一條從左上角到右下角的最小路徑和。每次只能向右或是向下移動。 2 解法 這題與LeetCode 課前預習 - 掌握 Dynamic Programming 的思維指南的題目類似，如果你會做Leetcode-62-Unique Paths，這題也是一樣的概念，只是這題是找最小路徑和。 2.1 Recursive 首先我們很清楚，我們只能往右或是往下走，假設i是row，j是column， 所以我們可以寫出以下的關係式 往右：helper(i, j+1) column + 1 往下：helper(i+1, j) row + 1 然後關係式：min(往右, 往下) + 當前 1min(helper(i, j+1), helper(i+1, j)) + grid[i][j] 接下來我們來解決最小問題的狀況： 如果只有一行或是一列，直接回傳總和，因為只有一條路可以走 何時知道走到底，當i==rows-1和j==cols-1時，就是走到底了，直接回傳grid[i][j] 12if i == rows-1 and j == cols-1: ...

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 之間哪一個數字是最適合的，唯一的方法就...