LeetCode #15 3Sum - 刷題之旅
1 題目描述
找到所有可以使三個數字的和為零的不重複組合。
2 解法
看到不重複,腦子第一個冒出來是set。應該要把所有的組合都放進去,然後再轉成list。
而這題是two pointer卻要找3個數字的和為0,而two pointer使用的前提最好是==排序==過的數組。我們可以透過固定一個數字,然後使用two pointer的方式找到另外兩個數字。
2.1 Hash Set
12345678910111213141516171819202122232425262728293031323334==== Step 1 ====# nums 排序過# i 是固定的數值# l, r 分別是 left pointer 和 right pointer[-4,-1,-1,0,1,2] i l r# 因為還太小,我們透過移動l來使總合變大nums[i] + nums[l] + nums[r] = -3==== Step 2 ====[-4,-1,-1,0,1,2] i l r# 因為還太小,我們透過移動l來使總合變大nums[i] + nums[l] + nu ...
LeetCode #11 Container With Most Water - 刷題之旅
1 題目描述
給定一個非負整數的數組height,每個元素代表一個垂直線,並且每個線的寬度都是1。找出兩條線,使得他們和x軸組成的容器可以容納最多的水。
(注意不可以傾斜容器)
2 解法
2.1 暴力解法
這題的暴力破解是O(N)基本上就是遍歷所有的組合,找出最大的容器。
12345678class Solution: def maxArea(self, height: List[int]) -> int: n = len(height) ans = 0 for i in range(n): for j in range(i+1, n): ans = max(ans, min(height[i], height[j]) * (j-i)) return ans
2.2 Speed O(N)
從知道這是two pointer的時候就要有個認知,那就是某種程度上他是有序的,這個案例有兩個變數,在計算面積 = 距離(指標距離) * 高度(min指標值),我們知道,距離最大 ...
LeetCode #167 Two Sum II - Input array is sorted - 刷題之旅
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[left ...
LeetCode 課前預習 - 掌握 Two Pointer 和 Sliding Window 捕捉使用時機
前言
今天想要深度的去了解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就是指向陣列的兩個指標,通常是指向陣列的頭尾,然後向中間移動,或是指向陣列的兩個不同位置,然後向中間移動。雙指標允許我們同時查看兩個不同的值,然後我們根據這兩個值的關係來決定下一 ...
LeetCode #123 124 Best Time to Buy and Sell Stock - 刷題之旅
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, not ...
LeetCode #221 Maximal Square - 刷題之旅
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: 右上角開始
...
LeetCode #72 Edit Distance - 刷題之旅
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, n ...
LeetCode #5 Longest Palindromic Substring - 刷題之旅
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 由中心向外 ...
LeetCode #63 Unique Paths II - 刷題之旅
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]) dp ...
LeetCode #64 Minimum Path Sum - 刷題之旅
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: ...