AMGE’s Blogger

Leetcode 網址: https://leetcode.com/problems/longest-palindromic-substring/ 題目說明: 給定一個字串 s，請找出該字串 s 中最長的回文子字串。 Example 1: Input: s = "babad" Output: "bab" Note: "aba" is also a valid answer. Example 2: Input: s = "cbbd" Output: "bb" Example 3: Input: s = "a" Output: "a" Example 4: Input: s = "ac" Output: "a" 解題說明: 該題有很多種解法，這邊主要介紹二種我比較喜歡的解法: 第一種是 Dynamic Programming， 假設我們有一個字串 S(l, r) 要判斷是否為回文， 因為回文的特性，所以 S(l - 1, r + 1) 勢必也要是回文，否則 S(l, r) 絕對不是回文。 例如: S(2, 5) 是否為回文必須要 S[2] == S[5] 而且 S(3, 4) 也是回文， 而 S(3, 4) 是否為回文則必須要 S[3] == S[4] ，而且 S(4, 3) 代表 right 小於 left，故不需理會。 透過以上，我們即可寫出一個 DP 的程式來解決這個問題，其空間跟時間複雜度皆為 O(n * n)。 第二種解法則是 Expand Around Center， 我們可以知道最長回文的長度不是奇數就是偶數 (這不是廢話嗎 XD)， 假設長度是奇數，那代表最長回文的正中間是一個字元， 假設長度是偶數，那代表最長回文的正中間是二個字元， 所以我們從字串中找出所有正中間的字元 (時間複雜度為 O(n))， 並藉由正中間字元的往外擴散去找回文 (時間複雜度為 O(n))， 透過以上，我們即可以寫出一個不需要額外空間的解法，其時間複雜度為 O(n * n)。 程式碼 (DP) class Solution { public: string longestPa...

Leetcode 網址: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/ 題目說明: 給定一個長度為 n 的序列，序列內的第 i 個數字代表第 i 天股票 A 的價格， 投資人被允許這 n 天內最多執行 2 次完成的交易 (買進 + 賣出算一次完整的交易)， 請設計一個演算法找出最大的獲利。 Note: 交易所限制買進時，手上必須沒有股票。 Example 1: Input: prices = [3,3,5,0,0,3,1,4] Output: 6 Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3. Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3. Example 2: Input: prices = [1,2,3,4,5] Output: 4 Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again. 解題說明: 遇到這種題目一開始沒有想法的話就先將 input 變小， 例如思考長度為 n 的序列之最大獲利要如何從 n - 1 中的序列推出呢 ? 思考了之後可以發現長度為 n 的序列之最大獲利可以分成二個情況: 1. 最大獲利的交易是否包含第 n 天 ? 如果不包含那答案就跟 n - 1 序列的最大獲利相同 2. 最大的獲利交易包含第 n 天，那麼我們就從 n - 1 的序列中找出最便宜的價格買進，並於第 n 天賣出 有以上的想法就可以把這想法寫成演算法囉 ~ 程式碼 class Solution { pu...

Leetcode 網址: https://leetcode.com/problems/edit-distance/ 題目說明: 給定二個字串 word1 以及 word2，請找出最少需要幾個操作才能將將 word1 轉換成 word2。 操作的定義有三種:    1. 新增字元 2. 刪除字元 3. 取代字元 Example 1: Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e') 解題說明: 遇到這種題目一開始沒有想法的話就先將 input 變小， 以範例 1 的而言，我們慢慢將 input 由小至大就可以推論出下表: 最後根據上表及推導中可以發現這題是個 Dynamic Programming 題型， 將推導的結果寫成演算法即可解決此題。 程式碼 class Solution { public: int minDistance(string word1, string word2) { int dp[word1.length() + 1][word2.length() + 1]; memset(&dp[0][0], 0, (word1.length() + 1) * (word2.length() + 1) * sizeof(int)); for (int i = 1; i <= word1.length(); i++) dp[i][0] = i; for (int i = 1; i <= word2.length(); i++) dp[0][i] = i; for (int i = 1; i <= word1.length(); i++) { for (int j = 1; j <= word2.length(); j++) ...